Skip to content

Instantly share code, notes, and snippets.

@shalvah
Last active October 22, 2018 19:21
Show Gist options
  • Save shalvah/7afa251a36f23d960cabdcf67bcbb24e to your computer and use it in GitHub Desktop.
Save shalvah/7afa251a36f23d960cabdcf67bcbb24e to your computer and use it in GitHub Desktop.
Tokenize and convert a math expression from infix to postfix in Javascript
function parse(inp){
var outQueue=[];
var opStack=[];
Array.prototype.peek = function() {
return this.slice(-1)[0];
};
var assoc = {
"^" : "right",
"*" : "left",
"/" : "left",
"+" : "left",
"-" : "left"
};
var prec = {
"^" : 4,
"*" : 3,
"/" : 3,
"+" : 2,
"-" : 2
};
Token.prototype.precedence = function() {
return prec[this.value];
};
Token.prototype.associativity = function() {
return assoc[this.value];
};
//tokenize
var tokens=tokenize(inp);
tokens.forEach(function(v) {
//If the token is a number, then push it to the output queue
if(v.type === "Literal" || v.type === "Variable" ) {
outQueue.push(v);
}
//If the token is a function token, then push it onto the stack.
else if(v.type === "Function") {
opStack.push(v);
} //If the token is a function argument separator
else if(v.type === "Function Argument Separator") {
//Until the token at the top of the stack is a left parenthesis
//pop operators off the stack onto the output queue.
while(opStack.peek()
&& opStack.peek().type !== "Left Parenthesis") {
outQueue.push(opStack.pop());
}
/*if(opStack.length == 0){
console.log("Mismatched parentheses");
return;
}*/
}
//If the token is an operator, o1, then:
else if(v.type == "Operator") {
//while there is an operator token o2, at the top of the operator stack and either
while (opStack.peek() && (opStack.peek().type === "Operator")
//o1 is left-associative and its precedence is less than or equal to that of o2, or
&& ((v.associativity() === "left" && v.precedence() <= opStack.peek().precedence())
//o1 is right associative, and has precedence less than that of o2,
|| (v.associativity() === "right" && v.precedence() < opStack.peek().precedence()))) {
outQueue.push(opStack.pop());
}
//at the end of iteration push o1 onto the operator stack
opStack.push(v);
}
//If the token is a left parenthesis (i.e. "("), then push it onto the stack.
else if(v.type === "Left Parenthesis") {
opStack.push(v);
}
//If the token is a right parenthesis (i.e. ")"):
else if(v.type === "Right Parenthesis") {
//Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
while(opStack.peek()
&& opStack.peek().type !== "Left Parenthesis") {
outQueue.push(opStack.pop());
}
/*if(opStack.length == 0){
console.log("Unmatched parentheses");
return;
}*/
//Pop the left parenthesis from the stack, but not onto the output queue.
opStack.pop();
//If the token at the top of the stack is a function token, pop it onto the output queue.
if(opStack.peek() && opStack.peek().type === "Function") {
outQueue.push(opStack.pop());
}
}
});
return outQueue.concat(opStack.reverse());
}
function toString(rpn) {
return rpn.map(token => token.value).join(" ");
}
@Pablo2048
Copy link

Hi and thank You. Unfortunately this won't work with unary '-' - try to convert -5 * 3 for example...

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment