欢迎来到天天文库
浏览记录
ID:44780297
大小:186.50 KB
页数:14页
时间:2019-10-28
《大数据结构中缀表达式转后缀表达式》由会员上传分享,免费在线阅读,更多相关内容在工程资料-天天文库。
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)
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)
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)
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)
此文档下载收益归作者所有