Scale Engineer

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
MathRecursion
Data structures
StringStack
Companies
ByteDanceDoorDashOraclePalo 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 * 105
  • 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

  1. Initialize two stacks: nums for numbers and ops for operators
  2. 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
  3. Process remaining operations in the stack
  4. Return final result

Walkthrough

This approach uses two stacks to evaluate the expression:

  1. First, we initialize two stacks - nums for numbers and ops for operators
  2. 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:

public int calculate(String s) {    Stack<Integer> nums = new Stack<>();    Stack<Character> ops = new Stack<>();        for (int i = 0; i < s.length(); i++) {        char c = s.charAt(i);        if (c == ' ') continue;                if (Character.isDigit(c)) {            int num = c - '0';            while (i + 1 < s.length() && Character.isDigit(s.charAt(i + 1))) {                num = num * 10 + (s.charAt(i + 1) - '0');                i++;            }            nums.push(num);        } else if (c == '(') {            ops.push(c);        } else if (c == ')') {            while (!ops.isEmpty() && ops.peek() != '(') {                nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));            }            ops.pop(); // Remove '('        } else if (c == '+' || c == '-') {            while (!ops.isEmpty() && ops.peek() != '(') {                nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));            }            ops.push(c);        }    }        while (!ops.isEmpty()) {        nums.push(applyOp(ops.pop(), nums.pop(), nums.pop()));    }        return nums.pop();} private int applyOp(char op, int b, int a) {    switch (op) {        case '+': return a + b;        case '-': return a - b;        default: return 0;    }}

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

Solutions

public class Solution {    public int Calculate(string s) {        var stk = new Stack < int > ();        int sign = 1;        int n = s.Length;        int ans = 0;        for (int i = 0; i < n; ++i) {            if (s[i] == ' ') {                continue;            }            if (s[i] == '+') {                sign = 1;            } else if (s[i] == '-') {                sign = -1;            } else if (s[i] == '(') {                stk.Push(ans);                stk.Push(sign);                ans = 0;                sign = 1;            } else if (s[i] == ')') {                ans *= stk.Pop();                ans += stk.Pop();            } else {                int num = 0;                while (i < n && char.IsDigit(s[i])) {                    num = num * 10 + s[i] - '0';                    ++i;                }--i;                ans += sign * num;            }        }        return ans;    }}

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 →

Next problem