The input (anything that the user types) will be an expression in the infix notation, which is human-readable. Consider this for example:
(1 + 1) * 2
However, this is not something that we can evaluate as it is, so we convert it into a postfix notation or reverse polish notation.
To convert an infix to a postfix notation is something that takes a little getting used to. What we have is a watered-down version of that algorithm in Wikipedia, as follows:
- Take the input expression (also known as, the infix expression) and tokenize it, that is, split it.
- Evaluate each token iteratively, as follows:
- Add the token to the output string (also known as the postfix notation) if the encountered character is a number
- If it is ( that is, an opening parenthesis, add it to the output string.
- If it is ) that is, a closed parenthesis, pop all the operators as far as the previous opening parenthesis into the output string.
- If the character is an operator, that is, *, ^, +, -, /, and , then check the precedence of the operator first before popping it out of the stack.
- Pop all remaining operators in the tokenized list.
- Return the resultant output string or the postfix notation.
Before we translate this into some code, let's briefly talk about the precedence and associativity of the operators, which is something that we need to predefine so that we can use it while we are converting the infix expression to postfix.
Precedence, as the name suggests, determines the priority of that particular operator whereas associativity dictates whether the expression is evaluated from left to right or vice versa in the absence of a parenthesis. Going by that, since we are only supporting simple operators, let's create a map of operators, their priority, and associativity:
var operators = {
"^": {
priority: 4,
associativity: "rtl" // right to left
},
"*": {
priority: 3,
associativity: "ltr" // left to right
},
"/": {
priority: 3,
associativity: "ltr"
},
"+": {
priority: 2,
associativity: "ltr"
},
"-": {
priority: 2,
associativity: "ltr"
}
};
Now, going by the algorithm, the first step is to tokenize the input string. Consider the following example:
(1 + 1) * 2
It would be converted as follows:
["(", "1", "+", "1", ")", "*", "2"]
To achieve this, we basically remove all extra spaces, replace all white spaces with empty strings, and split the remaining string on any of the *, ^, +, -, / operators and remove any occurrences of an empty string.
Since there is no easy way to remove all empty strings "" from an array, we can use a small utility method called clean, which we can create in the same file.
This can be translated into code as follows:
function clean(arr) {
return arr.filter(function(a) {
return a !== "";
});
}
So, the final expression becomes as follows:
expr = clean(expr.trim().replace(/\s+/g, "").split(/([\+\-\*\/\^\(\)])/));
Now that we have the input string split, we are ready to analyze each of the tokens to determine what type it is and take action accordingly to add it to the postfix notation output string. This is Step 2 of the preceding algorithm, and we will use a Stack to make our code more readable. Let's include the stack into our worker, as it cannot access the outside world. We simply convert our stack to ES5 code, which would look as follows:
var Stack = (function () {
var wmkey = {};
var items = new WeakMap();
items.set(wmkey, []);
function Stack() { }
Stack.prototype.push = function (element) {
var stack = items.get(wmkey);
stack.push(element);
};
Stack.prototype.pop = function () {
var stack = items.get(wmkey);
return stack.pop();
};
Stack.prototype.peek = function () {
var stack = items.get(wmkey);
return stack[stack.length - 1];
};
Stack.prototype.clear = function () {
items.set(wmkey, []);
};
Stack.prototype.size = function () {
return items.get(wmkey).length;
};
return Stack;
}());
As you can see, the methods are attached to the prototype and voilà we have our stack ready.
Now, let's consume this stack in the infix to postfix conversion. Before we do the conversion, we will want to check that the user-entered input is valid, that is, we want to check that the parentheses are balanced. We will be using the simple isBalanced() method as described in the following code, and if it is not balanced we will return an error:
function isBalanced(postfix) {
var count = 0;
postfix.forEach(function(op) {
if (op === ')') {
count++
} else if (op === '(') {
count --
}
});
return count === 0;
}
We are going to need the stack to hold the operators that we are encountering so that we can rearrange them in the postfix string based on their priority and associativity. The first thing we will need to do is check whether the token encountered is a number; if it is, then we append it to the postfix result:
expr.forEach(function(exp) {
if(!isNaN(parseFloat(exp))) {
postfix += exp + " ";
}
});
Then, we check whether the encountered token is an open bracket, and if it is, then we push it to the operators' stack waiting for the closing bracket. Once the closing bracket is encountered, we group everything (operators and numbers) in between and pop into the postfix output, as follows:
expr.forEach(function(exp) {
if(!isNaN(parseFloat(exp))) {
postfix += exp + " ";
} else if(exp === "(") {
ops.push(exp);
} else if(exp === ")") {
while(ops.peek() !== "(") {
postfix += ops.pop() + " ";
}
ops.pop();
}
});
The last (and a slightly complex) step is to determine whether the token is one of *, ^, +, -, /, and then we check the associativity of the current operator first. When it's left to right, we check to make sure that the priority of the current operator is less than or equal to the priority of the previous operator. When it's right to left, we check whether the priority of the current operator is strictly less than the priority of the previous operator. If any of these conditions are satisfied, we pop the operators until the conditions fail, append them to the postfix output string, and then add the current operator to the operators' stack for the next iteration.
The reason why we do a strict check for a right to left but not for a left to right associativity is that we have multiple operators of that associativity with the same priority.
After this, if any other operators are remaining, we then add them to the postfix output string.