输入（在javascript中）是"3-2+（8-3）"
我想将此表达式转换为反向波兰符号。但是，根据算法，我可以得到"3 2 8 3 - + -"，它不计算结果 12.....有什么解决方法吗？我知道这里的括号是不必要的，但是，哦，好吧...我在下面有我的函数：
function ShuntingYard(str){
str=str.replace(/)(/g, ")*(");
var arr=str.split("");
var sYqueue=[];
var sYstack=[];
while (arr.length>0){
var token=arr.shift();
if (/d+/.test(token)){
// if it's a number, push to the queue
sYqueue.push(token);
} // end if
else if (/[+]|[-]|[*]|[/]/.test(token)){
// if it's an operator
if (sYstack.length==0){
// if an empty operator stack
sYstack.push(token);
}
else{
while ((/[*]|[/]/.test(sYstack[sYstack.length-1])) &&
(/[+]|[-]/.test(token))){
// if the TOS has operator with higher precedence
// then need to pop off the stack
// and add to queue
console.log(sYstack);
sYqueue.push(sYstack.pop());
}
sYstack.push(token);
}
}
else if (/[(]/.test(token)){
// if it's left parenthesis
sYstack.push(token);
}
else if (/[)]/.test(token)){
// if it's right parenthesis
while (!(/[(]/.test(sYstack[sYstack.length-1]))){
// while there's no left parenthesis on top of the stack
// then need to pop the operators onto the queue
sYqueue.push(sYstack.pop());
} // end while
if (sYstack.length==0)
{ // unbalanced parenthesis!!
console.log("error, unbalanced parenthesis");
}
else
{
sYstack.pop(); // pop off the left parenthesis
}
}
else{
// other cases
}
} // end while
// now while the stack is not empty, pop every operators to queue
while (sYstack.length>0){
sYqueue.push(sYstack.pop());
}
return sYqueue;
} // end function ShuntingYard
很久以前，在一个遥远的要点中，我用JavaScript编写了Dijkstra调车场算法的实现：
function Parser(table) {
this.table = table;
}
Parser.prototype.parse = function (input) {
var length = input.length,
table = this.table,
output = [],
stack = [],
index = 0;
while (index < length) {
var token = input[index++];
switch (token) {
case "(":
stack.unshift(token);
break;
case ")":
while (stack.length) {
var token = stack.shift();
if (token === "(") break;
else output.push(token);
}
if (token !== "(")
throw new Error("Mismatched parentheses.");
break;
default:
if (table.hasOwnProperty(token)) {
while (stack.length) {
var punctuator = stack[0];
if (punctuator === "(") break;
var operator = table[token],
precedence = operator.precedence,
antecedence = table[punctuator].precedence;
if (precedence > antecedence ||
precedence === antecedence &&
operator.associativity === "right") break;
else output.push(stack.shift());
}
stack.unshift(token);
} else output.push(token);
}
}
while (stack.length) {
var token = stack.shift();
if (token !== "(") output.push(token);
else throw new Error("Mismatched parentheses.");
}
return output;
};
以下是您将如何使用它：
var parser = new Parser({
"*": { precedence: 2, associativity: "left" },
"/": { precedence: 2, associativity: "left" },
"+": { precedence: 1, associativity: "left" },
"-": { precedence: 1, associativity: "left" }
});
var output = parser.parse("3 - 2 + ( 8 - 3 )".split(" ")).join(" ");
alert(JSON.stringify(output)); // "3 2 - 8 3 - +"<script>function Parser(a){this.table=a}Parser.prototype.parse=function(a){var b=a.length,table=this.table,output=[],stack=[],index=0;while(index<b){var c=a[index++];switch(c){case"(":stack.unshift(c);break;case")":while(stack.length){var c=stack.shift();if(c==="(")break;else output.push(c)}if(c!=="(")throw new Error("Mismatched parentheses.");break;default:if(table.hasOwnProperty(c)){while(stack.length){var d=stack[0];if(d==="(")break;var e=table[c],precedence=e.precedence,antecedence=table[d].precedence;if(precedence>antecedence||precedence===antecedence&&e.associativity==="right")break;else output.push(stack.shift())}stack.unshift(c)}else output.push(c)}}while(stack.length){var c=stack.shift();if(c!=="(")output.push(c);else throw new Error("Mismatched parentheses.");}return output};</script>顺便说一下，这不会（也永远不会）评估为12，但这确实：
var parser = new Parser({
"*": { precedence: 2, associativity: "left" },
"/": { precedence: 2, associativity: "left" },
"+": { precedence: 1, associativity: "left" },
"-": { precedence: 1, associativity: "left" }
});
var output = parser.parse("3 * 3 - 2 + 8 - 3".split(" ")).join(" ");
alert(JSON.stringify(output)); // "3 3 * 2 - 8 + 3 -"<script>function Parser(a){this.table=a}Parser.prototype.parse=function(a){var b=a.length,table=this.table,output=[],stack=[],index=0;while(index<b){var c=a[index++];switch(c){case"(":stack.unshift(c);break;case")":while(stack.length){var c=stack.shift();if(c==="(")break;else output.push(c)}if(c!=="(")throw new Error("Mismatched parentheses.");break;default:if(table.hasOwnProperty(c)){while(stack.length){var d=stack[0];if(d==="(")break;var e=table[c],precedence=e.precedence,antecedence=table[d].precedence;if(precedence>antecedence||precedence===antecedence&&e.associativity==="right")break;else output.push(stack.shift())}stack.unshift(c)}else output.push(c)}}while(stack.length){var c=stack.shift();if(c!=="(")output.push(c);else throw new Error("Mismatched parentheses.");}return output};</script>这就是它：JavaScript中Dijkstra调车场算法的通用实现。
函数逻辑中存在错误：在 2 种情况下，必须将前一个运算符从堆栈弹出到输出队列：
1.它的优先级更高（您的代码处理这种情况）。
2.它具有相同的优先级，并且新运算符是左关联运算符（加号和减号就是这种情况）。
第二种情况未包含在您的代码中，因此它无法正常工作。
在github Xpresion上有一个表达式解析器引擎（JavaScript/PHP/Python和ActionScript的实现）（ps.我是作者）
该引擎非常灵活且可配置，可以创建解析器来解析任何表达式，其中还包括多态运算符和一般 n 元运算符（例如。三元如果-那么-否则）
该算法非常通用（可以说，调车场算法的广义变体）