233. Basic Calculator II

Given a string s representing an arithmetic expression with non-negative integers and the operators +, -, *, / (and spaces), evaluate it and return the integer result. Multiplication and division have higher precedence; integer division truncates toward zero.

Input: A quoted expression string.

Output: Integer — the evaluated result.

Examples

Input: "3+2*2"
Output: 7
Explanation: 2*2=4, +3 = 7.

Input: "3/2"
Output: 1
Explanation: Truncated division.

Input: " 3+5 / 2 "
Output: 5
Explanation: 5/2=2, +3 = 5.

Constraints

• 1<=s.length<=3*10^5
• valid expression
• no parentheses

Asked by