如何修改我的调度场算法所以它接受一元操作？(How can I modify my Shunting

我一直工作在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程序，我不习惯呢。

Answer 1:

最简单的事情是使isNumber比赛/-?[0-9]+(\.[0-9]+)?/ ，同时处理浮点和负数。

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

• 让他们右结合。
• 让比任何缀运营商的他们更高的优先级。
• 在单独处理它们EvaluateExpression （使一个单独的PerformUnaryExpression函数只需要一个操作数）。
• 在一元和二元减区分InfixToPostfix通过跟踪某种状态的。 怎么看'-'变成'-u'在这个Python的例子 。

我写了关于如何处理一元减去一个更透彻的解释另一个问题SO 。

Answer 2:

我的建议是这样的。 不处理“ - ”作为一个算术运算符。 把它当作一个“符号”操作。 或把它当作如果它的整体操作的部分（即它的符号）。 我的意思是你遇到每次“ - ”，你就必须通过-1后乘以操作数，然后继续读下一个标记。 :)我希望帮助。 只是一个简单的想法...

Answer 3:

我可以通过修改元运算符解决这个问题（“+”和“ - ”），从二进制的区分。

例如，我叫一元减“m”和一元加号“+”，使他们的权利，assocative及其优先级等于指数运算符（“^”）。

为了检测是否操作是一元的，我只是不得不检查操作之前标记为操作员或左括号。

这是我在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);
        }

这里运营商是一个堆栈和令牌是一个迭代中缀表达式串

（这只是运营商处理部分）

Answer 4:

当我需要支持这一点，我在中间阶段这样做。 我开始产生的所有表达的词位列表，然后使用辅助函数来提取运算符和操作数和“获取操作数”功能，只需消耗2个词素每当它看到了一元运算符。

这真的帮助，如果您使用其它字符来表示“一元减”，虽然。

Answer 5:

在我的Java实现，我做到了在接下来的方式：

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

文章来源: How can I modify my Shunting-Yard Algorithm so it accepts unary operators?