Easy Solution Using Two Stacks


  • 0
    H
    public class Solution {
        public int calculate(String s) {
            Stack<Character> ops = new Stack<>();
            Stack<Integer> values = new Stack<>();
            ops.push('+');
            values.push(0);
            int i = 0;
            while (i < s.length()) {
                char c = s.charAt(i);
                if (c >= '0' && c <= '9') {
                    // num
                    int j = i;
                    while (j < s.length() && s.charAt(j) >= '0' && s.charAt(j) <= '9') ++j;
                    int v = Integer.parseInt(s.substring(i, j));
                    if (ops.peek() == '(') {
                        values.push(v);
                    } else {
                        char op = ops.pop();
                        if (op == '+') {
                            values.push(values.pop() + v);
                        } else {
                            values.push(values.pop() - v);
                        }
                    }
                    i = j;
                } else if (c == '(') {
                    ops.push('(');
                    ++i;
                } else if (c == ')') {
                    ops.pop();
                    int v = values.pop();
                    char op = ops.pop();
                    if (op == '+') {
                        values.push(values.pop() + v);
                    } else {
                        values.push(values.pop() - v);
                    }
                    ++i;
                } else if (c == ' ') {
                    ++i;
                } else {
                    ops.push(c);
                    ++i;
                }
            }
            return values.peek();
        }
    

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.