All problems

Basic Calculator

Hard · stack

A calculator receives its sum as text. Given a string s holding an arithmetic expression, return its value.

The expression is made of non-negative whole numbers, the operators + and -, round brackets and spaces. Brackets work as usual: whatever is inside them is worked out first and then treated as one number.

A - can also mean "negate". This happens when it is the first thing in the expression or comes straight after an opening bracket (ignoring spaces). It then applies to the number or bracketed group that follows it, so -(2+3) is -5 and 1-(-2) is 3. A + is never used this way.

The expression is always valid, and every value that appears while you work it out fits in a signed 32-bit integer.

Examples

Example 1

Input: s = "1 + 1"

Output: 2

Example 2

Input: s = " 2-1 + 2 "

Output: 3

Without brackets, work from left to right: 2 - 1 is 1, then 1 + 2 is 3.

Example 3

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

Output: 23

The inner bracket is 11, so the first group is 1 + 11 - 3 = 9, the second is 14, and the total is 23.

Example 4

Input: s = "-(2+3)+(-4)"

Output: -9

The leading minus negates the bracket, giving -5, and the second bracket is -4.

Constraints

• 1 <= len(s) <= 3 * 10^5
• s contains digits, spaces and the characters '+', '-', '(' and ')'.
• s is a valid expression, and no number is split by a space.
• Brackets are nested at most 500 levels deep.
• Every number is between 0 and 2^31 - 1, and every value that appears during evaluation fits in a signed 32-bit integer.