Arithmetic Expression evaluation

The problem, simply

You get a math sentence as a string, like "3+2*(4-1)-5". It has whole numbers that are zero or more, the signs + - * /, brackets, and maybe spaces. Work out its value.

Follow the school rules: brackets first, then * and /, then + and -. Signs of the same strength go left to right. Division keeps only the whole part, so 5 / 2 is 2. You may assume the sentence is valid.

A story to remember it

Picture it

Examples

Way 1: the simple way

Do it like you would on paper. Find the innermost pair of brackets, work out what is inside, and write the answer in place of the brackets. Repeat until there are no brackets. Then work out the flat sentence that is left.

To work out a flat sentence with no brackets, read it left to right with one pile:

1. Remember the last sign seen, starting with +.
2. After reading each number: if the last sign was +, push the number. If -, push minus the number. If * or /, pop the top, combine it with the number, and push the result.
3. At the end, add up the pile.

class Solution {
    public int calculate(String s) {
        s = s.replace(" ", "");
        while (s.indexOf('(') >= 0) {
            int close = s.indexOf(')');              // first closing bracket
            int open = s.lastIndexOf('(', close);    // its partner: innermost pair
            long inside = flat(s.substring(open + 1, close));
            s = s.substring(0, open) + inside + s.substring(close + 1);
        }
        return (int) flat(s);
    }

    // A sentence with no brackets. A '-' where a number should start is a sign.
    private long flat(String s) {
        Deque<Long> pile = new ArrayDeque<>();
        char op = '+';
        int i = 0, n = s.length();
        while (i < n) {
            boolean neg = false;
            if (s.charAt(i) == '-') { neg = true; i++; }
            long num = 0;
            while (i < n && Character.isDigit(s.charAt(i))) {
                num = num * 10 + (s.charAt(i++) - '0');
            }
            if (neg) num = -num;
            if (op == '+') pile.push(num);
            else if (op == '-') pile.push(-num);
            else if (op == '*') pile.push(pile.pop() * num);
            else pile.push(pile.pop() / num);
            if (i < n) op = s.charAt(i++);
        }
        long sum = 0;
        for (long v : pile) sum += v;
        return sum;
    }
}

How long it takes: each pair of brackets makes us rebuild and reread the string, so with n / 2 nested pairs that is O(n^2). Extra room: the new strings and the pile, O(n).

Way 2: the clever way

Read the string once with two piles: a number pile and a sign pile. This is Dijkstra's two stack method.

1. A number: read all its digits and push it on the number pile.
2. (: push it on the sign pile. It blocks the signs below it.
3. ): cook signs from the top until you reach (, then throw the ( away.
4. A sign + - * /: while the top sign is not ( and is at least as strong, cook it. Then push the new sign.
5. At the end, cook every sign left.

To cook: pop sign op, pop b, then pop a, and push a op b. The order matters for - and /.

class Solution {
    public int calculate(String s) {
        Deque<Integer> nums = new ArrayDeque<>();
        Deque<Character> ops = new ArrayDeque<>();
        int i = 0, n = s.length();
        while (i < n) {
            char c = s.charAt(i);
            if (c == ' ') { i++; continue; }
            if (Character.isDigit(c)) {
                int num = 0;
                while (i < n && Character.isDigit(s.charAt(i))) {
                    num = num * 10 + (s.charAt(i++) - '0');   // read all digits
                }
                nums.push(num);
                continue;
            }
            if (c == '(') {
                ops.push(c);
            } else if (c == ')') {
                while (ops.peek() != '(') cook(nums, ops);
                ops.pop();                                    // throw away the (
            } else {
                while (!ops.isEmpty() && ops.peek() != '(' && strength(ops.peek()) >= strength(c)) {
                    cook(nums, ops);                          // older, stronger sign first
                }
                ops.push(c);
            }
            i++;
        }
        while (!ops.isEmpty()) cook(nums, ops);
        return nums.pop();
    }

    private int strength(char op) {
        return (op == '*' || op == '/') ? 2 : 1;
    }

    private void cook(Deque<Integer> nums, Deque<Character> ops) {
        char op = ops.pop();
        int b = nums.pop(), a = nums.pop();   // b was pushed last
        if (op == '+') nums.push(a + b);
        else if (op == '-') nums.push(a - b);
        else if (op == '*') nums.push(a * b);
        else nums.push(a / b);
    }
}

How long it takes: every number and every sign is pushed once and popped once, O(n). Extra room: the two piles, O(n) in the worst case, for example many open brackets.

Watch out for

• Pop b first, then a. a - b and a / b care about order.
• Read every digit of a number. 12 is one number, not 1 and 2.
• Stop cooking at ( when a sign arrives. A bracket must protect what is under it.
• Unary minus, as in -3+5 or 2*(-1), is not handled here. Push a 0 before a - that starts the sentence or follows (, and it works.
• Java's / cuts toward zero, so -7 / 2 is -3. Say so if the interviewer expects floor.

What interviewers ask next

• Only +, - and brackets (LeetCode 224). Keep a running total and a sign. On (, push the total and the sign, start fresh; on ), pop them and combine. No sign pile needed.
• Only + - * / and no brackets (LeetCode 227). Use the one pile flat method from Way 1, O(n) with one pass.
• Add ^ for powers. It is stronger than * and goes right to left, so cook only when the top is strictly stronger.
• Turn the sentence into postfix (Reverse Polish) first. The same sign pile does it: instead of cooking, write the sign to the output. Then evaluate the postfix with one number pile.
• Build an expression tree instead of a number. "Cooking" makes a node with a and b as children.

Remember this

Grown-up words: the math sentence is an infix expression, sign strength is operator precedence, left to right for equal strength is left associativity, the two piles are the operand stack and the operator stack, and the method is Dijkstra's two stack algorithm, close cousin of the shunting yard algorithm.