Postfix Expressions

What is Postfix Form?


When a mathematical expression is written in postfix form, operators follow their operands; for instance, to add $3$ and $4$, one would write "$3 \, 4 +$" rather than "$3 + 4$".

If there are multiple operations, the operator is given immediately after its last operand; so the expression written "$3 − 4 + 5$" in conventional notation (which is also called infix notation) would be written "$3 \, 4 − 5 +$" in postfix form: $4$ is first subtracted from $3$, then $5$ added to it.

An advantage of postfix form is that it eliminates the need for parentheses that are required by infix notation (where operators come between their operands). While "$3 − 4 × 5$" can also be written "$3 − (4 × 5)$", that means something quite different from "$(3 − 4) × 5$". In postfix, the former could be written "$3 \, 4 \, 5 \times \, −$", which unambiguously means "$3 \, (4 \, 5 \times) \, −$" which reduces to "$3 \, 20 −$"; the latter could be written "$3 \, 4 − 5 ×$" (or $5 \, 3 \, 4 − \, \times$, if keeping similar formatting), which unambiguously means "$(3 \, 4 −) \, 5 \times$".

Postfix notation is also called Reverse Polish Notation (RPN).

Using a Stack to Evaluate a Postfix Expression


The algorithm for evaluating any postfix expression with a stack is fairly straightforward:

  • While there are input tokens left, read the next token and then do one of two things:
    • If the token is a value, push it onto the stack.
    • Otherwise, the token is an operator (operator here includes both operators and functions), so we do the following:
      • Presuming the operator takes $n$ arguments, pop the top $n$ values from the stack.
      • Apply the operator to these $n$ values.
      • Push the result(s), if any, back onto the stack.
  • When there is no more input, there should only be one value in the stack -- that value is the result of the calculation.

As an example: the infix expression "$5 + ((1 + 2) × 4) − 3$" when written in postfix is given by the following:

$$5 \, 1 \, 2 + 4 \times \, + \,3 −$$

To evaluate this postfix expression, we read the above from left-to-right. The state of the stack after each input element is examined is shown below. The "bottom" of the stack is the left-most element, while the right-most element is on the stack's "top".

Input   Action         Stack     Details
  5     push value     5
  1     push value     5 1
  2     push value     5 1 2
  +     add            5 3       pop 2, pop 1, push 1+2=3
  4     push value     5 3 4
  x     multiply       5 12      pop 4, pop 3, push 3x4=12
  +     add            17        pop 12, pop 5, push 5+12=17
  3     push value     17 3      
  -     subtract       14        pop 3, pop 17, push 17-3=14

Upon reaching the end of the input, we pop the last element on the stack.
This element is the result of evaluating the expression: 14

Java Implementation

Below is an example of how one might implement the algorithm discussed above in Java.

import java.util.Scanner;
import java.util.Stack;


public class PostFixEvaluator {
    
    public static double evaluate(String expression) {
        
        Scanner scanner = new Scanner(expression);
        
        Stack operands = new Stack();
        
        while (scanner.hasNext()) {
            
            if (scanner.hasNextDouble()) {
                operands.push(scanner.nextDouble());
            }
            else {
                double operand2 = operands.pop();
                double operand1 = operands.pop();
                String operator = scanner.next();
                
                switch (operator) {
                case "+" : operands.push(operand1 + operand2); break;
                case "-" : operands.push(operand1 - operand2); break;
                case "*" : operands.push(operand1 * operand2); break;
                case "/" : operands.push(operand1 / operand2); break;
                case "^" : operands.push(Math.pow(operand1, operand2)); break;
                }
            }
        }
        
        scanner.close();
        return operands.pop();
    }

    public static void main(String[] args) {
        System.out.println("Enter a postfix expression:");
        Scanner scanner = new Scanner(System.in);
        String inputStr = scanner.nextLine();
        scanner.close();
        System.out.println(PostFixEvaluator.evaluate(inputStr));
    }

}