How can I modify my Shunting-Yard Algorithm so it accepts unary operators?

Posted by KingNestor on Stack Overflow See other posts from Stack Overflow or by KingNestor
Published on 2009-10-20T08:00:16Z Indexed on 2010/04/04 19:13 UTC
Read the original article Hit count: 217

I've been working on implementing the Shunting-Yard Algorithm in JavaScript for class.

Here is my work so far:

var userInput = prompt("Enter in a mathematical expression:");
var postFix = InfixToPostfix(userInput);
var result = EvaluateExpression(postFix);

document.write("Infix: " + userInput + "<br/>");
document.write("Postfix (RPN): " + postFix + "<br/>");
document.write("Result: " + result + "<br/>");


function EvaluateExpression(expression)
{
    var tokens = expression.split(/([0-9]+|[*+-\/()])/);
    var evalStack = [];

    while (tokens.length != 0)
    {
        var currentToken = tokens.shift();

        if (isNumber(currentToken))
        {
            evalStack.push(currentToken);
        }
        else if (isOperator(currentToken))
        {
            var operand1 = evalStack.pop();
            var operand2 = evalStack.pop();

            var result = PerformOperation(parseInt(operand1), parseInt(operand2), currentToken);
            evalStack.push(result);
        }
    }
    return evalStack.pop();
}

function PerformOperation(operand1, operand2, operator)
{
    switch(operator)
    {
        case '+': 
            return operand1 + operand2;
        case '-':
            return operand1 - operand2;
        case '*':
            return operand1 * operand2;
        case '/':
            return operand1 / operand2;
        default:
            return;
    }

}

function InfixToPostfix(expression)
{
    var tokens = expression.split(/([0-9]+|[*+-\/()])/);
    var outputQueue = [];
    var operatorStack = [];

    while (tokens.length != 0)
    {
        var currentToken = tokens.shift();

        if (isNumber(currentToken)) 
        {
            outputQueue.push(currentToken);
        }
        else if (isOperator(currentToken)) 
        {
            while ((getAssociativity(currentToken) == 'left' && 
                    getPrecedence(currentToken) <= getPrecedence(operatorStack[operatorStack.length-1])) ||
                   (getAssociativity(currentToken) == 'right' && 
                    getPrecedence(currentToken) < getPrecedence(operatorStack[operatorStack.length-1]))) 
            {
                outputQueue.push(operatorStack.pop())
            }

            operatorStack.push(currentToken);

        }
        else if (currentToken == '(')
        {
                operatorStack.push(currentToken);
        }
        else if (currentToken == ')')
        {
            while (operatorStack[operatorStack.length-1] != '(')
            {
    	        if (operatorStack.length == 0)
    	            throw("Parenthesis balancing error! Shame on you!");

    	        outputQueue.push(operatorStack.pop());
            }	
            operatorStack.pop();		
        }   
    }  

    while (operatorStack.length != 0)
    {
        if (!operatorStack[operatorStack.length-1].match(/([()])/))
            outputQueue.push(operatorStack.pop());
        else
            throw("Parenthesis balancing error! Shame on you!");         
    }

    return outputQueue.join(" ");
}    


function isOperator(token)
{
    if (!token.match(/([*+-\/])/))
        return false;
    else 
        return true;
}


function isNumber(token)
{
    if (!token.match(/([0-9]+)/))
        return false;
    else
        return true;
}


function getPrecedence(token)
{
    switch (token)
    {
    	case '^':
    	    return 9; 
    	case '*':		    
    	case '/':
    	case '%':
    	    return 8;
        case '+':
    	case '-':
    	    return 6;
    	default: 
    	    return -1;
    }
}

function getAssociativity(token)
{
    switch(token)
    {
    	case '+':
    	case '-':
    	case '*':
    	case '/':
    	    return 'left';
    	case '^':
    	    return 'right';
    }

}

It works fine so far. If I give it:

((5+3) * 8)

It will output:

Infix: ((5+3) * 8)
Postfix (RPN): 5 3 + 8 *
Result: 64

However, I'm struggling with implementing the unary operators so I could do something like:

((-5+3) * 8)

What would be the best way to implement unary operators (negation, etc)? Also, does anyone have any suggestions for handling floating point numbers as well?

One last thing, if anyone sees me doing anything weird in JavaScript let me know. This is my first JavaScript program and I'm not used to it yet.

© Stack Overflow or respective owner

Related posts about shunting-yard

Related posts about algorithm