调车场算法不必要的括号 [英] Shunting Yard Algorithm with unnecessary parentheses
本文介绍了调车场算法不必要的括号的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！
问题描述
输入（在JavaScript）为3-2 +（8-3）
我想翻译这个前pression到逆波兰式。 然而，根据算法，我可以得到3 2 8 3 - + - ，它不评估的结果12 .....左右方法的任何工作呢？我知道括号是不必要的位置，但是，哦...我有我下面的功能：
函数ShuntingYard（STR）{
海峡= str.replace（/ \）\（/克，）*（）;
VAR ARR = str.split（）;
变种sYqueue = [];
变种sYstack = [];
而（arr.length大于0）{
VAR令牌= arr.shift（）;
如果（/ \ D + /。测试（标记））{
//如果它是一个数字，推到队列
sYqueue.push（标记）;
如果} //结束
否则，如果（/ [+] | [ - ] | [*] | [\ /] /测试（标记））{
//如果它是一个运营商
如果（sYstack.length == 0）{
//如果一个空的运营商栈
sYstack.push（标记）;
}
其他{
而（（/[*]|[\/]/.test(sYstack[sYstack.length-1]））及＆安培;
（/ [+] | [ - ] /测试（标记）））{
//如果TOS有运营商，拥有较高的precedence
//那么就需要弹出堆栈
//并添加到队列
执行console.log（sYstack）;
sYqueue.push（sYstack.pop（））;
}
sYstack.push（标记）;
}
}
否则，如果（/ [（] /。测试（标记））{
//如果它的左括号
sYstack.push（标记）;
}
否则如果（/ [）] /。试验（令牌））{
//如果是右括号
而（！（/ [（] /。试验（sYstack [sYstack.length-1]）））{
//虽然没有在堆栈的顶部没有左括号
//那么就需要弹出的运营商到队列中
sYqueue.push（sYstack.pop（））;
} //结束时
如果（sYstack.length == 0）
{//不平衡的括号！
的console.log（错误，不平衡的括号）;
}
其他
{
sYstack.pop（）; //关闭弹出左括号
}
}
其他{
//其他情况
}
} //结束时
//现在而栈不为空，弹出每一个运营商要排队
而（sYstack.length大于0）{
sYqueue.push（sYstack.pop（））;
}
返回sYqueue;
} //函数结束ShuntingYard
解决方案
很久很久以前，在一个依据很远很远我在JavaScript写的Dijkstra的调车场算法的实现：
函数分析器（表）{
this.table =表;
}
Parser.prototype.parse =功能（输入）{
VAR长度= input.length，
表= this.table，
输出= []，
堆栈= []，
索引= 0;
而（指数＆LT;长度）{
VAR标记=输入[指数++];
开关（标记）{
外壳 （：
stack.unshift（标记）;
打破;
外壳 ）：
而（stack.length）{
VAR令牌= stack.shift（）;
如果（标记===（）打破;
其他output.push（标记）;
}
如果（令牌！==（）
抛出新的错误（不匹配的括号内。）;
打破;
默认：
如果（table.hasOwnProperty（令牌））{
而（stack.length）{
VAR标点符号=堆叠[0];
如果（标点符号===（）打破;
VAR运算符=表[令牌]
precedence =运算符。precedence，
。先行=表[标点符号] precedence;
如果（precedence＆GT;先行||
precedence ===先行和放大器;＆安培;
operator.associativity ===右）打破;
别的output.push（stack.shift（））;
}
stack.unshift（标记）;
}其他output.push（标记）;
}
}
而（stack.length）{
VAR令牌= stack.shift（）;
如果（令牌==（）output.push（标记）！;
否则抛出新的错误（不匹配的括号内。）;
}
返回输出;
};
下面是你将如何使用它：
VAR分析器=新的解析器（{
*：{precedence：2，关联性：左}，
/：{precedence：2，关联性：左}，
+：{precedence：1，关联性：左}，
- ：{precedence：1，关联性：左}
}）;
无功输出= parser.parse（3 - 2 +（8 - 3）分裂（。（）;））加入。
警报（JSON.stringify（输出））; //3月二号至8月3号 - +
＆LT;脚本＆GT;功能分析器（一）{this.table =一}分析器.prototype.parse =函数（）{VAR B =则为a.length，表= this.table，输出= []，堆栈= []，指数= 0;而（指数＆LT; B）{VAR C = A [索引++ ];开关（三）{案（：stack.unshift（C）;打破;案件）：而（stack.length）{VAR C = stack.shift（）;如果（C ===（ ）打破;否则output.push（C）}，如果（C = =！（）抛出新的错误;打破;默认情况下（不匹配的括号。）：如果（table.hasOwnProperty（C））{而（堆栈.length）{VAR D =栈[0];如果（D ===（）打破; VAR e=table[c],$p$pcedence=e.$p$pcedence,antecedence=table[d].$p$pcedence;if($p$pcedence>antecedence||$p$pcedence===antecedence&&e.associativity==="right")break;else output.push（stack.shift（））} stack.unshift（C）}其他output.push（C）}}而（stack.length）{VAR C = stack.shift（！）;如果（C == （）output.push（C）;否则抛出新的错误（不匹配的括号）;}返回输出};＆LT; / SCRIPT＆GT;
这，顺便说一句不（而且永远不会）计算为 12 ，但这：
VAR分析器=新的解析器（{
*：{precedence：2，关联性：左}，
/：{precedence：2，关联性：左}，
+：{precedence：1，关联性：左}，
- ：{precedence：1，关联性：左}
}）;
无功输出= parser.parse（3 * 3 - 2 + 8 - 3.split（（）;））加入。
警报（JSON.stringify（输出））; //3 3 * 2 - 8 + 3 -
＆LT;脚本＆GT;功能分析器（一）{this.table =一}分析器.prototype.parse =函数（）{VAR B =则为a.length，表= this.table，输出= []，堆栈= []，指数= 0;而（指数＆LT; B）{VAR C = A [索引++ ];开关（三）{案（：stack.unshift（C）;打破;案件）：而（stack.length）{VAR C = stack.shift（）;如果（C ===（ ）打破;否则output.push（C）}，如果（C = =！（）抛出新的错误;打破;默认情况下（不匹配的括号。）：如果（table.hasOwnProperty（C））{而（堆栈.length）{VAR D =栈[0];如果（D ===（）打破; VAR e=table[c],$p$pcedence=e.$p$pcedence,antecedence=table[d].$p$pcedence;if($p$pcedence>antecedence||$p$pcedence===antecedence&&e.associativity==="right")break;else output.push（stack.shift（））} stack.unshift（C）}其他output.push（C）}}而（stack.length）{VAR C = stack.shift（！）;如果（C == （）output.push（C）;否则抛出新的错误（不匹配的括号）;}返回输出};＆LT; / SCRIPT＆GT;
有你有它：在JavaScript广义实现Dijkstra的调车场算法
Input (in javascript) is "3-2+(8-3)"
I want to translate this expression to Reverse Polish Notation. However, according to the algorithm, I can get "3 2 8 3 - + -", which doesn't evaluate to the result 12..... Any work around method for this? I know the parentheses are unnecessary here, but, oh well...I have my function below:
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
解决方案
A long time ago in a gist far far away I wrote an implementation of Dijkstra's shunting yard algorithm in JavaScript:
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;
};
Here is how you would use it:
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>
This, incidentally does not (and never will) evaluate to 12, but this does:
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>
There you have it: a generalized implementation of Dijkstra's shunting yard algorithm in JavaScript.
这篇关于调车场算法不必要的括号的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
查看全文
