将中缀表达式转换为后缀表达式
5 将中缀表达式转换为后缀表达式 【问题描述】表达式转换。输入的中缀表达式为字符串,转换得到的后缀表达式存入字符数组中并输出。
例如: a*(x+y)/(b-x) 转换后得: a x y + * b x - / 【数据结构】
, 定义一个暂时存放运算符的转换工作栈opst。
, 中缀表达式字符串char *infix;
, 后缀表达式字符串char *postfix;
【算法提示】转换规则:把运算符移到它的两个操作数后面,删除掉所有的括号。 从头到尾扫描中缀表达式,对不同类型的字符按不同情况处理:
, 数字或小数点,直接写入字符串postfix,并在每个数值后面写入一个空格;
, 左括号,进栈,直到遇见相配的右括号,才出栈;
, 右括号,表明已扫描过括号内的中缀表达式,把从栈顶直到对应左括号之间的运算
符依次退栈,并把结果推入栈内;
, 对于运算符,分两种情况处理:
, 该运算符的优先级大于栈顶符号的优先级,则入栈;
, 若该运算符的优先级小于栈顶优先级,则先弹出栈顶运算符、写入postfix串;继续将该
运算符与栈顶运算符比较,直到能把它推入栈内为止(即优先级大于栈顶运算符)。
说明:自行设计运算符优先级的表示。
【主要代码】#include
#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--;
1
}
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<icp(ch)) //新输入字符优先级低
{s.pop(op);if(op!='('&&op!=')') cout<icp(ch)) //新输入字符优先级低
{s.pop(op); if(op!='('&&op!=')')cout<>item; //输入前缀表达式
for(int i=0;item!='#';i++)
{
infix[i]=item;
cin>>item;
}
infix[i]=item; //输入#
cout<<"转换后的后缀表达式为:"<<'\n';
Postfix(infix); //转换中缀表达式为后缀
3
}
运行结果:
【实验过程】用栈来实现中缀表达式到后主表达式的转换,先看了一下实验指导
书
关于书的成语关于读书的排比句社区图书漂流公约怎么写关于读书的小报汉书pdf
,没有相关实验,又看了一下课本,找到了一些指导,然后就开始写程序,把课本的函数修改了一下,写了主函数,运行后发现,结果不理想,那个函数不够严谨,很容易出错。最后经过认真
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
和调试,找出了问题,修改后,得到了满意的结果。
【实验体会】通过这次试验,我切身体会到了,编程不可偷懒,修改调试好别人一个的程序的时间,你可以自己写好几个好程序。我相信这些感悟和体会和经验对以后编程将会有极大的帮助。
同时我对于栈也有了新的感悟,对于其独特作用有了更好的理解与认识。
4