Basic Calculator - Practice Coding Problems

Basic Calculator - Problem

Given a string s representing a valid mathematical expression, implement a basic calculator to evaluate it and return the result.

The expression contains:

Non-negative integers
Addition (+) and subtraction (-) operators
Parentheses ( and ) for grouping
Spaces (which should be ignored)

Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().

Input & Output

Example 1 — Basic Expression

$ Input: s = "1 + 1"

› Output: 2

💡 Note: Simple addition: 1 + 1 = 2

Example 2 — With Parentheses

$ Input: s = " 2-1 + 2 "

› Output: 3

💡 Note: Left to right evaluation: 2 - 1 + 2 = 1 + 2 = 3

Example 3 — Nested Parentheses

$ Input: s = "(1+(4+5+2)-3)+(6+8)"

› Output: 23

💡 Note: Inner parentheses first: (4+5+2)=11, then (1+11-3)=9, finally 9+14=23

Constraints

1 ≤ s.length ≤ 3 × 10⁵
s consists of digits, '+', '-', '(', ')', and ' '
s represents a valid expression
'+' is not used as a unary operation
'-' could be used as a unary operation (i.e., "-1" and "-(2 + 3)" are valid)
There will be no two consecutive operators in the input
Every number and running calculation will fit in a 32-bit integer

Visualization

Tap to expand

Understanding the Visualization

Input

String expression with numbers, +/-, parentheses, spaces

Process

Parse and evaluate respecting parentheses precedence

Output

Single integer result

Key Takeaway

🎯 Key Insight: Use a stack to save the current state when entering parentheses and restore it when exiting

Asked in

G Google 45 a Amazon 38 M Microsoft 32 A Apple 28

The key insight is to use a stack to manage state across different parentheses levels. Best approach is the stack-based solution which processes each character once while maintaining previous results and signs. Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Stack-Based Approach	O(n)	O(n)	Use stack to track signs and partial results at each parentheses level
Recursive Parsing	O(n)	O(n)	Use recursion to evaluate expressions inside parentheses first

Stack-Based Approach — Algorithm Steps

Initialize stack with result=0, sign=1
For '(': push current state, reset for inner expression
For ')': pop previous state and combine
Process digits and operators normally

Visualization

Tap to expand

Step-by-Step Walkthrough

Process Characters

Build numbers and apply operations, push state on '('

Stack Management

Stack stores previous result and sign for each parentheses level

Combine Results

Pop stack on ')' and combine with current result

Code -

solution.c — C

#include <stdio.h>
#include <string.h>
#include <ctype.h>

#define MAX_SIZE 1000

int stack[MAX_SIZE];
int top = -1;

void push(int val) {
    stack[++top] = val;
}

int pop() {
    return stack[top--];
}

int solution(const char* s) {
    top = -1;
    int result = 0;
    int sign = 1;
    int num = 0;
    int len = strlen(s);
    
    for (int i = 0; i < len; i++) {
        char c = s[i];
        
        if (isdigit(c)) {
            num = num * 10 + (c - '0');
        } else if (c == '+') {
            result += sign * num;
            num = 0;
            sign = 1;
        } else if (c == '-') {
            result += sign * num;
            num = 0;
            sign = -1;
        } else if (c == '(') {
            push(result);
            push(sign);
            result = 0;
            sign = 1;
        } else if (c == ')') {
            result += sign * num;
            num = 0;
            result *= pop();
            result += pop();
        }
    }
    
    return result + sign * num;
}

int main() {
    char s[1000];
    fgets(s, sizeof(s), stdin);
    s[strcspn(s, "\n")] = 0;
    int result = solution(s);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass through the string, each character processed once

✓ Linear Growth

Space Complexity

O(n)

Stack can store up to n/2 states for nested parentheses

⚡ Linearithmic Space

67.0K Views

High Frequency

~25 min Avg. Time

2.1K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Stack-Based Approach — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler