Basic Calculator

Hard

#0212Time: O(n) where n is the length of the input string. We process each character once.Space: O(n) where n is the length of the input string. In worst case, we might need to store all numbers and operators in the stacks.12 companies

Patterns

Math Recursion

Data structures

String Stack

Companies

ByteDance DoorDash Oracle Palo Alto Networks

Prompt

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

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

Example 1:

Input: s = "1 + 1"
Output: 2

Example 2:

Input: s = " 2-1 + 2 "
Output: 3

Example 3:

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

Constraints:

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

Approaches

2 approaches with complexity analysis and trade-offs.

We can solve this problem using two stacks - one for numbers and one for operators. We process the expression character by character and handle parentheses by evaluating sub-expressions.

Algorithm

Initialize two stacks: nums for numbers and ops for operators
Iterate through each character in the string:
- Skip spaces
- Parse complete numbers when digits are found
- Handle opening parenthesis by pushing to ops stack
- Handle closing parenthesis by evaluating sub-expression
- Handle operators by evaluating previous operations
Process remaining operations in the stack
Return final result

Walkthrough

This approach uses two stacks to evaluate the expression:

First, we initialize two stacks - nums for numbers and ops for operators
We iterate through each character in the string:
- Skip spaces
- If we find a digit, parse the complete number
- If we find an opening parenthesis '(', push it to ops stack
- If we find a closing parenthesis ')', evaluate everything until matching '('
- If we find an operator (+/-), evaluate all higher or equal precedence operations before pushing

Here's the implementation:

1public int calculate(String s) {2    Stack<Integer> nums = new Stack<>();3    Stack<Character> ops = new Stack<>();4    5    for (int i = 0; i < s.length(); i++) {6        char c = s.charAt(i);7        if (c == ' ') continue;8        9        if (Character.isDigit(c)) {10            int num = c - '0';11            while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {12                num = num * 10 + (s.charAt(i + 1) - '0');13                i++;14            }15            nums.push(num);16        } else if (c == '(') {17            ops.push(c);18        } else if (c == ')') {19            while (!ops.isEmpty() && ops.peek() != '(') {20                nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));21            }22            ops.pop(); // Remove '('23        } else if (c == '+' || c == '-') {24            while (!ops.isEmpty() && ops.peek() != '(') {25                nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));26            }27            ops.push(c);28        }29    }30    31    while (!ops.isEmpty()) {32        nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));33    }34    35    return nums.pop();36}37 38private int applyOp(char op, int b, int a) {39    switch (op) {40        case '+': return a + b;41        case '-': return a - b;42        default: return 0;43    }44}

Complexity

Time

O(n) where n is the length of the input string. We process each character once.

Space

O(n) where n is the length of the input string. In worst case, we might need to store all numbers and operators in the stacks.

Trade-offs

Pros

Easy to understand and implement
Can handle nested parentheses
Straightforward approach for basic calculator operations

Cons

Uses extra space for two stacks
Requires multiple stack operations
Not as efficient as single pass solutions

We can optimize the solution by using a single stack and keeping track of signs. This approach is more efficient as it reduces the space complexity and number of operations.

Algorithm

Initialize variables for result, current number, and sign
Iterate through each character:
- Build number for consecutive digits
- Process operators by updating result and sign
- For opening parenthesis, push current result and sign
- For closing parenthesis, evaluate sub-expression
Handle final number if exists
Return final result

Walkthrough

This approach uses a single stack and tracks the current sign:

We use a stack to store intermediate results
We maintain a currentNumber and sign variable
When we encounter operators or parentheses, we process accordingly
For parentheses, we push the current result and sign onto stack

Here's the implementation:

1public int calculate(String s) {2    Stack<Integer> stack = new Stack<>();3    int result = 0;4    int number = 0;5    int sign = 1;6    7    for (int i = 0; i < s.length(); i++) {8        char c = s.charAt(i);9        10        if (Character.isDigit(c)) {11            number = number * 10 + (c - '0');12        } else if (c == '+') {13            result += sign * number;14            number = 0;15            sign = 1;16        } else if (c == '-') {17            result += sign * number;18            number = 0;19            sign = -1;20        } else if (c == '(') {21            stack.push(result);22            stack.push(sign);23            result = 0;24            sign = 1;25        } else if (c == ')') {26            result += sign * number;27            number = 0;28            result *= stack.pop();    // sign29            result += stack.pop();    // previous result30        }31    }32    33    if (number != 0) {34        result += sign * number;35    }36    37    return result;38}

Complexity

Time

O(n) where n is the length of the input string. We process each character exactly once.

Space

O(k) where k is the maximum depth of parentheses in the expression.

Trade-offs

Pros

More efficient than two-stack approach
Uses less memory
Handles parentheses elegantly
Single pass through the input

Cons

Slightly more complex logic
Still requires a stack for parentheses handling
Needs careful handling of edge cases

Solutions

Solution

1public class Solution {2    public int Calculate(string s) {3        var stk = new Stack < int > ();4        int sign = 1;5        int n = s.Length;6        int ans = 0;7        for (int i = 0; i < n; ++i) {8            if (s[i] == ' ') {9                continue;10            }11            if (s[i] == '+') {12                sign = 1;13            } else if (s[i] == '-') {14                sign = -1;15            } else if (s[i] == '(') {16                stk.Push(ans);17                stk.Push(sign);18                ans = 0;19                sign = 1;20            } else if (s[i] == ')') {21                ans *= stk.Pop();22                ans += stk.Pop();23            } else {24                int num = 0;25                while (i < n && char.IsDigit(s[i])) {26                    num = num * 10 + s[i] - '0';27                    ++i;28                }--i;29                ans += sign * num;30            }31        }32        return ans;33    }34}

1class Solution {2public3  int calculate(String s) {4    Deque<Integer> stk = new ArrayDeque<>();5    int sign = 1;6    int ans = 0;7    int n = s.length();8    for (int i = 0; i < n; ++i) {9      char c = s.charAt(i);10      if (Character.isDigit(c)) {11        int j = i;12        int x = 0;13        while (j < n && Character.isDigit(s.charAt(j))) {14          x = x * 10 + s.charAt(j) - '0';15          j++;16        }17        ans += sign * x;18        i = j - 1;19      } else if (c == '+') {20        sign = 1;21      } else if (c == '-') {22        sign = -1;23      } else if (c == '(') {24        stk.push(ans);25        stk.push(sign);26        ans = 0;27        sign = 1;28      } else if (c == ')') {29        ans = stk.pop() * ans + stk.pop();30      }31    }32    return ans;33  }34}

1class Solution {2public:3  int calculate(string s) {4    stack<int> stk;5    int ans = 0, sign = 1;6    int n = s.size();7    for (int i = 0; i < n; ++i) {8      if (isdigit(s[i])) {9        int x = 0;10        int j = i;11        while (j < n && isdigit(s[j])) {12          x = x * 10 + (s[j] - '0');13          ++j;14        }15        ans += sign * x;16        i = j - 1;17      } else if (s[i] == '+') {18        sign = 1;19      } else if (s[i] == '-') {20        sign = -1;21      } else if (s[i] == '(') {22        stk.push(ans);23        stk.push(sign);24        ans = 0;25        sign = 1;26      } else if (s[i] == ')') {27        ans *= stk.top();28        stk.pop();29        ans += stk.top();30        stk.pop();31      }32    }33    return ans;34  }35};

1# only + and - , no * , no / class Solution : def calculate ( self , s : str ) -> int : stk = [] ans , sign = 0 , 1 i , n = 0 , len ( s ) while i < n : if s [ i ]. isdigit (): x = 0 j = i # with this while, no need to do final calculation like below solution while j < n and s [ j ]. isdigit (): x = x * 10 + int ( s [ j ]) j += 1 ans += sign * x i = j - 1 elif s [ i ] == "+" : sign = 1 elif s [ i ] == "-" : sign = - 1 elif s [ i ] == "(" : stk . append ( ans ) stk . append ( sign ) ans , sign = 0 , 1 elif s [ i ] == ")" : ans = stk . pop () * ans + stk . pop () i += 1 return ans ############# class Solution : def calculate ( self , s : str ) -> int : ans = 0 num = 0 sign = 1 stack = [ sign ] # stack[-1]: current env's sign for c in s : if c . isdigit (): num = num * 10 + int ( c ) # num = num * 10 + (ord(c) - ord('0')) => also works elif c == '(' : stack . append ( sign ) elif c == ')' : stack . pop () # pop pairing sign for this () pair elif c == '+' or c == '-' : ans += sign * num sign = ( 1 if c == '+' else - 1 ) * stack [ - 1 ] # after all + or -, the sign for current num num = 0 return ans + sign * num # final calculation

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem