数据结构学习（C++）—栈应用（表达式求值）

　　　　　　　　　　　　　　　　　　happycock（原作）

　　栈的应用很广泛，原书只讲解了表达式求值，那我也就只写这些。其实，栈的最大的用途是解决回溯问题，这也包含了消解递归；而当你用栈解决回溯问题成了习惯的时候，你就很少想到用递归了，比如迷宫求解。另外，人的习惯也是先入为主的，比如树的遍历，从学的那天开始，就是递归算法，虽然书上也教了用栈实现的方法，但应用的时候，你首先想到的还是递归；当然了，如果语言本身不支持递归（如BASIC），那栈就是唯一的选择了——好像现在的高级语言都是支持递归的。

　　如下是表达式类的定义和实现，表达式可以是中缀表示也可以是后缀表示，用头节点数据域里的type区分，这里有一点说明的是，由于单链表的赋值函数，我原来写的时候没有复制头节点的内容，所以，要是在两个表达式之间赋值，头节点里存的信息就丢了。你可以改写单链表的赋值函数来解决这个隐患，或者你根本不不在两个表达式之间赋值也行。

#ifndef Expression_H
#define Expression_H
 
#include "List.h"
#include "Stack.h"
 
#define INFIX 0
#define POSTFIX 1
#define OPND 4
#define OPTR 8
 
template <class Type> class ExpNode
{
public:
 int type;
 union { Type opnd; char optr;};
 ExpNode() : type(INFIX), optr('=') {}
 ExpNode(Type opnd) : type(OPND), opnd(opnd) {}
 ExpNode(char optr) : type(OPTR), optr(optr) {}
};
 
template <class Type> class Expression : List<ExpNode<Type> >
{
public:
 void Input()
 {
 MakeEmpty(); Get()->type =INFIX;
  cout << endl << "输入表达式，以＝结束输入" << endl;
  Type opnd; char optr = ' ';
  while (optr != '=')
  {
   cin >> opnd;
   if (opnd != 0)
   {
    ExpNode<Type> newopnd(opnd);
    LastInsert(newopnd);
   }
   cin >> optr;
   ExpNode<Type> newoptr(optr);
   LastInsert(newoptr);
   
  }
 }