Basic Calculator

Statement

Given a string containing an arithmetic expression, implement a basic calculator that evaluates the expression string. The expression string can contain integer numeric values and should be able to handle the “+” and “-” operators, as well as “()” parentheses.

Constraints:

Let s be the expression string. We can assume the following constraints:

• $1 \leq$ s.length $\leq 3 \times 10^{3}$
• s consists of digits, “+”, “-”, “(”, and “)”.
• s represents a valid expression.
• “+” is not used as a unary operation ( $+1$ and $+(2 + 3)$ are invalid).
• “-” could be used as a unary operation ($-1$ and $-(2 + 3)$ are valid).
• There will be no two consecutive operators in the input.
• Every number and running calculation will fit in a signed 32-bit integer.

Examples