Start practising

Basic Calculator

Hard Stack Stack Basics Original on LeetCode

Basic Calculator is a hard stack problem solved with the stack basics pattern. The best approach, optimal (stack of saved results and signs), runs in O(n) time and O(n) space.

Problem

Evaluate an expression string containing non-negative integers, +, -, brackets and spaces. A - can also be unary, as in -2 or -(1 + 2). Do not use a built-in eval.

Examples

Example 1

Input
s = " 2 - (5 - 6) "
Output
3

Example 2

Input
s = "-(3 + (4 + 5))"
Output
-12
Why
A unary minus in front of a bracket flips everything inside.

Constraints

  • 1 <= s.length <= 3 * 10^5
  • Digits, + - ( ) and spaces. No * or /.
  • No library eval.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Optimal (stack of saved results and signs)O(n)O(n)

1Optimal (stack of saved results and signs)

TimeO(n)
SpaceO(n)The stack grows with nesting depth.

Scan left to right keeping result, the current number and the sign (+1 or -1) for the next number. On '(' push result and sign, then start fresh inside. On ')' finish the inner result, multiply by the saved sign and add the saved result.

  1. Digit: number = number * 10 + d.
  2. + or -: result += sign * number; number = 0; sign = ±1.
  3. (: push result, push sign; result = 0; sign = 1.
  4. ): result += sign * number; number = 0; result = result * pop() + pop().
  5. At the end return result + sign * number.
Java
class Solution {
    public int calculate(String s) {
        Deque<Integer> st = new ArrayDeque<>();
        int result = 0, number = 0, sign = 1;
        for (char c : s.toCharArray()) {
            if (Character.isDigit(c)) {
                number = number * 10 + (c - '0');
            } else if (c == '+' || c == '-') {
                result += sign * number;
                number = 0;
                sign = c == '+' ? 1 : -1;
            } else if (c == '(') {
                st.push(result);
                st.push(sign);
                result = 0;
                sign = 1;
            } else if (c == ')') {
                result += sign * number;
                number = 0;
                result = result * st.pop() + st.pop();
            }
        }
        return result + sign * number;
    }
}

Edge cases to test

  • Unary minus: -2 or -(...)
  • Multi-digit numbers
  • Nested brackets

Hints

Hint 1

With only + and -, each number is simply added with a sign. What decides that sign?

Hint 2

On '(' save the current result and sign; on ')' combine.

FAQ

What is the best time complexity for Basic Calculator?

Optimal (stack of saved results and signs) runs in O(n) time and O(n) extra space.

Which pattern does Basic Calculator use?

It is a stack problem that uses the stack basics pattern. Other problems with the same pattern: Valid Parentheses, Baseball Game, Asteroid Collision.

Which edge cases should I test for Basic Calculator?

Unary minus: -2 or -(...); Multi-digit numbers; Nested brackets.