java分流_java – 分流码算法的问题

听起来你正在做一个lex-then-parse风格的解析器,你需要在lexer中使用一个简单的状态机来获得单一和二进制减号的单独标记. (在PEG解析器中,这不是你需要担心的事情.)

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

如果你自己滚动,它可能比这更简单.看看这个Python code是一个聪明的方法.基本上,当您遇到 – 时,您只需检查以前的令牌是否为中缀运算符.该示例使用字符串“-u”来表示一元减号令牌,这样便于非正式标记化.我能说的最好,Python示例确实无法处理a – 遵循开放式paren,或者来自输入开头的情况.那些也应该被认为是一元的.

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

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

如果您可以完全关注Python,那么您应该能够在我链接的示例中看到我正在谈论的所有内容.我发现代码比其他人提到的C版本更容易阅读.另外,如果你很好奇,我在前一段时间做了一些关于使用shunting-yard in Ruby的文章,但是我将一元操作符作为一个单独的非终结符号处理,所以它们没有显示出来.