Staff
Basic Calculator III
Given a string s representing a valid arithmetic expression, implement a basic calculator to evaluate it and return its result.
The expression may contain:
- Non-negative integers
- The binary operators
+,-,*, and/ - Opening and closing parentheses
(and) - Spaces, which should be ignored
Operator precedence follows standard arithmetic rules: parentheses first, then multiplication and division, then addition and subtraction. Integer division should truncate toward zero.
You must solve the problem without using built-in expression evaluation functions such as eval.
Example 1
Input
s = "1+1"Output
2The expression evaluates to 2 after adding 1 and 1.
Example 2
Input
s = "2*(5+5*2)/3+(6/2+8)"Output
21The parentheses and operator precedence make the expression evaluate to 21.
Constraints
- 1 <= s.length <= 10^4
- s consists of digits, '+', '-', '*', '/', '(', ')', and spaces ' '.
- s is a valid arithmetic expression.
- All intermediate results are in the range [-2^31, 2^31 - 1].
- The result is guaranteed to fit in a 32-bit signed integer.