调车场算法存在的问题

Question

我已经成功地用java实现了一个调车场算法。算法本身很简单，但是我在使用标记器时遇到了问题。目前，该算法适用于我想要的所有东西，除了一件事。如何区分减法(-)和负数(-)

例如4-3是减法，但-4+3是负数

我现在知道如何找出什么时候应该是负数，什么时候应该是负数，但是它应该放在算法中的什么位置，因为如果你像使用函数一样使用它，它并不总是有效的，例如

3+4*2/ -( 1−5)^2^3

当1-5变成-4时，它在平方和立方之前会变成4

就像3+4*2/ cos( 1−5)^2^3一样，你可以在平方和立方体之前取余弦

但在真正的数学中，你不会使用-，因为你真正说的是3+4*2/ -(( 1−5)^2^3)，以获得正确的值

Answer 1

这听起来像是在做一个lex-then-parse风格的解析器，在这个解析器中，您需要在lexer中使用一个简单的状态机，以便为一元减号和二进制减号获得不同的标记。(在PEG解析器中，这不是您必须担心的事情。)

在JavaCC中，您会有一个DEFAULT状态，在此状态下，您会认为-字符为UNARY_MINUS。当您对主表达式的末尾进行标记时(根据您给出的示例，可以是闭合的paren，也可以是整数)，然后切换到INFIX状态，在该状态下，-将被视为INFIX_MINUS。一旦您遇到任何中缀操作符，您就会返回到DEFAULT状态。

如果你正在使用你自己的，它可能会比这简单一点。看看这个Python code，这是一种聪明的方式。基本上，当您遇到-时，您只需检查前一个令牌是否为中缀运算符。该示例使用字符串"-u"来表示一元减号标记，这对于非正式的标记化很方便。据我所知，Python示例不能处理-跟在一个开放的paren后面，或者出现在输入的开头的情况。这些也应该被认为是一元的。

为了在分车码算法本身中正确处理一元减号，它需要比任何中缀操作符具有更高的优先级，并且需要标记为右关联。(请确保处理右关联性。您可能遗漏了它，因为您的其余运算符都是左关联的。)这在Python代码中已经很清楚了(尽管我会使用某种结构，而不是两个单独的映射)。

在进行计算时，您需要以稍微不同的方式处理一元运算符，因为您只需要从堆栈中弹出一个数字，而不是两个。根据您的实现情况，只查看列表并用[-1, "*"]替换所有出现的"-u"可能会更容易。

如果您能够使用Python，那么您应该能够看到我在链接的示例中讨论的所有内容。我发现代码比其他人提到的C版本更容易阅读。另外，如果你感兴趣，我写了一些关于使用调车场in Ruby的文章，但是我把一元运算符作为一个单独的非终结符来处理，所以它们没有显示出来。

Answer 2

this question的答案可能会有所帮助。

特别是，其中一个答案引用了C中处理一元减号的solution。

基本上，你必须根据负号在二元运算符不能出现的位置上的出现来识别一元减号，并为它制作一个不同的标记，因为它具有不同的优先级。

Dijkstra的original paper没有太清楚地解释他是如何处理这个问题的，但是一元减号被作为一个单独的运算符列出。

Answer 3

在您的lexer中，您可以实现这个伪逻辑：

if (symbol == '-') {
    if (previousToken is a number 
     OR previousToken is an identifier 
     OR previousToken is a function) {
        currentToken = SUBTRACT;
    } else {
        currentToken = NEGATION;
    }
}

您可以设置求反，使其优先级高于乘除，但低于求幂。您也可以将其设置为右关联(就像‘^’一样)。然后，您只需将优先级和关联性集成到算法中，如维基百科页面所述。

如果标记是运算符o1，则为

，则:当堆栈顶部有一个运算符标记o2时，或者o1是左关联的且其优先级小于或等于o2，或者o1的优先级低于o2，则将o2从堆栈中弹出到输出队列上；将o1推送到堆栈上。

我最终实现了相应的代码：

} else if (nextToken instanceof Operator) {
    final Operator o1 = (Operator) nextToken;

    while (!stack.isEmpty() && stack.peek() instanceof Operator) {
        final Operator o2 = (Operator) stack.peek();

        if ((o1.associativity == Associativity.LEFT && o1.precedence <= o2.precedence)
         || (o1.associativity == Associativity.RIGHT && o1.precedence < o2.precedence)) {
            popStackTopToOutput();
        } else {
            break;
        }
    }

    stack.push(nextToken);
}

Austin Taylor是非常正确的，你只需要为一元运算符弹出一个数字：

if (token is operator negate) {
    operand = pop;
    push operand * -1;
}

示例项目：

https://github.com/Digipom/Calculator-for-Android/

进一步阅读：

http://en.wikipedia.org/wiki/Shunting-yard_algorithm

http://sankuru.biz/blog/1-parsing-object-oriented-expressions-with-dijkstras-shunting-yard-algorithm