# 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));
}

}