4.3.3.1 - Reverse Polish and infix expressions (Java)

Infix and Reverse Polish forms

The position of an operator determines how an expression records its operands and evaluation order.

Treat each sub-expression as a unit. Convert $(A+B)\times C$ by first converting the left operand to A B +, leaving C as the right operand, then placing * after both: A B + C *. In contrast, $A+B\times C$ is A B C * + because multiplication is grouped first. Spaces separate tokens; a multi-digit number such as 12 is one operand, not 1 then 2.

RPN needs no brackets to show grouping: the token order specifies exactly when operands are combined. It does not mean that all operators have the same precedence in the original infix expression. When converting, honour its brackets and precedence before writing postfix tokens. For $(A-B)/(C+D)$, the result is A B - C D + /. Operators such as subtraction/division are not commutative, so reversing their operands changes the result.

Evaluating with a stack

A stack evaluates RPN by holding values until an operator has both of its operands available.

Read left to right. Push a number. At a binary operator, pop the right operand first, then the left, calculate left operator right, and push the result. A valid complete expression finishes with exactly one value. For 12 3 2 * -, the stack below is written bottom-to-top:

This Java method assumes a valid token array containing integer operands and +, -, *. Methods belong inside a class with import java.util.*;. push and pop use the front of the deque as the top; the display above remains bottom-to-top.

static int evaluate(String[] tokens) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (String token : tokens) {
        if (token.equals("+") || token.equals("-") || token.equals("*")) {
            int right = stack.pop();
            int left = stack.pop();
            int result;
            if (token.equals("+")) result = left + right;
            else if (token.equals("-")) result = left - right;
            else result = left * right;
            stack.push(result);
        } else {
            stack.push(Integer.parseInt(token));
        }
    }
    return stack.pop();
}

For the valid tokens {"5","2","-","4","*"}, predict 12: the subtraction pushes 3, then multiplication pushes 12. To support integer division, recognise "/" too and compute left / right. Java integer division truncates towards zero; any division task must specify non-zero divisors and whether integer arithmetic is intended.