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

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

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

2、op;//栈顶指针T*st;//存栈元素的数组public:arrStack(intsizee){//创建定长顺序栈的实例mSize=sizee;top=-1;st=newT[mSize];}文档实用arrStack(){}~arrStack(){}voidclear(){}boolisEmpty(){}boolpush(constTitem){}boolpop(T&item){}T&gettop(){}boolinput(){}inttrans(){}boolCaculator(){}}主程序流程:文档实用各程

3、序模块间的调用关系；1、详细设计文档实用实现ADT定义的数据类型:arrStack(intsizee){//创建定长顺序栈的实例mSize=sizee;top=-1;st=newT[mSize];}arrStack(){//清空top=-1;}~arrStack(){//销毁delete[]st;}voidclear(){//清空top=-1;}boolisEmpty(){//若栈已空返回trueif(top==-1)returntrue;returnfalse;}boolpush(constTitem)//入栈

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

5、se;}else{item=st[top--];returntrue;}}T&gettop()//取栈顶O(1){if(top==-1){cout<<"空栈不能读取"<>in;while(in!='='){a[i]=in;cin>>in;i++;}a[i]='=';i=0;while(a[i]!='='){cout<

6、trans(){inti=0,j=0;charch,e;ch=a[i];while(ch!='='){switch(ch){case'(':push(ch);文档实用break;case'+':case'-':case'/':case'*':{while(!isEmpty()&&gettop()!='('&&gettop()<=ch){e=gettop();b[j]=e;pop(e);j++;}push(ch);}break;case')':if(!isEmpty()){while(gettop()!='('){

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

8、t>s(100);intnewope,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)