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

5 将中缀表达式转换为后缀表达式【问题描述】表达式转换。输入的中缀表达式为字符串，转换得到的后缀表达式存入字符数组中并输出。例如： a*(x+y)/(b-x) 转换后得： a x y + * b x - /【数据结构】l 定义一个暂时存放运算符的转换工作栈opst。l 中缀表达式字符串char *infix;l 后缀表达式字符串char *postfix;【算法提示】转换规则：把运算符移到它的两个操作数后面，删除掉所有的括号。从头到尾扫描中缀表达式，对不同类型的字符按不同情况处理：l 数字或小数点，直接写入字符串postfix，并在每个数值后面写入一个空格；l 左括号，进栈，直到遇见相配的右括号，才出栈；l 右括号，表明已扫描过括号内的中缀表达式，把从栈顶直到对应左括号之间的运算符依次退栈，并把结果推入栈内；l 对于运算符，分两种情况处理：u 该运算符的优先级大于栈顶符号的优先级，则入栈；u 若该运算符的优先级小于栈顶优先级，则先弹出栈顶运算符、写入postfix串；继续将该运算符与栈顶运算符比较，直到能把它推入栈内为止（即优先级大于栈顶运算符）。说明：自行设计运算符优先级的表示。【主要代码】#include#define QMAX 30 /设栈空间最大为30单元using namespace std;class Stackprivate:char stQMAX; /像素类型的栈空间int top; /栈顶public:Stack()top=-1;void push(char &e); /像素e进栈void pop(char &e); /出栈一个像素int IsEmpty(); /判断栈是否为空，若空则返回1，否则返回0void GetTop(char& ch1); /取栈顶值;void Stack:push(char &e) / 像素e进栈if(top=QMAX) exit(1);top+;sttop=e;void Stack:pop(char &e) /出栈一个像素，由e返回if(top=-1) exit(1);e=sttop;top-;int Stack:IsEmpty() /判断栈是否为空if(top=-1) return 1;else return 0;void Stack:GetTop(char& ch1 ) /取栈顶值if(IsEmpty() exit(1);ch1=sttop;isdigit(char ch2) /判断是否为数字if(ch2=0&ch2=9) return 1;return 0;int isp(char a) /栈内优先数if(a=#) return 0;else if(a=() return 1;else if(a=*)|(a=/)|(a=%) return 5;else if(a=+)|(a=-) return 3;else if(a=) return 6;else exit(1);int icp(char b) /栈外优先数if(b=#) return 0;else if(b=() return 6;else if(b=*)|(b=/)|(b=%) return 4;else if(b=+)|(b=-) return 2;else if(b=) return 1;else cout表达式有错误：;exit(1);void Postfix(char c) /转换中缀表达式为后缀的函数Stack s; /定义栈对象int i=0,j=0;char ch=#,ch1,op;s.push(ch);ch=ci+; /栈底放一个字符#,读入一个字符while(s.IsEmpty()=0&ch!=#) /栈不空且中缀表达式未读完，连续处理if(isdigit(ch)coutch;ch=ci+; /是数字，输出并读取一个字符elsecout ;s.GetTop(ch1); /读取栈顶元素ch1if(isp(ch1)icp(ch) /新输入字符优先级低s.pop(op);if(op!=(&op!=) coutop;else s.pop(op); /新输入字符优先级等于栈顶字符，退栈不输出while(s.IsEmpty()=0&ch=#) /中缀表达式已读完，站内字符退栈couticp(ch) /新输入字符优先级低s.pop(op); if(op!=(&op!=)coutop;elses.pop(op); /退栈break; /结束循环return;void main() /主函数测试用char infix14,item;cout请输入表达式，输入#结束:item; /输入前缀表达式for(int i=0;item!=#;i+)infixi=item;cinitem;infixi=item; /输入#cout转换后的后缀表达式为：n;Postfix(infix); /转换中缀表达式为后缀运行结果：【实验过程】用栈来实现中缀表达式到后主表达式的转换，先看了一下实验指导书，没有相关实验，又看了一下课本，找到了一些指导，然后就开始写程序，把课本的函数修改了一下，写了主函数，运行后发现，结果不理想，那个函数不够严谨，很容易出错。最后经过认真分析和调试，找出了问题，修改后，得到了满意的结果。【实