Basic Calculator III
Hard · Stack & Strings · Math · String · Stack · Recursion
Problem
Evaluate an arithmetic expression given as a string s and return its value. Do not use any built-in function that evaluates strings as expressions, such as eval().
The expression contains non-negative integers, the operators +, -, * and /, and brackets ( and ). Multiplication and division bind more tightly than addition and subtraction, and operators of the same precedence apply left to right. Integer division truncates toward zero.
The expression is always valid, has no spaces, never divides by zero, and every intermediate result lies in [-2^31, 2^31 - 1].
Examples
Input: s = "3+4*2" Output: 11
Multiplication comes first, so this is 3 + 8.
Input: s = "(7-2)*(8/3)" Output: 10
The brackets give 5 and 2 (8 / 3 truncated), and 5 · 2 = 10.
Input: s = "10/(1+3)-4" Output: -2
10 / 4 truncates to 2, and 2 - 4 = -2.
Constraints
- 1 <= len(s) <= 10^4
- s consists of digits, +, -, *, /, ( and )
- s is a valid expression
Approaches
- Baseline: recursion that rescans for each closing bracket — time O(n · d) for nesting depth d, O(n²) at worst, space O(n)
Follow-up
With unary minus (-(2+3) or 2*-3) the scanner must tell a sign from a subtraction by what came before it: an operator, ( or the start. Another direction: the same stack of levels scores bracket strings and counts atoms in chemical formulas, the two use cases below.
Related problems
Start free on Cariara · Coding problems · System design studio
