分流码算法的问题 [英] Problems with a shunting yard algorithm

问题描述

我已经在java中成功实现了一个调车场算法。算法本身很简单但是我在使用tokenizer时遇到了麻烦。目前，该算法适用于我想要的一切，不包括一件事。如何判断减法（ - ）和否定（ - ）

I have successfully implemented a shunting yard algorithm in java. The algorithm itself was simple however I am having trouble with the tokenizer. Currently the algorithm works with everything I want excluding one thing. How can I tell the difference between subtraction(-) and negative (-)

之间的区别，例如4-3是减法
但-4 + 3是负数

such as 4-3 is subtraction but -4+3 is negative

我现在知道如何找出它应该是负数何时应该是负数，但算法应放在哪里，因为如果你使用它就像例如，它不会一直有效的功能

I now know how to find out when it should be a negative and when it should be a minus, but where in the algorithm should it be placed because if you use it like a function it wont always work for example

3 + 4 * 2 / - （1 - 5）^ 2 ^ 3

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

当1-5变为-4时，它将变为4，然后变为平方和立方

when 1-5 becomes -4 it will become 4 before it gets squared and cubed

就像
3 + 4 * 2 / cos（ 1 - 5）^ 2 ^ 3，你会在平方和立方之前取余弦

just like 3 + 4 * 2 / cos( 1 − 5 ) ^ 2 ^ 3 , you would take the cosine before squaring and cubing

但是在实际数学中你不会用 - 因为你真正说的是
3 + 4 * 2 / - （（1 - 5）^ 2 ^ 3）为了拥有正确的价值

but in real math you wouldn’t with a - because what your really saying is 3 + 4 * 2 / -(( 1 − 5 ) ^ 2 ^ 3) in order to have the right value

推荐答案

听起来你正在做一个lex-then-parse风格的解析器，你需要在lexer中使用一个简单的状态机才能分开一元和二元减去。 （在PEG解析器中，这不是你必须担心的。）

It sounds like you're doing a lex-then-parse style parser, where you're going to need a simple state machine in the lexer in order to get separate tokens for unary and binary minus. (In a PEG parser, this isn't something you have to worry about.)

在JavaCC中，你将有一个 DEFAULT 州，您可以将 - 字符视为 UNARY_MINUS 。当您对主表达式的结尾（基于您给出的示例的结束表达式或整数）进行标记时，您将切换到 INFIX 状态，其中 - 将被视为 INFIX_MINUS 。一旦遇到任何中缀运算符，您将返回 DEFAULT 状态。

In JavaCC, you would have a DEFAULT state, where you would consider the - character to be UNARY_MINUS. When you tokenized the end of a primary expression (either a closing paren, or an integer, based on the examples you gave), then you would switch to the INFIX state where - would be considered to be INFIX_MINUS. Once you encountered any infix operator, you would return to the DEFAULT state.

如果你正在自己滚动，它可能比这更简单。请查看此 Python代码，以获得巧妙的方法。基本上，当您遇到 - 时，您只需检查以前的令牌是否为中缀运算符。该示例使用字符串 - u来表示一元减号，这样便于非正式标记化。我可以说，最好的Python示例无法处理 - 跟随打开的paren或输入开头的情况。那些也应该被认为是一元的。

If you're rolling your own, it might be a bit simpler than that. Look at this Python code for a clever way of doing it. Basically, when you encounter a -, you just check to see if the previous token was an infix operator. That example uses the string "-u" to represent the unary minus token, which is convenient for an informal tokenization. Best I can tell, the Python example does fail to handle case where a - follows an open paren, or comes at the beginning of the input. Those should be considered unary as well.

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

In order for unary minus to be handled correctly in the shunting-yard algorithm itself, it needs to have higher precedence than any of the infix operators, and it needs to marked as right-associative. (Make sure you handle right-associativity. You may have left it out since the rest of your operators are left-associative.) This is clear enough in the Python code (although I would use some kind of struct rather than two separate maps).

当需要进行评估时，您需要稍微改变一元运算符，因为您只需要从堆栈中弹出一个数字，而不是两个。根据您的实现情况，可能更容易通过列表并用 [ - 1替换 - u的每一次出现，*] 。

When it comes time to evaluate, you will need to handle unary operators a little differently, since you only need to pop one number off the stack, rather than two. Depending on what your implementation looks like, it may be easier to just go through the list and replace every occurrence of "-u" with [-1, "*"].

如果你可以完全关注Python，你应该能够看到我在谈论的所有内容。我联系的例子。我发现代码比其他人提到的C版本更容易阅读。另外，如果你很好奇的话，我在前一段时间做了一些关于使用调车场的文章，但是我将一元运算符作为单独的非终结符号处理，因此它们不会显示。

If you can follow Python at all, you should be able to see everything I'm talking about in the example I linked to. I find the code to be a bit easier to read than the C version that someone else mentioned. Also, if you're curious, I did a little write-up a while back about using shunting-yard in Ruby, but I handled unary operators as a separate nonterminal, so they are not shown.

这篇关于分流码算法的问题的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！