If you have been dealing with mathematical expressions, you might have heard of infix, prefix and postfix notation. If you have never heard of these kind of ways to write mathematical expressions, don’t be afraid. You already use one of them on a day-to-day basis. We’ll come back to which one later.
A short description of these kind of notations are as follows:

Infix, prefix and postfix notation are three equivalent ways of writing mathematical expressions. Despite being equivalent, they are expressed (written) in different ways.

If you already know the details, you can jump straight to the Java implementation.

Infix notation

We start off by describing infix notation, which in my opinion is the most easily understood notation of the three.
The infix notation is the notation you use in your daily life, whenever you want to write a mathematical expression / equation.  Let’s say you want to add a few numbers together, namely 2, 3 and 6. You would of course write it like this (I hope…):

Infix notation: 2 + 3 + 6

Another example of a mathematical expression with infix notation is:

Infix notation: 1 + 2 * 3⁴

This would also be evaluated the usual way. First, we take 3⁴ = 81, then 2 * 81 = 162, then 1 + 162 = 163. As you all see, this is the usual way of evaluating mathematical expressions. Note that 3⁴ is the equivalent of 3^4. This brings us to a formal definition of infix notation:

When using infix notation to write mathematical expressions, the operators (+, – etc..) are written between the operands.

Note that you can’t simply evaluate an infix expression from left to right – the normal rules for operator precedence applies. For example, in an equation without parentheses, we perform multiplication before addition – this is not new, and something we’re all familiar with.

 Prefix notation

When using prefix notation, the operators are written before their operands. The use of prefix notation is best described with an example. Assume you want to convert the infix expression 1 * ( 2 + 3 ) / 4 to prefix.

Infix notation: 1 * ( 2 + 3 ) / 4

Prefix notation: / * 1 + 2 3 4

So, how did we end up with this completely different expression? Let’s take it step by step. Note that when converting from infix to prefix, we read the expression from right to left, and use a stack to memorize the operands we have read. The basis for the algorithm is:

  • Reverse the infix expression.
  • If an operand is encountered, output it immediately.
  • An operator is encountered. Output all operators on the stack that has higher precedence than the operator read.
  • Reached end of equation, pop and output everything on the stack.

The step by step conversion of the equation above is described below. Remember that we start by outputting at the end of the prefix expression. In other words, the first operand we read will be the last operand in the prefix expression.

  • Reversing the infix expression: 4 /  ) 3 + 2 ( * 1
  • Reading ‘4’, immediately output 4. Output: 4, Stack: Empty
  • Reading ‘/’, pushing it to the stack. Output: 4, Stack: /
  • Reading ‘)’. Push it to the stack. Output: 4, Stack: ) /
  • Reading ‘3’. Immediately output. Output: 3 4, Stack: ) /
  • Reading ‘+’. Push it to the stack, since another a closing parenthesis hasn’t been read. Output: 3 4, Stack: + ) /
  • Reading ‘2’. Output: 2 3 4, Stack: + ) /
  • Reading ‘(‘. This is a closing parenthesis. Output every operator in between the parenthesis. Output: + 2 3 4, Stack: /
  • Reading ‘*’. Same precedence as the current on the stack. Push to stack. Output: + 2 3 4, Stack: * /
  • Reading ‘1’. Output: 1 + 2 3 4, Stack: * /
  • Reached the end of the equation. Output the rest on the stack. Result: / * 1 + 2 3 4

Postfix notation

With postfix notation, the operators are written after their operands. As with prefix, the use of postfix notation is also best described through an example. We continue with the same infix expression as above.

Infix notation: 1 * (2 + 3) / 4

Postfix notation: 1 2 3 + * 4 /

The basis for the algorithm to convert infix to postfix is:

  • Read the infix expression from left to right.
  • If an operand is encountered, output it immediately.
  • If an operator is encountered, there is two different scenarios. If the operator scanned has a higher precedence than the current operator on the stack, we push it to the stack. If the operator has lower precedence, we pop the stack until the current operator has less or equal precedence as the operator on top of the stack.
  • Reached end of equation, pop and output everything on the stack.

To be more concrete, the exact steps performed in the conversion from infix to postfix for the equation 1 * (2 + 3) / 4 is:

  • Reading ‘1’. Output: 1
  • Reading ‘*’. Pushing it to the stack. Output: 1, Stack: *
  • Reading ‘(‘. Pushing. Output: 1, Stack: * (
  • Reading ‘2’. Output: 1 2, Stack: * (
  • Reading ‘+’. Output: 1 2, Stack: * ( +
  • Reading ‘3’. Output: 1 2 3, Stack: * ( +
  • Reading ‘)’. Popping everything until ‘(‘ is encountered on the stack. Output: 1 2 3 +, Stack: *
  • Reading ‘/’. Same precedence as ‘*’. We pop the stack. Output: 1 2 3 + *, Stack: /
  • Reading ‘4’. Output: 1 2 3 + * 4, Stack: /
  • Reached the end of the equation, popping until the stack is empty. Result: 1 2 3 + * 4 /

Implementation in Java

No that we have gotten a basic understanding for what infix, prefix and postfix notation actually is, and how the algorithm to convert from infix to prefix / postfix works, it’s time to implement the algorithms in Java.

package infix_prefix_postfix;

import java.util.Stack;

/**
 * Class containing methods to convert infix to prefix / postfix. 
 * The infix expressions must be written without spaces!
 * @author AOProgrammer
 */
public class Converter {
    
    // Operators 
    private final static char PLUS = '+';
    private final static char MINUS = '-';
    private final static char PAREN_OPEN = '(';
    private final static char PAREN_CLOSE = ')';
    private final static char MULTIPLY = '*';
    private final static char DIVIDE = '/';
    private final static char MODULO = '%';
    private final static char POWER = '^';

    // We use Character, auto-boxing will do it's job for us. 
    Stack<Character> stack = new Stack<>();

    /**
     * Converting infix to postfix. * * @param infix expression * @return postfix expression * @throws IllegalArgumentException infix is null * @throws RuntimeException Invalid infix expression
     */
    public String infixToPostfix(String infix) {
        if (infix == null) throw new IllegalArgumentException("Invalid input");
        stack.clear();
        // Keeping track of number of parenthesis 
        int numberOfOpens = 0;
        // Removing beginning and ending whitespace 
        char[] infixArr = infix.trim().toCharArray();
        StringBuilder builder = new StringBuilder();
        for (char c : infixArr) {
            // We don't want to process whitespace 
            if (c == ' ') {
                continue;
            }
            // If we encounter an operand, we output it immediately 
            if (Character.isLetterOrDigit(c)) {
                builder.append(c);
            } // If we encounter an opening parenthesis, push it to the stack
            else if (c == PAREN_OPEN) {
                stack.push(c);
                numberOfOpens++;
            } // If we encouner a closing parenthesis, pop stack until open parenthesis is found 
            else if (c == PAREN_CLOSE) {
                while (!stack.isEmpty() && stack.peek() != PAREN_OPEN) builder.append(stack.pop());
                if (stack.isEmpty() || stack.peek() != PAREN_OPEN)
                    throw new RuntimeException("Mismatched parenthesis");
                // Got through tests, updating state and popping 
                numberOfOpens--;
                stack.pop();
            }
            // Encountered an operator. Pop stack until operator has <= precedence as operator on stack. 
            else {
                while (!stack.isEmpty() && getPrecedence(c) <= getPrecedence(stack.peek())) builder.append(stack.pop());
                stack.push(c);
            }
        } // End of for-loop 
        // Outputting the rest on the stack 
        while (!stack.isEmpty()) {
            if (stack.peek() == PAREN_OPEN) numberOfOpens++;
            else if (stack.peek() == PAREN_CLOSE) numberOfOpens--;
            if (numberOfOpens < 0) throw new RuntimeException("Mismatched parenthesis");
            builder.append(stack.pop());
        }
        if (numberOfOpens != 0) throw new RuntimeException("Mismatched parenthesis");
        return builder.toString();
    }

    /**
     * Converting infix to prefix. * * @param infix infix expression * @return prefix expression
     */
    public String infixToPrefix(String infix) {
        if (infix == null)
            throw new IllegalArgumentException("Invalid input");
        // Removing beginning and ending whitespace 
        infix = infix.trim();
        // Reversing, and replacing parenthesis 
        String infixRev = reverse(infix, true);
        String prefix = infixToPostfix(infixRev);
        // Returning reversed result, without replacing parenthesis 
        return reverse(prefix, false);
    }

    /**
     * Reversing a string * * @param s String to reverse * @param replace true if parenthesis shall be switched * @return reversed string
     */
    private String reverse(String s, boolean replace) {
        StringBuilder reverseBuilder = new StringBuilder();
        for (int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);
            if (replace) {
                if (c == PAREN_OPEN) c = PAREN_CLOSE;
                else if (c == PAREN_CLOSE) c = PAREN_OPEN;
            }
            reverseBuilder.append(c);
        }
        return reverseBuilder.toString();
    }

    /**
     * Returning precedence of an operator. * * @param operator the operator * @return int, higher number = higher precedence. -1 = invalid operator.
     */
    private int getPrecedence(char operator) {
        switch (operator) {
            case PLUS:
            case MINUS:
                return 1;
            case MULTIPLY:
            case DIVIDE:
            case MODULO:
                return 2;
            case POWER:
                return 3;
        }
        return -1;
    }
}