23

我一直致力于在 JavaScript 中为类实现 Shutting-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 程序，我还不习惯。

4

7 回答 7

14

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

如果您确实需要处理一元运算符（例如，括号表达式的一元否定），那么您必须：

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

我在另一个 SO question上写了一个关于处理一元减号的更彻底的解释。

于 2011-03-09T03:18:08.763 回答
4

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

于 2009-10-20T08:46:35.937 回答
2

我可以通过修改一元运算符（'+' 和 '-'）以将它们与二元运算符区分开来来解决这个问题。

例如，我将一元减'm'和一元加'p'称为右结合，并且它们的优先级等于指数运算符（'^'）。

要检测运算符是否是一元的，我只需检查运算符之前的标记是运算符还是左括号。

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

这里操作符是一个堆栈，令牌是中缀表达式字符串的迭代器

（这只是操作员处理部分）

于 2017-06-15T08:07:11.537 回答
1

当我需要支持这一点时，我在中间阶段这样做了。我首先生成所有表达式词位的列表，然后使用辅助函数来提取运算符和操作数，并且“获取操作数”函数只要看到一元运算符就简单地消耗两个词位。

不过，如果您使用另一个字符来表示“一元减号”，这真的很有帮助。

于 2009-10-20T08:48:46.930 回答
1

这不在 Javascript 中，但这是我在搜索并没有找到任何明确答案后专门解决此问题而编写的一个库。这可以满足您的所有需求，甚至更多：

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

它是一个运行修改后的分流场算法的 ruby​​ 库（以及用于检查它的测试平台），该算法还支持一元 ('-a') 和三元 ('a?b:c') 操作。它还执行 RPN、Prefix 和 AST（抽象语法树）——您的选择，并且可以评估表达式，包括产生可以处理任何变量评估的块（某种 lambda）的能力。只有 AST 做了全套的操作，包括处理短路操作的能力（例如 '||' 和 '?:' 等），但 RPN 确实支持一元。它还有一个灵活的优先级模型，包括 C 表达式或 Ruby 表达式（不一样）所做的优先级预设。测试台本身很有趣，因为它可以创建随机表达式，然后可以 eval() 并通过 libExpr 运行以比较结果。

它有相当的文档/评论，因此将这些想法转换为 Javascript 或其他语言应该不会太难。

一元运算符的基本思想是您可以根据先前的标记识别它们。如果前一个标记是运算符或左括号，则“可能的一元”运算符（+ 和 -）只是一元的，并且只能用一个操作数推送。重要的是，您的 RPN 堆栈区分一元运算符和二元运算符，以便它知道在评估时要做什么。

于 2022-01-12T02:51:28.403 回答
0

在我的 Java 实现中，我采用了以下方式：

expression = expression.replace(" ", "").replace("(-", "(0-")
                .replace(",-", ",0-");
        if (expression.charAt(0) == '-') {
            expression = "0" + expression;
        }
于 2012-03-12T19:03:41.787 回答
0

要处理浮点数，您可以将（数字部分）正则表达式更改为：

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

所以最终的正则表达式将是：

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

对于处理一元减号运算符，您可以将其更改为另一个字符，例如“u”。（正如- TGO在这里解释的那样）

我根据给出的链接为处理一元减号运算符编写的 javascript 代码是：

// 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('');
于 2020-10-31T23:41:28.760 回答