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

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


                    
                    
                        
                        javascript
                        
                        algorithm
                        
                        shunting-yard
                        
                    
                    
                        
                        
                        
                        
                        
                        Edit
                        
                        
                        
                            
                        
                        
                        Report

The easiest thing would be to make isNumber match /-?[0-9]+(\.[0-9]+)?/, handling both floating points and negative numbers.

If you really need to handle unary operators (say, unary negation of parenthesized expressions), then you have to:

Make them right-associative.
Make them higher precedence than any of the infix operators.
Handle them separately in EvaluateExpression (make a separate PerformUnaryExpression function which only takes one operand).
Distinguish between unary and binary minus in InfixToPostfix by keeping track of some kind of state. See how '-' is turned into '-u' in this Python example.

I wrote up a more thorough explanation of handling unary minus on another SO question.

answered 2011-03-09T03:18:08.763

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

1 Answer

Your Answer