题目描述：

Given a string s representing an expression, implement a basic calculator to evaluate it.

Example 1:

Input: s = “1 + 1”
Output: 2

Example 2:

Input: s = " 2-1 + 2 "
Output: 3

Example 3:

Input: s = " 2-1 + 2 "
Output: 3

Constraints:

1 <= s.length <= 3 * 10⁵
s consists of digits, ‘+’, ‘-’, ‘(’, ‘)’, and ’ '.
s represents a valid expression.

Time complexity: O(n)

class Solution {
    public int calculate(String s) {
        Stack<Integer> stack = new Stack<>();
        int res = 0;
        int operand = 0;
        int sign = 1;  // 1 means positive, -1 means negative
        for(int i = 0; i < s.length(); i++){
            char ch = s.charAt(i);
            if (Character.isDigit(ch)) {
                operand = operand*10+(int) (ch - '0');
            }else if(ch == '+'){
                res += sign*operand;
                operand = 0;
                sign = 1;
            }else if(ch == '-'){
                res += sign*operand;
                operand = 0;
                sign = -1;
            }else if (ch == '(') {
                stack.push(res);
                stack.push(sign);
                sign = 1;
                res = 0;
            }else if (ch == ')') {
                res += sign*operand;
                res *= stack.pop();
                res += stack.pop();
                operand = 0;
                
            }
        }
        return res+(sign*operand);
    }
}