分流码算法的问题

Question

我已经在java中成功实现了一个分流码算法.算法本身很简单但是我在使用tokenizer时遇到了麻烦.目前,该算法适用于我想要的一切,不包括一件事.如何区分减法( - )和负数( - )之间的区别

例如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.当您对主表达式的结尾(基于您给出的示例的结束表达式或整数)进行标记时,您将切换到将被视为的INFIX状态.一旦遇到任何中缀运算符,您将返回该状态.-INFIX_MINUSDEFAULT

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

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

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

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

Answer 2

这个问题的答案可能会有所帮助。

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

基本上，您必须根据二元运算符无法出现的位置中减号的出现来识别一元减号，并为其创建不同的标记，因为它具有不同的优先级。

Dijkstra 的原始论文并没有太清楚地解释他是如何处理这个问题的，但一元减号被列为一个单独的运算符。