C++数据结构学习:用栈做表达式求值

栈的应用很广泛，原书只讲解了表达式求值，那我也就只写这些。其实，栈的最大的

用途是解决回溯问题，这也包含了消解递归；而当你用栈解决回溯问题成了习惯的时候 ，

你就很少想到用递归了，比如迷宫求解。另外，人的习惯也是先入为主的，比如树的遍历，

从学的那天开始，就是递归算法，虽然书上也教了用栈实现的方法，但应用的时候，你

首先想到的还是递归；当然了，如果语言本身不支持递归（如 BASIC），那栈就是唯一

——

的选择了

好像现在的高级语言都是支持递归的。

 

　　 如下是表达式类的定义和实现，表达式可以是中缀表示也可以是后缀表示，用头节

点数据域里的 type 区分，这里有一点说明的是，由于单链表的赋值函数，我原来写的时

候没有复制头节点的内容，所以，要是在两个表达式之间赋值，头节点里存的信息就丢

了。你可以改写单链表的赋值函数来解决这个隐患，或者你根本不不在两个表达式之间赋

值也行。

 

　　 #ifndef Expression_H

 

　　 #define Expression_H

 

　　 #include "List.h"

 

　　 #include "Stack.h"

 

　　 #define INFIX 0

 

　　 #define POSTFIX 1

 

　　 #define OPND 4