栈应用后缀表达式计算.docx

后缀表达式计算LinkStack.cpp#includeusing namespace std;/单链表的结点结构体：template struct Node DataType data; Node *next; /带头结点的单链表类的声明template class LinkStack public: LinkStack( ) top=NULL; /构造函数 LinkStack( ); /析构函数 bool IsEmpty( ); /栈空操作 DataType GetTop ( ); /得到栈顶值操作 void Push( DataType x ); /进栈操作 DataType Pop( ); /出栈操作 private: Node *top;/析构函数,析构函数将单链表中所有结点的存储空间释放。template LinkStack : LinkStack( ) Node *q; while (top !=NULL) q = top; /暂存释放结点 top = top-next; /top指向被释放结点的下一个结点 delete q; /释放结点 cout链表已经删除。endl;/栈空返回true，否则返回falsetemplate bool LinkStack:IsEmpty() return (top=NULL)?true:false;/进栈操作template void LinkStack: Push( DataType x ) Node *s;s=new Node; /申请一个数据成为x的结点ss-data=x;s-next=top; top=s;/出栈操作template DataType LinkStack:Pop( ) Node *p; DataType x; if (IsEmpty() cout 栈空无值弹出 data; p=top;top=top-next;delete p;return x; ;/返回栈顶值操作 template DataType LinkStack:GetTop( ) if (IsEmpty() cout 栈空无值 data; ;PostExp.cpp#include LinkStack.h/后缀表达式计算的栈类声明template class PostExp public:PostExp( ) ; /构造函数 void Run( ); /执行表达式计算 void Clear( ); /清栈操作 private: LinkStack s; /栈对象svoid Enter( DataType num); /进栈操作bool In(char op); /判断操作数bool GetTwoOperands(DataType& operand1,DataType& operand2); /从栈中推出两个操作数void Compute(char op); /形成运算指令，进行计算;/进栈操作template void PostExp:Enter( DataType num)s.Push(num); /将操作数的值num进操作数栈/从栈中推出两个操作数template bool PostExp:GetTwoOperands(DataType& operand1,DataType& operand2) if(s.IsEmpty() /判断栈是否空cout 缺少右操作数 endl; return false;operand1=s.Pop();if(s.IsEmpty() cout 缺少左操作数 endl; return false;operand2=s.Pop(); /去左操作数return true;/形成运算指令，进行计算template void PostExp:Compute(char op)bool retult;DataType operand1,operand2;retult=GetTwoOperands(operand1,operand2); /取两个操作数if(retult=true) /如果操作数取成功，计算并进栈 switch( op ) case +: s.Push(operand2 + operand1); break; case -: s.Push(operand2 - operand1); break; case *: s.Push(operand2 * operand1); break; case /: if(operand1=0) cout 除数为零 endl; exit(1); else s.Push(operand2 / operand1); break; else s.LinkStack();/判断操作数template bool PostExp:In(char op) /判断操作数 switch( op ) /是操作符进行计算 case + : case - : case * : case / : return true; default : return false; /执行表达式计算template void PostExp:Run( )char ch;DataType newOperand;cout 输出后缀表达式，以#结束； ch,ch!=#) if(In(ch) Compute(ch); else /不是操作符，不进行计算 cin.putback(ch); /把字符放回操作流cinnewOperand; /从新读操作数Enter(newOperand); /将操作数放入栈中 if(! s.IsEmpty()cout 后缀表达式是： s.GetTop()end