# Basic Calculator

Implement a basic calculator to evaluate a simple expression string.

The expression string may contain open ( and closing parentheses ), the plus + or minus sign -, non-negative integers and empty spaces .

Example 1:

```Input: "1 + 1"
Output: 2
```
Example 2:

```Input: " 2-1 + 2 "
Output: 3```
Example 3:

```Input: "(1+(4+5+2)-3)+(6+8)"
Output: 23```
Note:
• You may assume that the given expression is always valid.
• Do not use the eval built-in library function.

Solution:

class Solution {
public int calculate(String s) {
int result = 0;
int num = 0;
int sign = 1;
Deque<Integer> contextSign = new ArrayDeque<>();
contextSign.push(sign);
for (char c : s.toCharArray()) {
if (Character.isDigit(c)) {
num = num * 10 + (c - '0');
} else if (c == '+' || c == '-') {
result += sign * num;
sign = contextSign.peek() * (c == '+' ? 1 : -1);
num = 0;
} else if (c == '(') {
contextSign.push(sign);
} else if (c == ')') {
contextSign.pop();
}
}
result += sign * num;
return result;
}
}