772. Basic Calculator III

Practice Basic Calculator III for free on NudgeCode: Hard, Stack pattern. Write it in Python or JavaScript, run the tests in your browser, and ask for a hint when you are stuck.

Evaluate an arithmetic expression given as a string and return its value. The expression contains non-negative integers, the operators + - * / and parentheses ( ), with no spaces. There is no unary minus. * and / bind tighter than + and -, operators of the same level go left to right, and parentheses are evaluated first. Integer division truncates toward zero, also when the left side is negative. Do not use a built-in eval.

Example

s = "6-4/2"                ->  4
s = "2*(5+5*2)/3+(6/2+8)"  ->  21
s = "2*(1-5)/3"            ->  -2   (-8 / 3 truncates to -2)

Constraints

• 1 <= s.length <= 10^4
• The expression is valid, no division by zero occurs, and every intermediate result fits in a 32-bit signed integer