Loading problem…
Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers, `'+'`, `'-'`, `'*'`, `'/'` operators, and open `'('` and closing parentheses `')'`. The integer division should **truncate toward zero**. You may assume that the given expression is always valid. All intermediate results will be in the range of `[-2^31, 2^31 - 1]`.
Example 1
Input: s = 1+1
Output: 2
Explanation: There is a single addition: 1 + 1 = 2.
Example 2
Input: s = 6-4/2
Output: 4
Explanation: Division is done before subtraction: 4 / 2 = 2, then 6 - 2 = 4.
Example 3
Input: s = 2*(5+5*2)/3+(6/2+8)
Output: 21
Explanation: Inside the first parentheses 5 + 5 * 2 = 15, so 2 * 15 / 3 = 30 / 3 = 10. Inside the second, 6 / 2 + 8 = 3 + 8 = 11. The total is 10 + 11 = 21.
Scan the expression maintaining a stack of terms. Apply the pending operator when the next operator (or end) is reached: push for +/-, and combine with the top for * and / (which bind tighter). A '(' recurses to evaluate the sub-expression as a single number.
Run checks all cases above. Submit evaluates all test cases.