E.W.Dijkstra 双栈算术求值

双栈算术是 E.W.Dijkstra 在 20 世纪 60 年代发明的一个非常简单的算法,通过使用两个栈。
一个保存运算操作符,一个保存值的方式,来实现算术运算。思路如下:

一个算术表达式通常由括号,运算符和数字组成,将表达式从左到右逐一按以下步骤处理:

  1. 如遇到 ( 忽略
  2. 遇到数字则压入专门保存数字的栈
  3. 遇到操作符则压入专门保存运算符的栈
  4. 遇到 ), 从保存数字的栈中弹出两个数,然后从保存运算符的栈中弹出一个运算符,运算后将结果压入保存数字的栈

(1 +(( 2 + 3 )x ( 4 x 5 ))) 为例,如下图

E.W.Dijkstra 双栈算术轨迹图


详情见 算法(第四版)81 页

0%