408. Pocket Calculator
A pocket calculator app receives a typed line such as "7 - (2 + (9 - 4))" and has to display its value. The line holds non-negative whole numbers, the symbols + and -, round brackets and any number of spaces. There is no multiplication or division, but a minus sign can also negate: it may stand at the very start, right after an opening bracket or right after another operator, and it flips the sign of the number or bracketed group that follows it.
Return the value of expression. The line is always well formed with balanced brackets, and each number and each intermediate result fits in a signed 32-bit integer. Brackets can be nested thousands of levels deep, so a solution that recurses once per bracket level may overflow the call stack; a stack of saved results is a safer idea. The line has at most 30,000 characters.
Example 1
- Input:
- expression = "12 - (4 + (7 - 10)) - -3"
- Output:
- 14
- Explanation:
The inner bracket 7 - 10 is -3, then 4 + -3 is 1, then 12 - 1 is 11, and subtracting a negated 3 gives 11 + 3 = 14.
Example 2
- Input:
- expression = "-(8 - 3) + (2 - (-6 + 1))"
- Output:
- 2
- Explanation:
The first group is negated to -5. In the second group -6 + 1 is -5 and 2 - (-5) is 7, so the total is -5 + 7 = 2.
Constraints
1 ≤ expression.length ≤ 3 * 104
The characters are digits, +, -, (, ) and spaces.
The expression is valid; numbers have no leading zeros.
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(n)
- Space
- O(n)