数据结构中缀表达式转后缀表达式.doc

中缀转后缀，后缀求值13070319张乐2015.4.211、 需求分析明确规定：需要运用栈来实现对中缀表达式转换为后缀表达式，并且再次输入后缀表达式，得出结果。输入形式、输入值的范围；中缀表达式的输入，操作数必须不为负数，并且表达式以=结束输入输出形式；第一次输出后缀表达式，接着输出后缀表达式求得的值程序功能；中缀表达式转换为后缀表达式，后缀表达式求值测试数据：10(20-10)+10=2、 概要设计 ADT定义:class arrStackprivate:int mSize; /栈最多存放元素个数int top;/栈顶指针T *st;/存栈元素的数组public:arrStack(int sizee) /创建定长顺序栈的实例mSize = sizee;top = -1;st =new TmSize;arrStack( ) arrStack( ) void clear( ) bool isEmpty( )bool push(const T item)bool pop(T& item) T& gettop() bool input()int trans()bool Caculator() 主程序流程:各程序模块间的调用关系；3、 详细设计实现ADT定义的数据类型:arrStack(int sizee) /创建定长顺序栈的实例mSize = sizee;top = -1;st =new TmSize; arrStack( ) /清空top = -1;arrStack( ) /销毁delete st;void clear( ) /清空top = -1;bool isEmpty( ) /若栈已空返回trueif(top=-1)return true;return false;bool push(const T item) /入栈 O(1)/*if (top=(mSize-1)/若上溢T *newst = new T mSize*2 ;/扩容到2倍for(int i = 0; i= top; i+)/复制newst i = st i ;delete st; /释放旧空间st = newst; /恢复stmSize *=2; /改写mSize*/st +top = item; /插入itemreturn true;bool pop(T& item) /出栈 O(1)if (top=-1)cout空栈不能删endl;return false;elseitem=st top- ;return true;T& gettop() /取栈顶O(1)if (top=-1)cout空栈不能读取endl;elsereturn st top ; bool input() char in; int i=0; cout请您输入您要转换的前缀表达式in; while(in!=) ai=in; cinin; i+; ai=; i=0; while(ai!=) coutai; i+; int trans() int i=0,j=0; char ch,e; ch=ai; while(ch!=) switch(ch) case (: push(ch); break; case +: case -: case /: case *: while(!isEmpty() & gettop()!=( & gettop()=0=9) bj+=ch; ch=a+i; while(!isEmpty() e=gettop(); bj+=e; pop(e); int k=0; coutendl您得到的后缀表达式为：endl; for (;kj;k+) coutbk ; return j;bool Caculator() /全局函数来计算后缀表达式 arrStacks(100); int newope,ope1,ope2,e; char c; coutendl请您输入您得到的后缀表达式(以输入等号结束):c,c!=) switch(c) case +: ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1+ope2);break; case -: ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1-ope2);break; case *: ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1*ope2);break; case /: ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1/ope2);break; default: cin.putback(c); cinnewope; s.push(newope); break; coutendl求得的值为：endl; e=s.gettop(); couteendl; s.pop(e);4、 调试分析调试中遇到的问题、如何解决、对设计与实现的分析讨论；调试过程中出现了中缀表达式转换为后缀表达式转换错误的问题，原因是操作符号优先级判断判断错。算法时空分析；O（n）5、 用户使用说明A. 按照提示输入中缀表达式B. 看到屏幕输出的后缀表达式C. 将屏幕输出的后缀表达式再次按照屏幕提示输入D. 看到屏幕输出的后缀表达式的值6、 测试结果列出测试用输入、输出；7、 源程序列出源程序清单：#include #includeusing namespace std;template class arrStackprivate:int mSize; /栈最多存放元素个数int top;/栈顶指针T *st;/存栈元素的数组public: char a100; char b100;arrStack(int sizee) /创建定长顺序栈的实例mSize = sizee;top = -1;st =new TmSize; arrStack( ) /清空top = -1;arrStack( ) /销毁delete st;void clear( ) /清空top = -1;bool isEmpty( ) /若栈已空返回trueif(top=-1)return true;return false;bool push(const T item) /入栈 O(1)/*if (top=(mSize-1)/若上溢T *newst = new T mSize*2 ;/扩容到2倍for(int i = 0; i= top; i+)/复制newst i = st i ;delete st; /释放旧空间st = newst; /恢复stmSize *=2; /改写mSize*/st +top = item; /插入itemreturn true;bool pop(T& item) /出栈 O(1)if (top=-1)cout空栈不能删endl;return false;elseitem=st top- ;return true;T& gettop() /取栈顶O(1)if (top=-1)cout空栈不能读取endl;elsereturn st top ; bool input() char in; int i=0; cout请您输入您要转换的前缀表达式in; while(in!=) ai=in; cinin; i+; ai=; i=0; while(ai!=) coutai; i+; int trans() int i=0,j=0; char ch,e; ch=ai; while(ch!=) switch(ch) case (: push(ch); break; case +: case -: case /: case *: while(!isEmpty() & gettop()!=( & gettop()=0=9) bj+=ch; ch=a+i; while(!isEmpty() e=gettop(); bj+=e; pop(e); int k=0; coutendl您得到的后缀表达式为：endl; for (;kj;k+) coutbk ; return j;bool Caculator() /全局函数来计算后缀表达式 arrStacks(100); int newope,ope1,ope2,e; char c; coutendl请您输入您得到的后缀表达式(以输入等号结束):c,c!=) switch(c) case +: ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1+ope2);break; case -: ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1-ope2);break; case *: ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s.push(ope1*ope2);break; case /: ope2=s.gettop();s.pop(e);ope1=s.gettop();s.pop(e);s