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

1、中缀转后缀，后缀求值13070319张乐2015.4.211、 需求分析明确规定：需要运用栈来实现对中缀表达式转换为后缀表达式，并且再次输入后缀表达式，得出结果。输入形式、输入值的范围；中缀表达式的输入，操作数必须不为负数，并且表达式以=结束输入输出形式；第一次输出后缀表达式，接着输出后缀表达式求得的值程序功能；中缀表达式转换为后缀表达式，后缀表达式求值测试数据：10(20-10)+10=2、 概要设计 ADT定义:class arrStackprivate:int mSize; /栈最多存放元素个数int top;/栈顶指针T *st;/存栈元素的数组public:arrStack(int

2、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 = -

3、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

4、; /释放旧空间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 t

5、op ; bool input() char in; int i=0; cout<<"请您输入您要转换的前缀表达式"<<endl; cin>>in; while(in!='=') ai=in; cin>>in; i+; ai='=' i=0; while(ai!='=') cout<<ai; i+; int trans() int i=0,j=0; char ch,e; ch=ai; while(ch!='=') switch(ch) case 

6、9;(': push(ch); break; case '+': case '-': case '/': case '*': while(!isEmpty() && gettop()!='(' && gettop()<=ch) e=gettop(); bj=e; pop(e); j+; push(ch); break; case ')': if (!isEmpty() while(gettop()!='(') e=gettop(); bj

7、=e; pop(e); j+; pop(e); break; default: if (ch>='0'<='9') bj+=ch; ch=a+i; while(!isEmpty() e=gettop(); bj+=e; pop(e); int k=0; cout<<endl<<"您得到的后缀表达式为："<<endl; for (;k<j;k+) cout<<bk<<' ' return j;bool Caculator() /全局函数来计算后缀表达式

8、 arrStack<int>s(100); int newope,ope1,ope2,e; char c; cout<<endl<<"请您输入您得到的后缀表达式(以输入等号结束):"<<endl; while(cin>>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.gett

9、op();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); cin>>newope; s.push

10、(newope); break; cout<<endl<<"求得的值为："<<endl; e=s.gettop(); cout<<e<<endl; s.pop(e);4、 调试分析调试中遇到的问题、如何解决、对设计与实现的分析讨论；调试过程中出现了中缀表达式转换为后缀表达式转换错误的问题，原因是操作符号优先级判断判断错。算法时空分析；O（n）5、 用户使用说明A. 按照提示输入中缀表达式B. 看到屏幕输出的后缀表达式C. 将屏幕输出的后缀表达式再次按照屏幕提示输入D. 看到屏幕输出的后缀表达式的值6、 测试结果列出

11、测试用输入、输出；7、 源程序列出源程序清单：#include <iostream>#include<string.h>using namespace std;template <class T>class arrStackprivate:int mSize; /栈最多存放元素个数int top;/栈顶指针T *st;/存栈元素的数组public: char a100; char b100;arrStack(int sizee) /创建定长顺序栈的实例mSize = sizee;top = -1;st =new TmSize; arrStack( ) /清空

12、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 *=

13、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=

14、0; cout<<"请您输入您要转换的前缀表达式"<<endl; cin>>in; while(in!='=') ai=in; cin>>in; i+; ai='=' i=0; while(ai!='=') cout<<ai; i+; int trans() int i=0,j=0; char ch,e; ch=ai; while(ch!='=') switch(ch) case '(': push(ch); break; case &

15、#39;+': case '-': case '/': case '*': while(!isEmpty() && gettop()!='(' && gettop()<=ch) e=gettop(); bj=e; pop(e); j+; push(ch); break; case ')': if (!isEmpty() while(gettop()!='(') e=gettop(); bj=e; pop(e); j+; pop(e); break; de

16、fault: if (ch>='0'<='9') bj+=ch; ch=a+i; while(!isEmpty() e=gettop(); bj+=e; pop(e); int k=0; cout<<endl<<"您得到的后缀表达式为："<<endl; for (;k<j;k+) cout<<bk<<' ' return j;bool Caculator() /全局函数来计算后缀表达式 arrStack<int>s(100); int n

17、ewope,ope1,ope2,e; char c; cout<<endl<<"请您输入您得到的后缀表达式(以输入等号结束):"<<endl; while(cin>>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)