Basic Calculator
Hard · Stack & Strings · Math · String · Stack · Recursion
Problem
You are given a string s holding a valid arithmetic expression. Evaluate it and return the result. You may not use any built-in function that evaluates strings as expressions, such as eval().
The expression contains non-negative integers, +, -, parentheses and spaces. + is only ever a binary operator, but - may also be unary, as in "-2" or "-(3 + 4)". Two operators never appear next to each other, and every intermediate result fits in a signed 32-bit integer.
Examples
Input: s = "7 - (3 + 2)" Output: 2
The bracket evaluates to 5, and 7 - 5 = 2.
Input: s = "-(4-6)+1" Output: 3
4 - 6 = -2, negating it gives 2, and adding 1 gives 3.
Input: s = "(1+(4+5+2)-3)+(6+8)" Output: 23
The inner bracket is 11, the first group 1 + 11 - 3 = 9, and 9 + 14 = 23.
Constraints
- 1 <= len(s) <= 3 · 10^5
- s consists of digits, '+', '-', '(', ')' and ' '
- s is a valid expression
- '+' is never used as a unary operator
- '-' may be used as a unary operator
- No two consecutive operators appear in s
- Every number and intermediate result fits in a signed 32-bit integer
Approaches
- Baseline: evaluate the innermost bracket and splice it in — time O(n²), space O(n)
Follow-up
Add * and / and each bracket level needs more state: the finished sum, the term being built and the pending operator. Or write a recursive-descent parser (expression → term → factor), which also handles any depth of nesting given an explicit stack.
Related problems
Start free on Cariara · Coding problems · System design studio
