Shunting Yard Algorithm with unnecessary parentheses

Question

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

Answer 1

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.

Answer 2

There is an error in your function logic: the previous operator must be popped from the stack to the output queue in 2 cases:
1. It's precedence is higher(your code handles this case).
2. It has the same precedence and a new operator is left-associative(which is the case for plus and minus).
The second case is not covered in your code, so it doesn't work properly.

Answer 3

There is an expression parser engine (implementations for JavaScript/PHP/Python and ActionScript), on github Xpresion (ps. i'm the author)

The engine is quite flexible and configurable, one can create parsers that parse any expression which also includes polymorphic operators and general n-ary operators (eg. ternary if-then-else)

The algorithm is quite general (one could say, a generalised variation of Shunting Yard algorithm)