双栈算术是 E.W.Dijkstra 在 20 世纪 60 年代发明的一个非常简单的算法,通过使用两个栈。
一个保存运算操作符,一个保存值的方式,来实现算术运算。思路如下:
一个算术表达式通常由括号,运算符和数字组成,将表达式从左到右逐一按以下步骤处理:
- 如遇到
(忽略 - 遇到数字则压入专门保存数字的栈
- 遇到操作符则压入专门保存运算符的栈
- 遇到
), 从保存数字的栈中弹出两个数,然后从保存运算符的栈中弹出一个运算符,运算后将结果压入保存数字的栈
以 (1 +(( 2 + 3 )x ( 4 x 5 ))) 为例,如下图

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