如何修改我的Shunting-Yard算法以便接受一元运算符？

Question

我一直在努力在JavaScript中实现Shunting-Yard算法.

到目前为止,这是我的工作:

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';
    }

}

它到目前为止工作正常.如果我给它:

((5 + 3)*8)

它将输出:

中缀:((5 + 3)*8)
后缀(RPN):5 3 + 8*
结果:64

但是,我正在努力实现一元运算符,所以我可以做类似的事情:

((-5 + 3)*8)

实现一元运算符(否定等)的最佳方法是什么？另外,有没有人有任何处理浮点数的建议？

最后一件事,如果有人看到我在JavaScript中做任何奇怪的事情让我知道.这是我的第一个JavaScript程序,我还不习惯它.

Answer 1

最简单的方法是进行isNumber匹配/-?[0-9]+(\.[0-9]+)?/,处理浮点数和负数.

如果你真的需要处理一元运算符(比如,对括号表达式进行一元否定),那么你必须:

• 使它们成为正确的联想.
• 使它们优先于任何中缀运算符.
• 单独处理它们EvaluateExpression(创建一个单独的PerformUnaryExpression函数,只需要一个操作数).
• InfixToPostfix通过跟踪某种状态来区分一元和二元减去.看看在这个Python示例中'-'是如何变成的.'-u'

我写了一个更彻底的解释,处理另一个问题上的一元减号.

Answer 2

我的建议是这样的。不要将“-”作为算术运算符来处理。将其视为“符号”运算符。或者将其视为整个操作数的一部分（即其符号）。我的意思是，每次遇到“-”时，只需将其后面的操作数乘以-1，然后继续读取下一个标记。:) 我希望有帮助。只是一个简单的想法...