class Solution {
    Stack<Character> op = new Stack<>();
    Stack<Integer> num = new Stack<>();
    Map<Character, Integer> map = new HashMap<>();

    public int calculate(String s) {
        int len = s.length();

        map.put('+', 1);
        map.put('-', 1);
        map.put('*', 2);
        map.put('/', 2);

        for(int i = 0; i < len; i ++ ){
            char c = s.charAt(i);
            if(c == ' ') continue;
            if(Character.isDigit(c)){
                int x = 0, j = i;
                while(j < len && Character.isDigit(s.charAt(j))) x = x * 10 + s.charAt(j ++ ) - '0';
                num.push(x);
                i = j - 1;
            } else if(c == '('){
                op.push(c);
            } else if(c == ')'){
                while(op.peek() != '(') eval();
                op.pop();
            } else if(op.isEmpty()){
                op.push(c);
            } else {
                while(!op.isEmpty() && op.peek() != '(' && map.get(op.peek()) >= map.get(c)) eval();
                op.push(c);
            }
        }

        while(op.size() > 0) eval();
        return num.peek();
    }

    public void eval(){
        int num1 = num.pop();
        int num2 = num.pop();
        char x = op.pop();
        if(x == '+') num.push(num2 + num1);
        else if(x == '-') num.push(num2 - num1);
        else if(x == '*') num.push(num2 * num1);
        else if(x == '/') num.push(num2 / num1);
    }
}