Evaluation of Postfix expression

The problem, simply

In a postfix sentence, each sign comes right after the two things it works on. So 3 4 + means 3 + 4, and 5 1 2 + 4 * + 3 - means 5 + (1 + 2) * 4 - 3.

You get the pieces as a list of strings, numbers and the signs + - * /. Work out the value. Division keeps only the whole part, cutting toward zero. You may assume the sentence is valid.

The nice thing about postfix: there are no brackets and no "times before plus" rules. The order of the pieces already says everything.

A story to remember it

Picture it

Examples

Way 1: the simple way

Keep the pieces in a list. Find the first sign. The two pieces right before it are its numbers. Replace those three pieces with the result. Repeat until one piece is left.

1. Find the first index k where the piece is a sign.
2. Work out list[k - 2] op list[k - 1].
3. Remove the three pieces and put the result at k - 2.

class Solution {
    public int evalRPN(String[] tokens) {
        List<String> list = new ArrayList<>(Arrays.asList(tokens));
        while (list.size() > 1) {
            int k = 0;
            while (!isSign(list.get(k))) k++;                // first sign
            int a = Integer.parseInt(list.get(k - 2));
            int b = Integer.parseInt(list.get(k - 1));
            int r = apply(a, b, list.get(k));
            list.remove(k);                                  // remove the sign
            list.remove(k - 1);                              // and b
            list.set(k - 2, String.valueOf(r));              // a becomes the result
        }
        return Integer.parseInt(list.get(0));
    }

    private boolean isSign(String t) {
        return t.equals("+") || t.equals("-") || t.equals("*") || t.equals("/");
    }

    private int apply(int a, int b, String op) {
        switch (op) {
            case "+": return a + b;
            case "-": return a - b;
            case "*": return a * b;
            default:  return a / b;
        }
    }
}

How long it takes: each round searches the list and removes from the middle, which costs O(n). There can be n / 2 rounds, so O(n^2). Extra room: the list copy, O(n).

Way 2: the clever way

Keep a pile of numbers, a stack.

1. Read the pieces left to right.
2. A number: push it.
3. A sign: pop b, then pop a. Push a op b.
4. At the end, the pile holds one number. Return it.

Why does this work? In postfix, the two things a sign needs are always the two most recent results. The top of a stack is exactly "most recent".

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> pile = new ArrayDeque<>();
        for (String t : tokens) {
            switch (t) {
                case "+": pile.push(pile.pop() + pile.pop()); break;
                case "*": pile.push(pile.pop() * pile.pop()); break;
                case "-": {
                    int b = pile.pop(), a = pile.pop();   // b is on top
                    pile.push(a - b);
                    break;
                }
                case "/": {
                    int b = pile.pop(), a = pile.pop();
                    pile.push(a / b);
                    break;
                }
                default: pile.push(Integer.parseInt(t));  // a number, maybe negative
            }
        }
        return pile.pop();
    }
}

How long it takes: one push or two pops and a push per piece, O(n). Extra room: the pile holds at most about n / 2 numbers, O(n).

Watch out for

• A piece like "-3" is a number. Compare the whole piece with "-", not its first character.
• Read multi-digit numbers whole. If the input is a single string, split on spaces first.
• Division by zero is not possible in valid input, but say how you would handle it.
• If the pile has more than one number at the end, or too few when a sign arrives, the input was not valid postfix.

What interviewers ask next

• Evaluate prefix instead, like - + 5 * + 1 2 4 3. Read right to left with the same pile, and now the first pop is a and the second is b.
• Turn a normal sentence into postfix. Use a pile of signs: write numbers out right away, and before pushing a sign, write out every sign on top that is at least as strong. This is the shunting yard method.
• Build the expression tree. Push leaf nodes for numbers. For a sign, pop two nodes and make them its children.
• Why do calculators and the Java virtual machine like postfix? No brackets and no precedence rules, so a simple stack machine can run it in one pass.
• Can you do it without a stack? Use recursion from the end of the list: the last piece is the root sign, and its right and left parts come before it. It still uses the call stack.

Remember this

Grown-up words: the snack pile is a stack, the sentence with signs after their numbers is postfix or Reverse Polish Notation, the two numbers a sign uses are its operands, and turning normal math into postfix is the shunting yard algorithm.