Basic Calculator

Hard

Description

You are given a string s that holds a maths expression. It can have digits, the signs + and -, round brackets ( and ), and spaces. Work out its value and return it.

Do not use any built-in function that evaluates a string as maths, such as eval().

A - sign can also come first, in front of a number or a bracket, to turn it negative.

Examples

Example 1:

Input: s = "7 - (2 + 3)"
Output: 2
Explanation: The bracket is 5, and 7 - 5 = 2.

Example 2:

Input: s = "10-(4-(2+1))"
Output: 9
Explanation: 2+1 = 3, then 4-3 = 1, then 10-1 = 9.

Example 3:

Input: s = "-(3+4)+10"
Output: 3
Explanation: The first "-" flips the bracket: -7 + 10 = 3.

Math
String
Stack
Recursion

Constraints

s has only digits, '+', '-', '(', ')' and spaces.
s is a correct expression.
A '+' is never used as a sign in front of a number or bracket, so "+1" and "+(2 + 3)" do not appear.
A '-' can be used that way, so "-1" and "-(2 + 3)" are allowed.
Two operators never sit side by side.
Every number and every step of the calculation fits in a signed 32-bit integer.
1 <= s.length <= 300000

Examples

3 shown

Example 1

Input

"7 - (2 + 3)"

Output

Example 2

Input

"10-(4-(2+1))"

Output

Example 3

Input

"-(3+4)+10"

Output

Opening the editor...