Postfixing Simple Expressions - No Parentheses

What are infix and postfix notation?

Infix notation is the mathematical notation like

3 + 4 * 15 - 42 / 7

that people know and love. To simplify such an expression, mathematicians have defined an order of operations (PEMDAS). Humans can quickly scan simple expressions and determine the correct computations to make without really thinking about what they are doing.

Postfix notation looks like 3415*+427/- and is much easier for computers. The operators (*, +, /, and -) are in order so that the computer can work left to right. This post won't cover solving postfix expressions, but just notice that * comes before the + and / comes before the -. And the operands (the numbers) separate them in just the right places so that the computer can always use the preceding two operands in each operation.

For more information, I like this explanation about postfix notation that covers how to evaluate such expressions.

Shunting Yard Algorithm

Edsger Dijkstra developed the shunting yard algorithm to quickly convert from infix to postfix. The general idea behind this algorithm allows for a lot of flexibility to properly order complex expressions for evaluation.

To illustrate this algorithm most simply we will avoid any edge cases and not allow any parentheses. Also there will not be any negative numbers to avoid confusion with subtraction.

The first step in our process is to create an array that is in the original order but with multi-character expressions (often called tokens) in the same cell. Then each token is evaluated and placed into a final postfixed array at just the right place.

Separate Operands and Operations

We will convert infix strings into arrays by walking through each character and either creating a new cell or add to the end of the string in the previous cell. In our simplified universe of expressions, each operation is one character and these will determine when we create new cells.

Start with an empty array and then add an empty string as the first element in the array. Then iterate over each character in the infix expression.

var input = "37+14*561-12.4/x";
var arr = [];
arr.push("");
for (var i=0;i<input.length;i++){

When a character is either +,-,*, or / we will add two elements to the array. The first will be a string that is simply the given operation and the second will be an empty string.

if (input[i] == "+" || input[i] == "*" || input[i] == "-" || input[i] == "/"){
	arr.push(input[i]);
	arr.push("");
}

For any other characters, we simply concatenate to the end of the last string in the array.

else {
	arr[arr.length-1] += input[i];
}

Ultimately we have a simple algorithm to break the original expression into an array that is a bit simpler to deal with in the next step.

var input = "37+14*561-12.4/x";
var arr = [];
arr.push("");
for (var i=0; i<input.length;i++){
	if (input[i] == "+" || input[i] == "*" || input[i] == "-" || input[i] == "/"){
		arr.push(input[i]);
		arr.push("");
	}
	else {
		arr[arr.length-1] += input[i];
	}
}
//arr should be [37,+,14,*,561,-,12.4,/,x]

Ordering the Operations

Then we need to place the operations in the right places. We will create two arrays. One will be the eventual final array and the other will be a stack that temporarily holds some operations until the right time to move them.

var infixArray = ["14","+","13","*","2","-","1"];
var postfix = [];
var stack = [];

Only operations will go in the stack, operations will only be added to the end of the stack, and operations will only be removed from the end of the stack (so the stack is LIFO -- last-in-first-out).

There are only a few scenarios to consider as we move through the infix array element by element.

for (var i=0;i<infixArray.length;i++){

The element is an operand

Operands (thins like numbers and variables) are simple. Each time we see an operand, push it to the postfix array.

//The indexOf function will return -1 for anything other than the 4 operations.
if ("+-*/".indexOf(infixArray[i]) < 0){
	postfix.push(infixArray[i]);
}

The element is an operator and the stack is empty

Every other element must be an operator and there are a few things that can happen. The simplest case is when the stack is empty and we just add the operation to the stack.

else if (stack.length == 0){
	stack.push(infixArray[i]);
}

If the operand has greater precedence

To correctly apply order of operations, each operation is assigned a precedence. A higher precedence means that an operation is performed first. For our simple universe of operations, multiplication and division will have precedence of 2 while addition and subtraction will have precedence of 1.

var prec = {"*":2,"/":2,"+":1,"-":1};

If we hit an operation with greater precedence than the last operation in the stack, we also just add that operation to the end of the stack.

else if (prec[infixArray[i]] > prec[stack[stack.length-1]]){
	stack.push(infixArray[i]);
}

If the precedence is not greater

The final possibility is an operation with precedence less than or equal to the last operation in the stack. In this case we move operations from the end of the stack to the postfix array until the stack is empty or the new operation has greater precedence than the last operation in the stack.

Then we add the new operation to the end of the stack.

else {
	while (stack.length > 0 && prec[infixArray[i]] <= prec[stack[stack.length-1]]){
		postfix.push(stack[stack.length-1]);
		stack.pop();//removes last element of stack
	}
	stack.push(infixArray[i]);
}

Clear the stack

Once every element in the infix array has been handled with one of the four above cases, there might still be some operations in the stack. Move all of them to the postfix array starting from the end.

while (stack.length > 0){
	postfix.push(stack[stack.length-1]);
	stack.pop();//removes last element of stack
}

The Full Algorithm

The algorithm is really quite simple for simple expressions. Visit Replit for an interactive version of the code.

var infixArray = ["14","+","13","*","2","-","1"];
var postfix = [];
var stack = [];
var prec = {"*":2,"/":2,"+":1,"-":1};
for (var i=0;i<infixArray.length;i++){
    if ("+-*/".indexOf(infixArray[i]) < 0){
        postfix.push(infixArray[i]);
    }
    else if(stack.length ==0){
        stack.push([]);
    }
    else if (prec[infixArray[i]] > prec[stack[stack.length-1]]){ 	
        stack.push(infixArray[i]); 
    }
    else {
        while (stack.length > 0 && prec[infixArray[i]] <= prec[stack[stack.length-1]]){ 		
            postfix.push(stack[stack.length-1]);
            stack.pop();//removes last element of stack			
        } 	
        stack.push(infixArray[i]);
    }
}
while (stack.length > 0){
    postfix.push(stack[stack.length-1]);
    stack.pop();//removes last element of stack
}
//postfix array should be [14,13,2,*,+,1,-]

Handling more complex expressions is really just a matter of adding more cases. This blog post covers many more math expressions.

Enter a simple math expression below to see the postfixed equivalent, or click here to see it in action step-by-step.