Hands-On Data Structures and Algorithms with JavaScript
上QQ阅读APP看书,第一时间看更新

Converting infix to postfix expressions

Putting together all the code discussed above, the final code for converting the infix expression to postfix looks like the following: 

function convert(expr) {
var postfix = "";
var ops = new Stack();
var operators = {
"^": {
priority: 4,
associativity: "rtl"
},
"*": {
priority: 3,
associativity: "ltr"
},
"/": {
priority: 3,
associativity: "ltr"
},
"+": {
priority: 2,
associativity: "ltr"
},
"-": {
priority: 2,
associativity: "ltr"
}
};


expr = clean(expr.trim().replace(/\s+/g, "").split(/([\+\-\*\/\^\(\)])/));

if (!isBalanced(expr) {
return 'error';
}

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();
} else if("*^+-/".indexOf(exp) !== -1) {
var currOp = exp;
var prevOp = ops.peek();
while("*^+-/".indexOf(prevOp) !== -1 && ((operators[currOp].associativity === "ltr" && operators[currOp].priority <= operators[prevOp].priority) || (operators[currOp].associativity === "rtl" && operators[currOp].priority < operators[prevOp].priority)))
{
postfix += ops.pop() + " ";
prevOp = ops.peek();
}
ops.push(currOp);
}
});

while(ops.size() > 0) {
postfix += ops.pop() + " ";
}
return postfix;
}

This converts the infix operator provided into the postfix notation.