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

《数据结构中缀表达式转后缀表达式》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

2、){//创建定长顺序栈的实例mSize=sizee;top=-1;st=newT[mSize];}arrStack(){}~arrStack(){}voidclear(){}boolisEmpty(){}boolpush(constTitem){}boolpop(T&item){}T&gettop(){}boolinput(){}inttrans(){}boolCaculator(){}}主程序流程:各程序模块间的调用关系；1、详细设计实现ADT定义的数据类型:arrStack(intsizee){//创建定长顺序栈的实例mSize=sizee;top=-1;st=newT[mSize];}a

3、rrStack(){//清空top=-1;}~arrStack(){//销毁delete[]st;}voidclear(){//清空top=-1;}boolisEmpty(){//若栈已空返回trueif(top==-1)returntrue;returnfalse;}boolpush(constTitem)//入栈O(1){/*if(top==(mSize-1)){//若上溢T*newst=newT[mSize*2];//扩容到2倍for(inti=0;i<=top;i++)//复制newst[i]=st[i];delete[]st;//释放旧空间st=newst;//恢复stmSize*=

4、2;//改写mSize}*/st[++top]=item;//插入itemreturntrue;}boolpop(T&item)//出栈O(1){if(top==-1){cout<<"空栈不能删"<>in;while(in!='='

5、){a[i]=in;cin>>in;i++;}a[i]='=';i=0;while(a[i]!='='){cout<

6、pty()){while(gettop()!='('){e=gettop();b[j]=e;pop(e);j++;}}pop(e);break;default:if(ch>='0'<='9')b[j++]=ch;}ch=a[++i];}while(!isEmpty()){e=gettop();b[j++]=e;pop(e);}intk=0;cout<s(100);intnewop

7、e,ope1,ope2,e;charc;cout<>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()