# Infix, Prefix and Postfix notation

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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 | package infix_prefix_postfix; import java.util.Stack; /** * Class containing methods to convert infix to prefix / postfix. * <p> * The infix expressions must be written without spaces! * * @author Modestprogrammer.com */ 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; } } |