algorithm - 必须实现调车场算法，需要帮助理解它

Question

我正在尝试实现 Shunting-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)

编辑:我确定 Reverse Polish notation我在这里使用是正确的，所以这应该不是问题。

我知道我在做一些愚蠢的事情，但我这辈子都想不通。

我认为，如果有人能指出我逻辑中的错误，那将是最有帮助的，因为算法应该是好的，因为它来自维基百科，而且我已经看到其他人向我指出了它。所以它必须是好的，我只是在某处弄乱了一些东西。

是队列吗？我很确定我正在处理 Reverse Polish notation好吧。

Answer 1

你错了:

Expression: 2+5*4+3/5 

对于每个 token :

    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