4

我正在尝试实现一个没有括号的Shutting-yard算法，但我无法理解它。我试过维基百科，但条目真的很糟糕。我在实现代码时应该没有什么问题，但如果我不明白，我就无法实现它。

现在：这个算法是如何工作的？

以下是我的理解：

  • 从左到右，所有数字都添加到输出队列中，所有操作数都添加到堆栈中。到达末尾后，您将弹出所有操作数并将它们添加到输出中

    Expression: 2+5*4+3/5   ( = 2+20+0.6 = 22.6 )

Stack: +*+/             ( -> top )

OutputQueue: 5 3 4 5 2  ( -> exits)

现在我弹出堆栈并将其添加到队列中

    OutputQueue: (insert ->) + * + / 5 3 4 5 2   ( -> exit)

据我了解，表格应该是：25435/+*+

让我们尝试解决它：

    5/3 ~ 1.6 + 4 ~= 5.6 * 5 ~= 28 + 2 ~= 30 (or 30.3 recurring .3 if you insist)

编辑：我确信我在这里使用的反向波兰符号是正确的，所以这不应该是问题。

我知道我在做一些愚蠢的事情，但对于我的一生，我无法弄清楚。

我认为如果有人能指出我的逻辑中的错误，那将很有帮助，因为算法应该很好，因为它来自维基百科，而且我看到其他人向我指出了它。所以它必须是好的，我只是在某个地方搞砸了。

是队列吗？我很确定我可以很好地处理逆波兰符号。

4

2 回答 2

4

你理解错了 ：

Expression: 2+5*4+3/5

对于每个令牌：

    token : 2
    outputqueue 2
    stack

    token : +
    outputqueue 2
    stack +

    token : 5
    outputqueue 25
    stack +

    token : "*" 
    "*" has higher predencence as "+", so we push into the stack
    outputqueue 25
    stack +*

    token : 4
    outputqueue 254
    stack +*

    token : "+"
    "+ "has lower predencence as "*", we pop "*" from the stack.
    "+" has same predecence as "+", so we pop "+" from the stack then add the current  token "+" in the stack
    outputqueue 254*+
    stack +

    token : 3
    outputqueue 254*+3
    stack +

    token : "/"
    "/" has lower predencence as "+", we push "/" into the stack
    outputqueue 254*+
    stack +/

    token : 5
    outputqueue 254*+35
    stack +/

表达式结束，出栈：

output 254*+35/+

计算 ：

5*4 = 20
2+20 = 22
3/5 = 0.6
22 + 0.6 = 22.6
于 2012-06-11T11:41:46.313 回答
2

我不太确定您想要的算法是否如此简单 - 您是否阅读了您链接到的整个 wiki 文章？具体来说，请参阅“算法详细信息”部分，其中很多涉及运算符优先级，我认为您在当前的实现中将其丢弃。我的建议是按照要点（并根据需要与下面的示例进行比较）一次一步地浏览该部分，以尝试为该问题提出适当的形式。一旦你这样做了，它应该有望帮助你对算法的总体理解。

于 2012-06-11T11:38:39.503 回答