如何修改调车场算法以使其接受一元运算符？

Question

我一直致力于在课堂上用 JavaScript 实现调车场算法。

到目前为止，这是我的工作：

 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 程序，我还不习惯。

原文由 KingNestor 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

最简单的方法是制作 isNumber 匹配 /-?[0-9]+(\.[0-9]+)?/ ，同时处理浮点数和负数。

如果你真的需要处理一元运算符（比如，括号表达式的一元否定），那么你必须：

• 使它们右结合。
• 使它们的优先级高于任何中缀运算符。
• 在 EvaluateExpression 中分别处理它们（制作一个单独的 PerformUnaryExpression 只接受一个操作数的函数）。
• 通过跟踪某种状态，区分 InfixToPostfix 中的一元和二进制减号。在这个 Python 示例 中，看看 '-' 是如何变成 '-u' 的。

我在 另一个 SO 问题 上写了关于处理一元减号的更详尽的解释。

原文由 Austin Taylor 发布，翻译遵循 CC BY-SA 3.0 许可协议