224. Basic Calculator

Practice Basic Calculator 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, +, -, parentheses ( ) and spaces. - can also be unary ("-2+1", "-(3+4)"), but + is never unary. Do not use a built-in eval.

Example

s = "1 + 1"                ->  2
s = " 2-1 + 2 "            ->  3
s = "(1+(4+5+2)-3)+(6+8)"  ->  23

Constraints

• 1 <= s.length <= 3 * 10^5
• The expression is valid; every number and every intermediate result fits in a 32-bit signed integer