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

Question

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.

Answer 1

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.

Answer 2

my suggestion is this. don't handle the '-' as an arithmetic operator. treat it as a 'sign' operator. or treat it as if it's a part of the whole operand (i.e. its sign). what i mean is that everytime you encounter '-', you just have to multiply the operand after it by -1, then proceed to read the next token. :) i hope that helps. just a simple thought...

Answer 3

I could solve this problem by modifying unary operators('+' and '-') to distinguish them from the binary ones.

For example, I called the unary minus 'm' and unary plus 'p', making them right-assocative and their precedence equal to the exponent operator('^').

To detect if the operator is unary I simply had to check if the token before the operator was an operator or an opening bracket.

This is my implementation in C++:

        if (isOperator(*token))
        {
            if (!isdigit(*(token - 1)) && *(token - 1) != ')')   // Unary check
            {
                if (*token == '+')
                    *token = 'p';        // To distinguish from the binary ones
                else if (*token == '-')
                    *token = 'm';
                else
                    throw;
            }

            short prec = precedence(*token);
            bool rightAssociative = (*token == '^' || *token == 'm' || *token == 'p');

            if (!operators.empty())
            {
                while (prec < precedence(operators.top()) || (prec == precedence(operators.top()) && !rightAssociative))
                {
                    rpn += operators.top();
                    operators.pop();

                    if (operators.empty())
                        break;
                }
            }
            operators.push(*token);
        }

Here operators is a stack and token is an iterator to the infix expression string

(This just the operator handling part)

Answer 4

When I needed to support this, I did this in an intermediate stage. I started by generating a list of all expression lexemes, then used helper functions to extract operators and operands and the "get operand" function simply consumed two lexemes whenever it saw a unary operator.

It really helps if you use another character to signify "unary minus", though.

Answer 5

To handle floating point numbers you can change your (number part of) regex to:

/([0-9]+\.?[0-9]*)/

so the final regex would be:

/([0-9]+\.?[0-9]*|[*+-\/()])/

And for handling unary minus operator, you can change it to another character like 'u'. (As it is explained here by -TGO)

The javascript code that i wrote for handling unary minus operator based on the link given is:

// expr is the given infix expression from which, all the white spaces has been
// removed.(trailing and leading and in between white space characters)
const operators = ['+', '*', '-', '/', '^'];
const openingBrackets = ['(', '[', '{'];
let exprArr = Array.from(expr);
// Since strings are immutable in js, I am converting it to an array for changing 
// unary minus to 'u'
for (let i = 0; i < expr.length; i++) {
    if (expr[i] === '-') {
        if (i === 0) {
            exprArr[i] = 'u';
        } else if (operators.includes(expr[i - 1])) {
            exprArr[i] = 'u';
        } else if (openingBrackets.includes(expr[i - 1])) {
            exprArr[i] = 'u';
        } else {
            // '-' is not a unary operator
            // it is a binary operator or we have the wrong expression, so...
            if (!openingBrackets.includes(expr[i + 1]) && !/[0-9]/.test(expr[i + 1])) {
                throw new Error("Invalid Expression...");
            }
        }
    }
}
// And finally converting back to a string.
let expr2 = exprArr.join('');

Answer 6

This isn't in Javascript, but here is a library I wrote to specifically solve this problem after searching and not finding any clear answers. This does all you want and more:

https://marginalhacks.com/Hacks/libExpr.rb/

It is a ruby library (as well as a testbench to check it) that runs a modified shunting yard algorithm that also supports unary ('-a') and ternary ('a?b:c') ops. It also does RPN, Prefix and AST (abstract syntax trees) - your choice, and can evaluate the expression, including the ability to yield to a block (a lambda of sorts) that can handle any variable evaluation. Only AST does the full set of operations, including the ability to handle short-circuit operations (such as '||' and '?:' and so on), but RPN does support unary. It also has a flexible precedence model that includes presets for precedence as done by C expressions or by Ruby expressions (not the same). The testbench itself is interesting as it can create random expressions which it can then eval() and also run through libExpr to compare results.

It's fairly documented/commented, so it shouldn't be too hard to convert the ideas to Javascript or some other language.

The basic idea as far as unary operators is that you can recognize them based on the previous token. If the previous token is either an operator or a left-paren, then the "unary-possible" operators (+ and -) are just unary and can be pushed with only one operand. It's important that your RPN stack distinguishes between the unary operator and the binary operator so it knows what to do on evaluation.

Answer 7

In my Java implementation I did it in next way:

expression = expression.replace(" ", "").replace("(-", "(0-")
                .replace(",-", ",0-");
        if (expression.charAt(0) == '-') {
            expression = "0" + expression;
        }