657. Basic Calculator III

Given a string s representing an expression with non-negative integers, the operators +, -, *, /, parentheses, and spaces (with normal precedence), evaluate it and return the integer result. Division truncates toward zero. The input is JSON {s}.

Input: JSON {s}.

Output: Integer — the evaluated result.

Examples

Input: {"s":"2*(5+5*2)/3+(6/2+8)"}
Output: 21
Explanation: Full precedence with parentheses.

Input: {"s":"6-4/2"}
Output: 4
Explanation: Division before subtraction.

Input: {"s":"1+1"}
Output: 2
Explanation: Simple addition.

Constraints

• 1<=|s|<=10^5
• valid expression

Asked by