The standard notation used to represent mathematical expressions is called infix notation. You should be very familiar with it already because it is almost exclusively used in books and thought in schools. Just to be clear, the typical example of infix expression is:

(2 + 3) - 7 / 9

However, there exists two other yet significantly less popular notations called prefix and postfix. In this article we will concentrate on the later and describe what it is and how to evaluate it using computer.

Postfix notation

Postfix notation (also known as Reverse Polish Notation or RPN in short) is a mathematical notation in which operators follow all of its operands. It is different from infix notation in which operators are placed between its operands. The previously mentioned infix expression can be represented using postfix notation like this:

2 3 + 7 9 / -

To evaluate this expression we take two first numbers 2 and 3, add them and remember the result; then we take the next two numbers 7 and 9, divide them and remember the result. At last we take the two remembered values and we subtract them to obtain the final result.

While postfix notation may seem less natural and straightforward, it has several advantages which made it popular in computing. The main reason is that postfix expressions are generally easier to calculate on computers than the equivalent infix expressions and do not require any brackets to define the order of operations (assuming that every operator has fixed number of operands). Additionally, the ease of processing results in significantly simpler and more efficient algorithms. This made postfix notation very popular in representing intermediate results of computations.

Algorithm

The algorithm to evaluate any postfix expression is based on stack and is pretty simple:

1. Initialize empty stack
2. For every token in the postfix expression (scanned from left to right):
   1. If the token is an operand (number), push it on the stack
   2. Otherwise, if the token is an operator (or function):
      1. Check if the stack contains the sufficient number of values (usually two) for given operator
      2. If there are not enough values, finish the algorithm with an error
      3. Pop the appropriate number of values from the stack
      4. Evaluate the operator using the popped values and push the single result on the stack
3. If the stack contains only one value, return it as a final result of the calculation
4. Otherwise, finish the algorithm with an error

Example

As an example we will try to evaluate the following postfix expression:

2 3 4 + * 6 -

which can be represented in infix notation like this:

2 * (3 + 4) - 6

The exact steps of the algorithm are put in the table below:

The contents of the stack in the Stack contents … column is represented from left to right with the rightmost values being on the top of the stack. When there are no more tokens in the input, the contents of the stack is checked. If there is only one value, it is the result of the calculation. If there are no values or if there are many, the passed input expression was not a valid postfix expression.

Source code

The algorithm can be easily implemented in Java using LinkedList as a stack implementation:

package com.example.evalpostfix;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

public class PostfixEvaluator {

    private Deque<Double> args;

    public PostfixEvaluator() {
        args = new LinkedList<>();
    }

    public double evaluate(String expr) {
        args.clear();
        try (Scanner scanner = new Scanner(expr)) {
            while (scanner.hasNext()) {
                String token = scanner.next();
                processToken(token);
            }
        }

        if (args.size() == 1) {
            return args.pop();
        } else {
            throw new IllegalArgumentException("Invalid number of operators");
        }
    }

    private void processToken(String token) {
        switch (token) {
            case "+":
                addArgs();
                break;
            case "-":
                subArgs();
                break;
            case "*":
                mulArgs();
                break;
            case "/":
                divArgs();
                break;
            default:
                try {
                    double arg = Double.parseDouble(token);
                    args.push(arg);
                } catch (NumberFormatException e) {
                    throw new IllegalArgumentException("Invalid number: " + token, e);
                }
        }
    }

    private void addArgs() {
        checkArgumentsSize();
        double arg2 = args.pop();
        double arg1 = args.pop();
        args.push(arg1 + arg2);
    }

    private void subArgs() {
        checkArgumentsSize();
        double arg2 = args.pop();
        double arg1 = args.pop();
        args.push(arg1 - arg2);
    }

    private void mulArgs() {
        checkArgumentsSize();
        double arg2 = args.pop();
        double arg1 = args.pop();
        args.push(arg1 * arg2);
    }

    private void divArgs() {
        checkArgumentsSize();
        double arg2 = args.pop();
        double arg1 = args.pop();
        args.push(arg1 / arg2);
    }

    private void checkArgumentsSize() {
        if (args.size() < 2) {
            throw new IllegalArgumentException("Not enough parameters for operation");
        }
    }
}

The code allows any double value as an operand and can be easily extended to support additional binary operators (e.g. modulo, power), unary operations (e.g. factorial, square root) or functions (e.g. logarithm, trigonometric functions).

Conclusion

Evaluating postfix expressions is a very simple example presenting usefulness of stack in evaluating mathematical expressions. If you are interested in evaluating infix expressions, you can check Shunting-yard algorithm.

You can find the complete source code with tests at GitHub.