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

我试图实现一个没有括号的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。

来源

2012-06-11 Kalec

你理解错了：

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-11 11:41:46

我不太确定你想要的算法是非常简单的 - 你读过你链接到的整个wiki文章吗？具体来说，请参阅“The algorithm in detail”部分，其中涉及运算符的优先级，我认为您在当前的实现中将会丢弃它。我的建议是按照要点逐步浏览该部分（并根据需要比较下面的示例），一步一步地尝试为此问题提出正确的形式。一旦你做完了，它应该有希望帮助你理解算法。

来源

2012-06-11 11:38:39 Tim

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

回答

相关问题