1

输入（在 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
4

3 回答 3

1

很久以前，在一个很远的地方，我用 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 的调车场算法的通用实现。

于 2014-12-01T11:16:13.580 回答
0

您的函数逻辑中存在错误：在 2 种情况下，必须将前一个运算符从堆栈弹出到输出队列：
1. 它的优先级更高（您的代码处理这种情况）。
2.它具有相同的优先级，并且新运算符是左关联的（加号和减号就是这种情况）。
第二种情况未包含在您的代码中，因此无法正常工作。

于 2014-12-01T09:10:44.023 回答
0

在github Xpresion上有一个表达式解析器引擎（JavaScript/PHP/Python 和 ActionScript 的实现）（ps。我是作者）

该引擎非常灵活且可配置，可以创建解析器来解析任何表达式，其中还包括多态运算符和通用 n 元运算符（例如三元 if-then-else）

该算法非常通用（可以说，Shunting Yard algorithm的广义变体）

于 2015-01-26T22:26:07.737 回答