表达式求值实验报告 (桂豪纵)

数据结构 课程设计 班级：11021001 姓名：桂豪纵 学号：2010302672 2012年7月12日 一、需求分析 设计一个程序，演示用算符优先法对算术表达式求值的过程。利用算符优先关系，实现对算术四则混合运算表达式的求值。 （1）输入的形式：表达式，例如2*(3+4)=或者2*(3+4)#； 包含的运算符只能有'+' 、'-' 、'*' 、'/' 、'('、 ')'； （2）输出的形式：运算结果，例如77，56.24； （3）程序所能达到的功能：对表达式求值并输出结果。 二、概要设计： 本课程设计需要用到抽象数据类型栈存储表达式。本部分给出栈的类型定义与表达式求值操作描述。 1、存储结构（顺序栈）： template class Sqstack { private: SElemType *base; SElemType *top; int stacksize; protected: public: Sqstack(); Status InitStack(); Status Push(SElemType e); Status Pop(SElemType *e); Status StackEmpty(); Status DestroyStack(); Status GetTop(SElemType *e); }; 2、基本操作： Status InitStack() 操作结果：初始化一个空栈s。 Status GetTop(SElemType *e) 操作结果：得到s的栈顶元素并用e带回。 Status Push(SElemType e) 操作结果：向栈s中压入元素e。 Status Pop(SElemType *e) 操作结果：弹出栈s栈顶元素，并用e带回。 Status StackEmpty(); 操作结果：判断栈是否为空，若空这返回TRUE，否则返回FLASE。 Status DestroyStack(); 操作结果：销毁整个栈。 三、详细设计 本部分主要给出表达式求值的实现算法 1、初始化一个空栈 template Status Sqstack ::InitStack() { base = (SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType)); if(!base) exit(OVERFLOW); top = base; stacksize = STACK_INIT_SIZE; return OK; } 2、读取栈顶元素 template Status Sqstack ::GetTop(SElemType *e) { if(top>base) { *e=*(top-1); return OK; } else return FALSE; } 3、向栈中压入元素e template Status Sqstack ::Push(SElemType e) { if(top-base>=stacksize) { base = (SElemType*)realloc(base,(stacksize+STACKINCREMENT)*sizeof(SElemType)); if(!base)exit(OVERFLOW); top = base+stacksize; stacksize+=STACKINCREMENT; } *(top)++=e; return OK; } 4、弹出栈顶元素 template Status Sqstack ::Pop(SElemType *e) { if(base == top) return ERROR; *e=*(--top); return OK; } 5、判断栈是否为空 template Status Sqstack ::StackEmpty() { if(top==base) return ERROR; else return FALSE; } 6、销毁栈 template Status Sqstack ::DestroyStack() { free(base); base = NULL; stacksize = 0; top = NULL; return OK; } 7、比较两运算符优先级 int compare(char p1,char p2) { switch(p1) { case '-': case '+': switch(p2) { case ')': case '+': case '-': case '*': case '/': return -1; case '(': case '#': return 1; } break; case '/': case '*': switch(p2) { case '+': case '-': case '(': case '#': return 1; case '*': case '/': case ')': return -1; } break; case '(': switch(p2) { case '+': case '-': case '*': case '/': case '(': case '#': return 1; case ')': return ERROR; } break; case ')': switch(p2) { case '+': case '-': case '*': case '/': return -1; case '(': return 0; case ')': return ERROR; case '#': return ERROR; } break; case '=': switch(p2) { case '+': case '-': case '*': case '/': case ')': return -1; case '(': return ERROR; } break; } return 0; } 8、四则运算 template T chengfa(T x1,T x2) { return x1*x2; } template T chufa(T x1,T x2) { return x1/x2; } template T jiafa(T x1,T x2) { return x1+x2; } template T jianfa(T x1,T x2) { return x1-x2; } 9、主函数进行表达式求值 #include "stdafx.h" #include #include "Stack.cpp" using namespace std; typedef float Type; int compare(char p1,char p2); template T chengfa(T x1,T x2); template T chufa(T x1,T x2); template T jiafa(T x1,T x2); template T jianfa(T x1,T x2); int _tmain(int argc, _TCHAR* argv[]) { Sqstack sqstack1; sqstack1.InitStack(); Sqstack sqstack2; sqstack2.InitStack(); sqstack2.Push('#'); char ch,tm,tempch; char e='#'; Type temp1,temp2; double j=1.0; bool point=false; Type t1; cin>>ch; tempch = '#'; while(ch!='='||e!='#') { if((ch>='0'&&ch<='9')||ch=='.') { if(ch=='.') { tempch='#'; point=true; } else { if((tempch>='0'&&tempch<='9')||tempch=='.') { if(point) { j=j/10; sqstack1.Pop(&t1); sqstack1.Push(t1+(ch-48)*j); } else { sqstack1.Pop(&t1); sqstack1.Push(t1*10+Type(ch-48)); } } else sqstack1.Push(Type(ch-48)); } } else { point=false; j=1.0; while(compare(ch,e)<0) { sqstack2.Pop(&tm); sqstack1.Pop(&temp1); sqstack1.Pop(&temp2); switch(tm) { case '+': sqstack1.Push(jiafa(temp1,temp2)); break; case '-': sqstack1.Push(jianfa(temp2,temp1)); break; case '*': sqstack1.Push(chengfa(temp2,temp1)); break; case '/': sqstack1.Push(chufa(temp2,temp1)); break; } sqstack2.GetTop(&e); } if(compare(ch,e)>0) { sqstack2.Push(ch); } else if(compare(ch,e)==0) { sqstack2.Pop(&tm); } sqstack2.GetTop(&e); } if(ch!='=') { tempch = ch; cin>>ch; } } sqstack1.GetTop(&temp1); cout<