使用逆波兰算法后，不理解如何处理输出结果的问题。

Question

我一直在查看维基页面：http://en.wikipedia.org/wiki/Shunting-yard_algorithm 我已经使用了代码示例来构建第一部分，基本上我现在可以将：3 + 4 * 2 / (1-5)^2^3转换为3 4 2 * 1 5 − 2 3 ^ ^ / + 但我不知道如何使用3 4 2 * 1 5 − 2 3 ^ ^ / +来获得3.00012207 维基上的示例代码和说明对我来说毫无意义。

请问有人能解释一下如何计算3 4 2 * 1 5 − 2 3 ^ ^ / +并得出答案吗？谢谢。我不需要一个代码示例，只需要一个好的解释或示例的分解。

虽然这没有什么关系，但我正在使用 .NET C#。

- Patrick Lorio

Answer 1

馈送场算法的目的是将其输出转换成逆波兰表示法，这样便于进行评估：

• 创建一个堆栈来保存值
• 当还有逆波兰表示法输入时：
  • 读取输入项
  • 如果它是一个值，则将其推入堆栈
  • 否则，它就是一个操作符；从堆栈中弹出值，对这些值执行操作，然后将结果推回去
• 当没有输入剩余时，如果表达式格式正确，则堆栈上应该恰好有一个值；这是评估结果。

- moonshadow

---

一个堆栈是一种适当的数据结构实现这一点，你建议在Java中使用哪种集合？LinkedList还是Deque？我知道Java有一个Stack<E>类，但我读过它不建议使用，因为同步。 - tonix

Answer 2

后缀表示法是你在使用HP计算器等设备进行数学运算时的方法。保持一个栈，每当你得到一个数字时，将其添加到栈顶。每当你得到一个运算符时，从栈顶消耗输入，然后将结果添加到栈顶。

token stack
      *empty*
 3    3         //push numbers...
 4    3 4
 2    3 4 2
 *    3 8       //remove 4 and 2, add 4*2=8
 1    3 8 1
 5    3 8 1 5
 -    3 8 -4
 2    3 8 -4 2
 3    3 8 -4 2 3
 ^    3 8 -4 8
 ...    ...

- hugomg

Answer 3

按照以下步骤从左到右处理元素3 4 2 * 1 5 − 2 3 ^ ^ / +：

1. 初始化一个用于保存数字的栈。
2. 如果元素是数字，则将其推入栈中。
3. 如果元素是操作符，则从栈中取出顶部的两个元素，对这两个元素应用操作符，并将结果推入栈中。

当到达末尾时，栈应该只剩下一个元素，即为最终结果。

- Ted Hopp

Answer 4

看起来我来晚了。

我看到这个问题后离题写了一些 Rosetta Code 的任务。碰巧 这个任务 可能是你想要的。它给出了逐个标记计算 RPN 表达式值时发生的注释表格。

以下是其输出的示例：

For RPN expression: '3 4 2 * 1 5 - 2 3 ^ ^ / +'

TOKEN           ACTION                 STACK      
3     Push num onto top of stack 3                
4     Push num onto top of stack 3 4              
2     Push num onto top of stack 3 4 2            
*     Apply op to top of stack   3 8              
1     Push num onto top of stack 3 8 1            
5     Push num onto top of stack 3 8 1 5          
-     Apply op to top of stack   3 8 -4           
2     Push num onto top of stack 3 8 -4 2         
3     Push num onto top of stack 3 8 -4 2 3       
^     Apply op to top of stack   3 8 -4 8         
^     Apply op to top of stack   3 8 65536        
/     Apply op to top of stack   3 0.0001220703125
+     Apply op to top of stack   3.0001220703125  

 The final output value is: '3.0001220703125'

- Paddy3118