将中缀表达式转换为后缀表达式
- 格式：doc
- 大小：76.50 KB
- 文档页数：4
5 将中缀表达式转换为后缀表达式
【问题描述】表达式转换。
输入的中缀表达式为字符串，转换得到的后缀表达式存入字符数组中并输出。
例如：a*(x+y)/(b-x) 转换后得： a x y + * b x - /
【数据结构】
●定义一个暂时存放运算符的转换工作栈opst。
●中缀表达式字符串char *infix;
●后缀表达式字符串char *postfix;
【算法提示】转换规则：把运算符移到它的两个操作数后面，删除掉所有的括号。
从头到尾扫描中缀表达式，对不同类型的字符按不同情况处理：
●数字或小数点，直接写入字符串postfix，并在每个数值后面写入一个空格；
●左括号，进栈，直到遇见相配的右括号，才出栈；
●右括号，表明已扫描过括号内的中缀表达式，把从栈顶直到对应左括号之间的运算
符依次退栈，并把结果推入栈内；
●对于运算符，分两种情况处理：
◆该运算符的优先级大于栈顶符号的优先级，则入栈；
◆若该运算符的优先级小于栈顶优先级，则先弹出栈顶运算符、写入postfix串；继续将该
运算符与栈顶运算符比较，直到能把它推入栈内为止（即优先级大于栈顶运算符）。
说明：自行设计运算符优先级的表示。
【主要代码】#include<iostream>
#define QMAX 30 //设栈空间最大为30单元
using namespace std;
class Stack{
private:
char st[QMAX]; //像素类型的栈空间
int top; //栈顶
public:
Stack(){top=-1;}
void push(char &e); //像素e进栈
void pop(char &e); //出栈一个像素
int IsEmpty(); //判断栈是否为空，若空则返回1，否则返回0
void GetTop(char& ch1); //取栈顶值
};
void Stack::push(char &e){ // 像素e进栈
if(top==QMAX) exit(1);
top++;
st[top]=e;
}
void Stack::pop(char &e){ //出栈一个像素，由e返回
if(top==-1) exit(1);
e=st[top];
top--;
}
int Stack::IsEmpty(){ //判断栈是否为空
if(top==-1) return 1;
else return 0;
}
void Stack::GetTop(char& ch1 ) //取栈顶值
{
if(IsEmpty()) exit(1);
ch1=st[top];
}
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=c[i++]; //栈底放一个字符#,读入一个字符
while(s.IsEmpty()==0&&ch!='#') //栈不空且中缀表达式未读完，连续处理{
if(isdigit(ch)){cout<<ch;ch=c[i++];} //是数字，输出并读取一个字符
else
{
cout<<" ";
s.GetTop(ch1); //读取栈顶元素ch1
if(isp(ch1)<icp(ch)) //新输入字符优先级高
{s.push(ch);ch=c[i++];}
else if (isp(ch1)>icp(ch)) //新输入字符优先级低
{s.pop(op);if(op!='('&&op!=')') cout<<op;}
else
{
s.pop(op); //新输入字符优先级等于栈顶字符，退栈不输出
}
}
}
while(s.IsEmpty()==0&&ch=='#') //中缀表达式已读完，站内字符退栈{
cout<<" ";
s.GetTop(ch1); //读取栈顶元素ch1
if (isp(ch1)>icp(ch)) //新输入字符优先级低
{s.pop(op); if(op!='('&&op!=')')cout<<op;}
else
{
s.pop(op); //退栈
break; //结束循环
}
}
return;
}
void main() //主函数测试用
{
char infix[14],item;
cout<<"请输入表达式，输入#结束:"<<'\n';
cin>>item; //输入前缀表达式
for(int i=0;item!='#';i++)
{
infix[i]=item;
cin>>item;
}
infix[i]=item; //输入#
cout<<"转换后的后缀表达式为："<<'\n';
Postfix(infix); //转换中缀表达式为后缀
}
运行结果：
【实验过程】用栈来实现中缀表达式到后主表达式的转换，先看了一下实验指导书，没有相关实验，又看了一下课本，找到了一些指导，然后就开始写程序，把课本的函数修改了一下，写了主函数，运行后发现，结果不理想，那个函数不够严谨，很容易出错。
最后经过认真分析和调试，找出了问题，修改后，得到了满意的结果。
【实验体会】通过这次试验，我切身体会到了，编程不可偷懒，修改调试好别人一个的程序的时间，你可以自己写好几个好程序。
我相信这些感悟和体会和经验对以后编程将会有极大的帮助。
同时我对于栈也有了新的感悟，对于其独特作用有了更好的理解与认识。
