6

我一直在看维基页面：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

wiki上的示例代码和解释对我来说没有任何意义。

有人可以解释如何评估3 4 2 * 1 5 − 2 3 ^ ^ / +和产生答案。提前致谢。我不需要一个代码示例，只需要一个很好的解释或一个示例的分解。

没关系，但我正在使用.net C#。

4

4 回答 4

9

调车场算法的目的是它的输出是反向波兰表示法，这很容易评估：

  • 创建一个堆栈来保存值
  • 虽然左侧有反向波兰符号输入：
    • 读取输入项
    • 如果它是一个值，则将其压入堆栈
    • 否则为操作；从堆栈中弹出值，对这些值执行操作，将结果推回
  • 当没有输入时，如果表达式格式正确，则堆栈上应该只有一个值；这是评估结果。
于 2011-12-01T16:14:12.090 回答
8

后缀表示法是您在 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
 ...    ...
于 2011-12-01T16:12:48.027 回答
3

3 4 2 * 1 5 − 2 3 ^ ^ / +按如下方式从左到右处理元素：

  1. 初始化堆栈以保存数字。
  2. 如果元素是数字，则将其压入堆栈。
  3. 如果元素是运算符，则从堆栈中删除顶部的两个元素，将运算符应用于这两个元素，然后将结果压入堆栈。

当你到达最后，堆栈应该有一个元素，这将是结果。

于 2011-12-01T16:14:13.890 回答
2

我知道我参加聚会有点晚了。

我看到了这个问题，并开始为 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'
于 2011-12-03T07:34:36.417 回答