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:

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;
    }
}