395. Full Calculator
A tiny spreadsheet cell accepts arithmetic written as text: non-negative integers, the operators +, -, *, /, round brackets and optional blank spaces. A minus sign may also be used as a prefix on a number or on a bracketed part, as in -(2+3) or 4*-5. Multiplication and division bind tighter than addition and subtraction, operators of equal rank are applied left to right, and a prefix minus binds tightest of all.
Given the string expression, evaluate it and return the result. Division discards the fractional part (it truncates toward zero, so -7/2 is -3). The expression is valid, never divides by zero, and every intermediate value fits in a 32-bit signed integer. You may not call any built-in expression evaluator, and the text can be deeply nested.
Example 1
- Input:
- expression = "9 - (-4 + 1) * 6 / -3"
- Output:
- 3
- Explanation:
-4 + 1 is -3, then -3 * 6 is -18, then -18 / -3 is 6, and 9 - 6 is 3.
Example 2
- Input:
- expression = "-(17 + 4) / 5 * 3"
- Output:
- -12
- Explanation:
The prefix minus gives -21, then -21 / 5 truncates to -4, and -4 * 3 is -12.
Constraints
1 ≤ expression.length ≤ 4 * 104
Characters are digits, + - * /, ( ) and spaces; numbers have no leading zeros unless they are exactly 0.
No division by zero; all numbers and intermediate results fit in a signed 32-bit integer.
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)