Basic Calculator

Given a valid expression string s, build a basic calculator that computes and returns the expression's value.

Restriction: Do not rely on any built-in feature that interprets a string as a mathematical expression, including eval().

Examples

Example 1:

Input: s = "7 + 3"

Output: 10

Explanation: Adding 7 and 3 produces 10.

Example 2:

Input: s = " 9-4 + 1 "

Output: 6

Explanation: Evaluating 9 - 4 + 1 gives 6.

Example 3:

Input: s = "(2+(3+6+1)-4)+(5+7)"

Output: 20

Explanation: The left parenthesized portion evaluates to 8, the right portion is 12, and their sum is 20.

Constraints

• 1 <= s.length <= 3 * 10^5
• The string s contains only digits, '+', '-', '(', ')', and spaces.
• You may assume that s is a syntactically valid expression.
• '+' never appears as a unary operator, so forms such as "+1" and "+(2 + 3)" are invalid.
• '-' may act as a unary operator, as in "-1" or "-(2 + 3)".
• The input does not contain two operators next to each other.
• Each numeric value and every intermediate result fits within a signed 32-bit integer.