调车场算法不必要的括号

调车场算法不必要的括号

本文介绍了调车场算法不必要的括号的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

输入(在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;

    而(指数<长度){
        VAR标记=输入[指数++];

        开关(标记){
        外壳 (:
        stack.unshift(标记);
            打破;
        外壳 ):
            而(stack.length){
                VAR令牌= stack.shift();
                如果(标记===()打破;
                其他output.push(标记);
            }

            如果(令牌!==()
                抛出新的错误(不匹配的括号内。);
            打破;
        默认:
            如果(table.hasOwnProperty(令牌)){
                而(stack.length){
                    VAR标点符号=堆叠[0];

                    如果(标点符号===()打破;

                    VAR运算符=表[令牌]
                        precedence =运算符。precedence,
                        。先行=表[标点符号] precedence;

                    如果(precedence>先行||
                        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号 - + <脚本>功能分析器(一){this.table =一}分析器.prototype.parse =函数(){VAR B =则为a.length,表= this.table,输出= [],堆栈= [],指数= 0;而(指数< 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);否则抛出新的错误(不匹配的括号);}返回输出};< / SCRIPT>

这,顺便说一句不(而且永远不会)计算为 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 - <脚本>功能分析器(一){this.table =一}分析器.prototype.parse =函数(){VAR B =则为a.length,表= this.table,输出= [],堆栈= [],指数= 0;而(指数< 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);否则抛出新的错误(不匹配的括号);}返回输出};< / SCRIPT>

有你有它:在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.

这篇关于调车场算法不必要的括号的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!

09-06 06:29