输入(在 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
最佳答案
很久以前在gist在很远的地方,我用 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>
您已经知道了:Dijkstra 调车场算法在 JavaScript 中的通用实现。
关于javascript - 带不必要括号的调车场算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27222141/