将中缀表达式转换为后缀表达式

《将中缀表达式转换为后缀表达式》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、5将中缀表达式转换为后缀表达式【问题描述】表达式转换。输入的中缀表达式为字符串，转换得到的后缀表达式存入字符数组中并输出。例如：a*(x+y)/(b-x)转换后得：axy+*bx-/【数据结构】l定义一个暂时存放运算符的转换工作栈opst。l中缀表达式字符串char*infix;l后缀表达式字符串char*postfix;【算法提示】转换规则：把运算符移到它的两个操作数后面，删除掉所有的括号。从头到尾扫描中缀表达式，对不同类型的字符按不同情况处理：l数字或小数点，直接写入字符串postfix，并在每个数值后面写入一个空格；l左括号，进栈，直到遇见相配的右括号，才出栈；

2、l右括号，表明已扫描过括号内的中缀表达式，把从栈顶直到对应左括号之间的运算符依次退栈，并把结果推入栈内；l对于运算符，分两种情况处理：u该运算符的优先级大于栈顶符号的优先级，则入栈；u若该运算符的优先级小于栈顶优先级，则先弹出栈顶运算符、写入postfix串；继续将该运算符与栈顶运算符比较，直到能把它推入栈内为止（即优先级大于栈顶运算符）。说明：自行设计运算符优先级的表示。【主要代码】#include#defineQMAX30//设栈空间最大为30单元usingnamespacestd;classStack{private:charst[QMAX]

3、;//像素类型的栈空间inttop;//栈顶public:Stack(){top=-1;}voidpush(char&e);//像素e进栈voidpop(char&e);//出栈一个像素intIsEmpty();//判断栈是否为空，若空则返回1，否则返回0voidGetTop(char&ch1);//取栈顶值};voidStack::push(char&e){//像素e进栈if(top==QMAX)exit(1);top++;st[top]=e;}voidStack::pop(char&e){//出栈一个像素，由e返回if(top==-1)exit(1);e=st[t

4、op];top--;4}intStack::IsEmpty(){//判断栈是否为空if(top==-1)return1;elsereturn0;}voidStack::GetTop(char&ch1)//取栈顶值{if(IsEmpty())exit(1);ch1=st[top];}isdigit(charch2)//判断是否为数字{if(ch2>='0'&&ch2<='9')return1;return0;}intisp(chara)//栈内优先数{if(a=='#')return0;elseif(a=='(')return1;elseif((a=='*')

5、

6、(a=

7、='/')

8、

9、(a=='%'))return5;elseif((a=='+')

10、

11、(a=='-'))return3;elseif(a==')')return6;else{exit(1);}}inticp(charb)//栈外优先数{if(b=='#')return0;elseif(b=='(')return6;elseif((b=='*')

12、

13、(b=='/')

14、

15、(b=='%'))return4;elseif((b=='+')

16、

17、(b=='-'))return2;elseif(b==')')return1;else{cout<<"表达式有错误：";exit(1);}}

18、voidPostfix(charc[])//转换中缀表达式为后缀的函数{Stacks;//定义栈对象inti=0,j=0;charch='#',ch1,op;s.push(ch);ch=c[i++];//栈底放一个字符#,读入一个字符while(s.IsEmpty()==0&&ch!='#')//栈不空且中缀表达式未读完，连续处理{if(isdigit(ch)){cout<

19、级高{s.push(ch);ch=c[i++];}elseif(isp(ch1)>icp(ch))//新输入字符优先级低{s.pop(op);if(op!='('&&op!=')')cout<icp(ch))//新输入字符优先级低{s.pop(op);if(op!='('&&o