Given a string s holding a valid expression, evaluate it and return the result. It can contain non-negative integers, +, -, parentheses and spaces, and a - can also be unary, as in -(2 + 3).
Don't use a built-in function that evaluates strings as code, like eval.
Examples
Example 1
- Input
- s = "1 + 1"
- Output
- 2
Example 2
- Input
- s = " 2-1 + 2 "
- Output
- 3
Example 3
- Input
- s = "(1+(4+5+2)-3)+(6+8)"
- Output
- 23
Constraints
1 <= s.length <= 3 * 10^5scontains digits,+,-,(,)and spaces, and is always a valid expression.- Every number and every intermediate result fits in a 32-bit signed integer.