中缀表达式转后缀表达式并计算结果(C语言版)

5 将中缀表达式转换为后缀表达式【问题描述】表达式转换。

输入的中缀表达式为字符串，转换得到的后缀表达式存入字符数组中并输出。

例如：a*(x+y)/(b-x) 转换后得：a x y + * b x - /【数据结构】●定义一个暂时存放运算符的转换工作栈opst。

●中缀表达式字符串char *infix;●后缀表达式字符串char *postfix;【算法提示】转换规则：把运算符移到它的两个操作数后面，删除掉所有的括号。

从头到尾扫描中缀表达式，对不同类型的字符按不同情况处理：●数字或小数点，直接写入字符串postfix，并在每个数值后面写入一个空格；●左括号，进栈，直到遇见相配的右括号，才出栈；●右括号，表明已扫描过括号内的中缀表达式，把从栈顶直到对应左括号之间的运算符依次退栈，并把结果推入栈内；●对于运算符，分两种情况处理：◆该运算符的优先级大于栈顶符号的优先级，则入栈；◆若该运算符的优先级小于栈顶优先级，则先弹出栈顶运算符、写入postfix串；继续将该运算符与栈顶运算符比较，直到能把它推入栈内为止（即优先级大于栈顶运算符）。

说明：自行设计运算符优先级的表示。

【主要代码】#include<iostream.h>#include<assert.h>#include<math.h>#include<string.h>const int stackIncreament=0;class opst{public:opst(int sz=50){maxSize=sz;top=-1;elements=new char[maxSize];assert(elements!=NULL);}~opst(){delete[]elements;}bool IsEmpty(){return (top==-1)?true:false;} bool IsFull(){return(top==maxSize-1)?true:false;}void Push( char &x);bool Pop(char &x);bool getTop(char &x);int getSize()const{return top+1;}void MakeEmpty(){top=-1;}void input();void Convert();friend ostream& operator<<(ostream &os,opst &s);private:char *elements;int top;int maxSize;void overflowProcess();};void opst::overflowProcess()//溢出处理{char *newArray=newchar[maxSize+stackIncreament];for(int i=0;i<=top;i++)newArray[i]=elements[i];maxSize=maxSize+stackIncreament; delete [] elements;elements=newArray;}void opst::Push(char &x){if(IsFull()==true) overflowProcess(); elements[++top]=x;}bool opst::Pop( char &x){if(IsEmpty()==true) return false;x=elements[top--];return true;}bool opst::getTop(char &x){if(IsEmpty()==true)return false;x=elements[top];return true;}ostream& operator<<(ostream &os,opst &s) {os<<"top=="<<s.top<<endl;for(int i=0;i<=s.top;i++)os<<s.elements[i];return os;}void opst::input(){char ch[20];cout<<"请输入中缀表达式(括号不能省略)："<<endl;cin.getline(ch,20);int i=0;while(ch[i]!='\0'){this->Push(ch[i]);i++;}ch[i]='#';}bool isdigit(char &x){if((x>='a'&&x<='z')||(x>='A'&&x<='Z')||(x>=' 0'&&x<='9'))return true;else return false;}int isp(char &x)//设置栈内优先级{switch(x){case '#':{return 0;break;}case '(':{return 1;break;}case '*':case '/':case '%':{return 5;break;}case '+':case '-':{return 3;break;}case ')':{return 6;break;}}}int icp(char &x)//设置栈外优先级{switch(x){case '#':{return 0;break;}case '(':{return 6;break;}case '*':case '/':case '%':{return 4;break;}case '+':case '-':{return 2;break;}case ')':{return 1;break;}}}void opst::Convert(){opst s;int i=0;char ch='#',ch1,op;s.Push(ch);this->Push(ch);elements[i];while(this->IsEmpty()==false&&elements[i]! ='#'){if(isdigit(elements[i])){cout<<elements[i];i++;}else{s.getTop(ch1);if(isp(ch1)<icp(elements[i])){s.Push(elements[i]);i++;}else if(isp(ch1)>icp(elements[i])){s.Pop(op);cout<<op;}else{s.Pop(op);if(op=='(') i++;}}}}void main(){opst a;a.input();cout<<"后缀表达式为："<<endl;a.Convert();cout<<endl;}【实验过程】请输入中缀表达式（括号不能省略）：(a+((b-c)/d))后缀表达式为：abc-d/+【实验体会】怎么样设置栈内外的优先级是解决这个程序的关键，我是用了开关语句来实现的。

第3章堆栈和队列39 c=getchar();}if(Top(S, &newop))printf("%f", newop); //取栈顶元素，得结果输出Destroy(S); //释放堆栈创建时动态申请的空间}若输入的后缀表达式为6 4 2 − / 3 2 * +，则计算结果为9。

设后缀中的符号数为n（表达式中操作数、操作符和界限符的总数）。

不难看出，函数GetOperands()和DoOperator()的时间复杂度均为O(1)。

主函数main()对输入的表达式只进行一次扫描，所以其时间复杂度为O(n)。

3.3.3 中缀表达式转换为后缀表达式由于后缀表达式具有计算简便等优点，编译程序中常将中缀表达式转换为后缀表达式。

这种转换也是栈应用的一个典型例子。

从表3.2中可以看出，在中缀和后缀两种形式中，操作数的顺序是相同的。

因此很容易得到转换过程：（1）从左到右逐个扫描中缀表达式中各项，遇到结束符“#”转（6），否则继续；（2）遇到操作数直接输出；（3）若遇到右括号“）”，则连续出栈输出，直至遇到左括号“（”为止（注意：左括号出栈但并不输出），否则继续；（4）若是其他操作符，则和栈顶的操作符比较优先级，若小于等于栈顶操作符的优先级，则连续出栈输出，直到大于栈顶操作符的优先级结束，操作符进栈；（5）转（1）继续；（6）输出栈中剩余操作符（#除外）。

实现这个转换的关键是确定操作符的优先级，因为优先级决定了操作符是否进、出栈。

操作符在栈内外的优先级应该有所不同，以体现中缀表达式同优先级操作符从左到右的计算要求。

左括号的优先级在栈外最高，但进栈后应该比除“#”外的操作符低，可使括号内的其他操作符进栈。

为此，设计了栈内优先级isp(in-stack priority)和栈外优先级icp(incoming priority)，如表3.4所示。

表3.4 操作符的栈内外优先级表3.5所示为中缀表达式a/(b−c)+d*e转换为后缀表达式abc−/de*+的方法。

1.问题描述（1）表达式求值问题表达式是数据运算的基本形式。

人们的书写习惯是中缀式，如：11+22*(7-4)/3 。

中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。

表达式还有后缀式（如：2274-*3/11+）和前缀式（如： + 11 / * 22–7 4 3）。

后缀表达式和前缀表达式中没有括号，给计算带来方便。

如后缀式计算时按运算符出现的先后进行计算。

本设计的主要任务是进行表达式形式的变换及不相同形式的表达式计算。

2.数据结构设计（ 1）表达式求值问题由于表达式中有字符与数字两各种类，故定义结点一个标志域 data ，标志结点储藏的为字符 data=2 还是数字 data=1 ，再搜寻结点中对应的储藏地址，读取数字域 data1, 字符域 data2 。

而在前缀表达式时，存在表达式逆序，因表达式种类不一致，用栈逆序极不方便，选择成立双向链表，储藏表达式。

typedef struct Node//定义储藏中缀表达式的结点种类{int data;int data1;char data2;struct Node *next;}Lnode;typedef struct Node2//定义储藏前缀表达式的结点种类{int data;int data1;char data2;struct Node2 *next;struct Node2 *prior;}Lnode2;3. 运行、测试与解析（ 1）表达式求值问题（1）按提示输入中缀表达式，以下列图。

如输入中缀表达式不正确，提示输入有误，如图 , 所示。

图图图（2）选择表达式变换并求值方式。

按“1”选择中缀表达式求值，以下列图。

图（3）按“ 2”选择中缀表达式转变为后缀表达式并求值，以下列图。

图（4）按“ 3”选择中缀表达式转变为前缀表达式并求值，以下列图。

图附录：源代码（ 1）表达式求值问题#include<>#include<>#define MAXNUM 100typedef struct Node//定义储藏中缀表达式的结点种类{int data;int data1;char data2;struct Node *next;}Lnode;typedef struct Node2//定义储藏前缀表达式的结点种类{int data;int data1;char data2;struct Node2 *next;struct Node2 *prior;}Lnode2;typedef int selemtype1;//定义运算数栈的结点typedef struct //定义运算数栈的种类{selemtype1 *base;selemtype1*top; }sqstack1;void InitStack1(sqstack1 &s) //新建一个空运算数栈{=(selemtype1 *)malloc(MAXNUM*sizeof(selemtype1));=;if(! printf("出错：申请空间失败！\n");}void Push1(sqstack1 &s,selemtype1 &e)//运算数栈，入栈：插入元素 e 为新的栈顶元素{ if printf("出错：表达式过长！1\n");*++=e;}void GetTop1(sqstack1 s,selemtype1 &e) //运算数栈，用e返回栈顶元素{e=*;}void Popopnd1(sqstack1 &s,selemtype1 &e) // 运算数栈，退栈：删除栈顶元素，并用 e 返回其值{e=*;}int stackempy1(sqstack1 s) // 运算数栈，若为空栈返回 1，否则返回 0 {if== return 1;else return 0;}typedef char selemtype2;//定义运算符栈的结点种类typedef struct //定义运算符栈种类{selemtype2 *base;selemtype2*top; }sqstack2;void InitStack2(sqstack2 &s) //新建一个空运算符栈{=(selemtype2 *)malloc(MAXNUM*sizeof(selemtype2));=;if(! printf("出错：申请空间失败！\n");}void Push2(sqstack2 &s,selemtype2 &e)//运算符栈，入栈：插入元素 e 为新的栈顶元素{ if printf("出错：表达式过长！2\n");*++=e;}void GetTop2(sqstack2 s,selemtype2 &e) //运算符栈，用e返回栈顶元素{e=*;}void Popopnd2(sqstack2 &s,selemtype2 &e) // 运算符栈，退栈：删除栈顶元素，并用 e 返回其值{e=*;}int stackempy2(sqstack2 s) // 运算符栈，若为空栈返回 1，否则返回 0 {if== return 1;else return 0;}void priority(char c,int &i)//确定运算符优先级{if (c=='*'||c=='/'||c=='%') i=2 ;else if (c=='+'||c=='-') i=1 ;else i=0;}int compare(char a,char b) //比较栈顶元素运算符与外面运算符优先级大小，外面优先级大则返回1，反之返回 0{int in,out;priority(a,in);priority(b,out);if(out>in) return 1;else return 0;}void Operat(sqstack1 &OPND,sqstack2 &OPTR){int num1,num2,num;char c;Popopnd1(OPND,num2);Popopnd1(OPND,num1);Popopnd2(OPTR,c);switch(c){case '+':num=num1+num2;break;case '-':num=num1-num2;break;case '*':num=num1*num2;break;case '/':num=num1/num2;break;case '%':num=num1%num2;break;}Push1(OPND,num);}void Operatqianzhui(sqstack1 &OPND,sqstack2 &OPTR){int num1,num2,num;char c;Popopnd1(OPND,num1);Popopnd1(OPND,num2);Popopnd2(OPTR,c);switch(c){case '+':num=num1+num2;break;case '-':num=num1-num2;break;case '*':num=num1*num2;break;case '/':num=num1/num2;break;case '%':num=num1%num2;break;}Push1(OPND,num);}//后缀表达式求值void houzhuiqiuzhi(Lnode *p,int &e){sqstack1 OPND; //运算数栈sqstack2 OPTR; //运算符栈int n;char c;p=p->next;InitStack1(OPND);InitStack2(OPTR);while(p){switch(p->data){case 1:n=p->data1;Push1(OPND,n);break;case 2:c=p->data2;Push2(OPTR,c);Operat(OPND,OPTR);break;default:printf("结点有误 ");break;}p=p->next;}Popopnd1(OPND,n);e=n;}void zhongzhui(Lnode *p)//中缀表达式求值{sqstack1 OPND; //运算数栈sqstack2 OPTR; //运算符栈int n;char c,c2;Lnode *first;first=p;p=p->next;InitStack1(OPND);InitStack2(OPTR);while(!stackempy2(OPTR)||p){while(p){switch(p->data){case 1:n=p->data1;Push1(OPND,n);break;case 2:c=p->data2;if(stackempy2(OPTR)) Push2(OPTR,c);else { switch(c){case '(': Push2(OPTR,c);break;case ')': GetTop2(OPTR,c2);while(c2!='('){Operat(OPND,OPTR);GetTop2(OPTR,c2);}Popopnd2(OPTR,c2);break;default: GetTop2(OPTR,c2);if(compare(c2,c)) Push2(OPTR,c);else { Operat(OPND,OPTR);Push2(OPTR,c);}break;}}break;default: printf("结点有误");break;}p=p->next;}while(!stackempy2(OPTR))Operat(OPND,OPTR);}Popopnd1(OPND,n);p=first->next;while(p){if(p->data==1) printf("%d ",p->data1);if(p->data==2) printf("%c",p->data2);p=p->next;}printf("=%d ",n);}void houzhui(Lnode*p)//中缀表达式转变为后缀表达式{sqstack2 OPTR; //运算符栈Lnode *r,*q,*head;int n;char c,c2;InitStack2(OPTR);p=p->next;q=(Lnode*)malloc(sizeof(struct Node));head=q;while(p){ switch(p->data){case 1:n=p->data1;r=(Lnode*)malloc(sizeof(struct Node));q->next=r;q=q->next;q->data=1;q->data1=n;break;case 2:c=p->data2; if(stackempy2(OPTR))Push2(OPTR,c); else { switch(c){ case '(': Push2(OPTR,c);break;case ')': Popopnd2(OPTR,c2);while(c2!='('){r=(Lnode*)malloc(sizeof(struct Node));q->next=r;q=q->next;q->data=2;q->data2=c2;Popopnd2(OPTR,c2);}break;default: GetTop2(OPTR,c2);while(!compare(c2,c)){ Popopnd2(OPTR,c2);r=(Lnode*)malloc(sizeof(structNode));q->next=r;q=q->next;q->data=2;q->data2=c2;GetTop2(OPTR,c2);}Push2(OPTR,c);break;}}break;default: printf("结点有误");break;}p=p->next;}while(!stackempy2(OPTR)){ Popopnd2(OPTR,c2);r=(Lnode*)malloc(sizeof(struct Node));q->next=r;q=q->next;q->data=2;q->data2=c2;}q->next=NULL;q=head->next;while(q){if(q->data==1) printf("%d ",q->data1);if(q->data==2) printf("%c",q->data2);q=q->next;}houzhuiqiuzhi(head,n);printf("=%d ",n);}void qianzhuiqiuzhi(Lnode2 *p,int &e)//前缀表达式求值{sqstack1 OPND; //运算数栈sqstack2 OPTR; //运算符栈int n;char c;Lnode2 *head;head=p;p=p->next;InitStack1(OPND);InitStack2(OPTR);while(p!=head){switch(p->data){case 1:n=p->data1;Push1(OPND,n);break;case 2:c=p->data2;Push2(OPTR,c);Operatqianzhui(OPND,OPTR);break;default:printf("结点有误 ");break;}p=p->next;}Popopnd1(OPND,n);e=n;}void qianzhui(Lnode *p)//中缀表达式转变为前缀表达式{sqstack2 OPTR; //运算符栈InitStack2(OPTR);int n;char c,c2;Lnode *first;Lnode2 *q,*head,*r,*head2,*s;first=p;p=p->next;q=(Lnode2*)malloc(sizeof(struct Node2));//成立存中缀表达式的双向循环链表head=q;while(p){r=(Lnode2*)malloc(sizeof(struct Node2));q->next=r;r->prior=q;q=q->next;q->data=p->data;q->data1=p->data1;q->data2=p->data2;p=p->next;}q->next=head;head->prior=q;s=(Lnode2*)malloc(sizeof(struct Node2));//成立存前缀表达式的双向循环链表head2=s;while(q!=head){switch(q->data){case 1:n=q->data1;r=(Lnode2*)malloc(sizeof(struct Node2));s->next=r;r->prior=s;s=s->next;s->data=1;s->data1=n;break;case 2:c=q->data2;if(stackempy2(OPTR)) Push2(OPTR,c);else{ GetTop2(OPTR,c2);if(c2==')') Push2(OPTR,c);else{ switch(c){ case ')':Push2(OPTR,c);break;case '(': Popopnd2(OPTR,c2);while(c2!=')'){r=(Lnode2*)malloc(sizeof(struct Node2));s->next=r;r->prior=s;s=s->next;s->data=2;s->data2=c2;Popopnd2(OPTR,c2);}break;default: GetTop2(OPTR,c2);while(!compare(c2,c)){ Popopnd2(OPTR,c2);r=(Lnode2*)malloc(sizeof(struct Node2));s->next=r;r->prior=s;s=s->next;s->data=2;s->data2=c2;GetTop2(OPTR,c2);}Push2(OPTR,c);break;}}}break;default:printf("结点有误 ");break;}q=q->prior;}while(!stackempy2(OPTR)){ Popopnd2(OPTR,c2);r=(Lnode2*)malloc(sizeof(struct Node2));s->next=r;r->prior=s;s=s->next; s->data=2; s->data2=c2;}s->next=head2;head2->prior=s;while(s!=head2){if(s->data==1) printf("%d ",s->data1);if(s->data==2) printf("%c",s->data2);s=s->prior;}qianzhuiqiuzhi(head2,n);printf("=%d ",n);}int main(){ char n[10];char c;int i,j,k,a,b,z,y,e; Lnode *p,*q,*first;i=0;e=1;a=0;b=1;z=0;y=0;p=(Lnode*)malloc(sizeof(struct Node)); first=p;printf("请输入中缀表达式 ");do{ c = getchar();if('0'<=c&&c<='9'){ n[i]=c;i++;}else{ switch (c){ case '+':case '-':case '*':case '/':case '%':case '(':case ')':case '\n':{ if(n[0]>'0'&&n[0]<='9'){ q=(Lnode*)malloc(sizeof(struct Node));p->next=q;p=p->next;for(k=0;k<i;k++){ for(j=0;j<=i-k-2;j++)e=e*10;a=a+(n[k]-'0')*e;e=1;n[k]='0';}p->data=1;p->data1=a;i=0;a=0;}if(c!='\n'){ if(p->data==2){ if(p->data2!=')'&&c!='(')b=0;}q=(Lnode*)malloc(sizeof(struct Node));p->next=q;p=p->next;p->data=2;p->data2=c;if(c=='(') z++;if(c==')') y++;}}default:if(c!='+'&&c!='-'&&c!='*'&&c!='/'&&c!='%'&&c!='\n'&&c!='('&&c!=')')b=0;}}}while (c != '\n');if(z!=y) b=0;p->next=NULL;if(b==0)printf("输入中缀表达式有误 ");else{printf(" 输入 1 中缀表达式求值，输入 2 后缀表达式求值，输入 3 前缀表达式求值 ");scanf("%d",&b);if(b==1) zhongzhui(first); if(b==2) houzhui(first); if(b==3) qianzhui(first); }return 1;}。

目录一、设计思想 (01)二、算法流程图 (02)三、源代码 (04)四、运行结果 (14)五、遇到的问题及解决 (16)六、心得体会 (16)一、设计思想（1）中缀表达式转后缀表达式并计算创建一个数组存储输入的计算表达式。

另创建一个数组储存将要生成的后缀表达式。

创建一个栈储存操作符。

对已存储的表达式数组扫描。

判断当前节点，如果是操作数或’.’，直接加入后缀表达式中，如果是操作符，则比较前一个操作符与当前操作符的优先级。

如果前一个操作符的优先级较高，则将前一个操作符加入后缀表达式中，否则将操作符压入操作符栈。

如果遇到左括号’(’，直接入栈；如果遇到右括号’)’,则在操作符栈中反向搜索，直到遇到匹配的左括号为止，将中间的操作符依次加到后缀表达式中。

当执行完以上操作，发现栈中仍有剩余操作符，则将操作符依次加到后缀表达式中。

此时中缀表达式已经转换成了后缀表达式。

对后缀表达式进行计算。

如果后缀表达式为大于0小于9的字符，则将它转换成浮点型数据并存入数栈中。

如果遇到操作符，则从数栈中提取两个数，进行相应的运算。

依次进行下去，当没有运算符是，运算结束得到最后的结果。

（2）直接表达式求值创建一个数组存储输入的计算表达式。

创建两个栈，一个字符型的栈，一个双精度型的栈。

分别用来存储字符和数。

对已存储的表达式数组扫描。

判断当前节点，如果是操作数和’.’，将字符型的操作数转换为浮点型的数后存入操作数栈。

如果是操作符则判断操作符的优先级。

如果字符栈中已存储符号的优先级小于要存入的字符的优先级，则直接让字符入操作符栈。

如果字符栈中已存储符号的优先级大于或等于要存入的字符的优先级，则取出操作符栈中的一个字符和操作数栈中的两个数进行计算，然后将结果存入操作数栈中，同上进行下去，直到字符栈中已存储符号的优先级小于要存入的字符的优先级时，将操作符存入操作符栈中。

当遇到左括号’(’，将左括号直接存入操作符栈中。

当遇到右括号’)’，则在操作符栈中反向搜索，并且每搜到一个字符就在操作数栈中取两个数进行相应的计算。

C语⾔实现中缀表达式转换为后缀表达式本⽂实例为⼤家分享了C语⾔实现中缀表达式转后缀表达式的具体代码，供⼤家参考，具体内容如下中缀表达式转换为后缀表达式（思路）1.创建栈2.从左向右顺序获取中缀表达式a.数字直接输出b.运算符情况⼀：遇到左括号直接⼊栈，遇到右括号将栈中左括号之后⼊栈的运算符全部弹栈输出，同时左括号出栈但是不输出。

情况⼆：遇到乘号和除号直接⼊栈，直到遇到优先级⽐它更低的运算符，依次弹栈。

情况三：遇到加号和减号，如果此时栈空，则直接⼊栈，否则，将栈中优先级⾼的运算符依次弹栈（注意：加号和减号属于同⼀个优先级，所以也依次弹栈）直到栈空或则遇到左括号为⽌，停⽌弹栈。

（因为左括号要匹配右括号时才弹出）。

情况四：获取完后，将栈中剩余的运算符号依次弹栈输出例:⽐如将:2*(9+6/3-5)+4转化为后缀表达式 2 9 6 3 / +5 - * 4 +转换算法代码如下：/*中缀转后缀函数*/void Change(SqStack *S,Elemtype str[]){int i=0;Elemtype e;InitStack(S);while(str[i]!='\0'){while(isdigit(str[i])){/*过滤数字字符，直接输出，直到下⼀位不是数字字符打印空格跳出循环 */printf("%c",str[i++]);if(!isdigit(str[i])){printf(" ");}}/*加减运算符优先级最低，如果栈顶元素为空则直接⼊栈，否则将栈中存储的运算符全部弹栈，如果遇到左括号则停⽌，将弹出的左括号从新压栈，因为左括号要和⼜括号匹配时弹出，这个后⾯单独讨论。

弹出后将优先级低的运算符压⼊栈中*/ if(str[i]=='+'||str[i]=='-'){if(!StackLength(S)){PushStack(S,str[i]);}else{do{PopStack(S,&e);if(e=='('){PushStack(S,e);}else{printf("%c ",e);}}while( StackLength(S) && e != '(' );PushStack(S,str[i]);}}/*当遇到右括号是，把括号⾥剩余的运算符弹出，直到匹配到左括号为⽌左括号只弹出不打印（右括号也不压栈）*/else if(str[i]==')'){PopStack(S,&e);while(e!='('){printf("%c ",e);PopStack(S,&e);}}/*乘、除、左括号都是优先级⾼的，直接压栈*/else if(str[i]=='*'||str[i]=='/'||str[i]=='('){PushStack(S,str[i]);}else if(str[i]=='\0'){break;}else{printf("\n输⼊格式错误！\n");return ;}i++;}/*最后把栈中剩余的运算符依次弹栈打印*/while(StackLength(S)){PopStack(S,&e);printf("%c ",e);}}完整代码如下：#include<stdio.h>#include<stdlib.h>#include<ctype.h>#include<assert.h>#define INITSIZE 20#define INCREMENT 10#define MAXBUFFER 20#define LEN sizeof(Elemtype)/*栈的动态分配存储结构*/typedef char Elemtype;typedef struct{Elemtype *base;Elemtype *top;int StackSize;}SqStack;/*初始化栈*/void InitStack(SqStack *S){S->base=(Elemtype*)malloc(LEN*INITSIZE);assert(S->base !=NULL);S->top=S->base;S->StackSize=INITSIZE;}/*压栈操作*/void PushStack(SqStack *S,Elemtype c){if(S->top - S->base >= S->StackSize){S->base=(Elemtype*)realloc(S->base,LEN*(S->StackSize+INCREMENT));assert(S->base !=NULL);S->top =S->base+S->StackSize;S->StackSize+=INCREMENT;}*S->top++ = c;}/*求栈长*/int StackLength(SqStack *S){return (S->top - S->base);}/*弹栈操作*/int PopStack(SqStack *S,Elemtype *c){if(!StackLength(S)){return 0;}*c=*--S->top;return 1;}/*中缀转后缀函数*/void Change(SqStack *S,Elemtype str[]){int i=0;Elemtype e;InitStack(S);while(str[i]!='\0'){while(isdigit(str[i])){/*过滤数字字符，直接输出，直到下⼀位不是数字字符打印空格跳出循环 */printf("%c",str[i++]);if(!isdigit(str[i])){printf(" ");}}/*加减运算符优先级最低，如果栈顶元素为空则直接⼊栈，否则将栈中存储的运算符全部弹栈，如果遇到左括号则停⽌，将弹出的左括号从新压栈，因为左括号要和⼜括号匹配时弹出，这个后⾯单独讨论。

//1.h#ifndef STACK_H#define STACK_H#include<stdio.h>#include<stdlib.h>typedef struct astack *Stack;typedef struct astack{int top;int maxtop;char* data;}Astack;Stack NewEmpty(int size){Stack S=(Stack)malloc(sizeof(Astack)); S->maxtop=size;S->top=-1;S->data=(char*)malloc(size*sizeof(char)); return S;}int StackEmpty(Stack S){return S->top<0;}int StackFull(Stack S){return S->top==S->maxtop;}int Peek(Stack S){return S->data[S->top];}void Push(char x,Stack S){if(StackFull(S)){printf("Stack is full!\n");exit(1);}elseS->data[++S->top]=x;int Pop(Stack S){if(StackEmpty(S)){printf("Stack is empty!\n");exit(1);}elsereturn S->data[S->top--];}Stack NewStack(int size){Stack S=NewEmpty(size);int i,x,num;printf("Please enter the number of data:\n"); scanf("%d",&num);for(i=0;i<num;i++){printf("Please enter the %d date:\n",i+1); scanf("%c",&x);Push(x,S);}return S;}void ShowStack(Stack S){int i;for(i=0;i<=S->top;i++){printf(" %c",S->data[i]);}printf("\n");}#endif#include<stdio.h>#include<stdlib.h>#include<ctype.h>#include"1.h"#define MAX 30int Precedence(char ch){if(ch=='+'||ch=='-')return 2; else if(ch=='*'||ch=='/')return 3; else if(ch=='('||ch==')')return 4; else if(ch=='@')return 1;else return 0;}void Change(char *s1,char *s2) {Stack S=NewEmpty(MAX);int i=0,j=0,one=0;char ch=s1[i];Push('@',S);while(ch!='@'){if(ch==' ')ch=s1[++i];else if(isalnum(ch)!=0){if(one==1){s2[j++]=' ';}s2[j++]=ch;ch=s1[++i];one=0;}else if(ch=='('){Push(ch,S);ch=s1[++i];one=1;}else if(ch==')'){while(Peek(S)!='(')s2[j++]=Pop(S);Pop(S);ch=s1[++i];one=1;}else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){while(Peek(S)!='('&&Precedence(Peek(S))>=Precedence(ch)) {s2[j++]=Pop(S);one=1;}Push(ch,S);ch=s1[++i];one=1;}}while(StackEmpty(S)!=1){s2[j++]=Pop(S);one=1;}s2[j]='\0';}int main(){char s1[MAX],s2[MAX];printf("Enter the equation:\n");gets(s1);Change(s1,s2);printf("%s\n",s2);return 0;}。

栈的应⽤1——超级计算器（中缀与后缀表达式）C语⾔这⾥要学的程序主要⽤来实现⼀个功能——输⼊表达式输出结果，也就是⼀个计算器。

效果如下：这个程序主要有两个步骤：1、把中缀表达式转换为后缀表达式；2、计算后缀表达式的结果。

⾸先先明⽩⼏个问题：1、为什么要转换为后缀表达式？因为后缀表达式容易实现计算机计算结果。

（可以百度⼀下后缀表达式，⼜称逆波兰式）2、怎么把中缀表达式转换为后缀表达式？3、怎么⽤后缀表达式输出结果？相信如果弄明⽩了上⾯⼏个问题，有C语⾔基础的同学就可以编出这个程序啦。

⽽后⾯两个问题都要⽤到⼀个数据结构——栈。

实际上数据结构只是⼀种思想，⼀种思维，是连接⼈脑与计算机的桥梁（纯属个⼈杜撰= =） 好，那么我们先学怎么把中缀表达式转换为后缀表达式。

为了简化问题，我们不妨设输⼊的数字都是⼀位整数，这样读⼊的时候只需要以字符的⽅式逐个读⼊即可，也就是说读⼊的必定是数字或者+-*/，读到回车视为结束；另外不妨直接将结果打印到屏幕上，也就是说结果不必存储（这样我们可以更多地关注算法本⾝，⽽⾮输⼊输出⽅式的细枝末节） 类似上⾯的图⽚，它的后缀表达式是 9 3 1 - 2 * + 5 2 / + 怎么得到的呢？下⾯开始讲这个转换的算法： 1、设置⼀个栈，栈底填⼀个"@"作为结束符（当然也可以⽤别的符号，⾄于为什么要⽤⼀会讲优先级的时候会说）； 2、开始逐个字符读⼊； 3、如果读⼊的是数字，直接打印printf("%c ",c)；（数字后⾯打印⼀个空格作为间隔符，要不然没法看了931-。

不解释） 4、如果读⼊的是"("直接进栈； 5、如果读⼊的是")"，说明前⾯肯定读⼊过⼀个"("找到这个左括号，把两者之间的符号逐个弹栈（这⾥要说明的是，括号不必打印，因为后缀表达式没有括号）； 6、如果不是上⾯的⼏种情况，那必定是+-*/中的⼀个啦，这样来说就容易多了。

一、设计思想计算算术表达式可以用两种方法实现:1.中缀转后缀算法此算法分两步实现：先将算术表达式转换为后缀表达式，然后对后缀表达式进行计算.具体实现方法如下:（1）中缀转后缀需要建一个操作符栈op和一个字符数组exp,op栈存放操作符，字符数组用来存放转换以后的后缀表达式。

首先，得到用户输入的中缀表达式,将其存入str数组中。

对str数组逐个扫描，如果是数字或小数点,则直接存入exp数组中，当扫描完数值后,在后面加一个＃作为分隔符。

如果是操作符，并且栈为空直接入栈，如果栈不为空，与栈顶操作符比较优先等级，若比栈顶优先级高，入栈；如果比栈顶优先级低或相等，出栈将其操作符存到exp数组中，直到栈顶元素优先等级低于扫描的操作符，则此操作符入栈；如果是左括号，直接入栈，如果是右括号，出栈存入exp数组,直到遇到左括号，左括号丢掉。

然后继续扫描下一个字符,直到遇到str中的结束符号\0，扫描结束。

结束后看op栈是否为空，若不为空，继续出栈存入exp数组中，直到栈为空.到此在exp数组最后加结束字符\0。

我们就得到了后缀表达式。

（2）后缀表达式计算此时需要一个数值栈od来存放数值。

对exp数组进行逐个扫描，当遇到数字或小数点时，截取数值子串将其转换成double类型的小数，存入od栈中。

当遇到操作符，从栈中取出两个数，进行计算后再放入栈中。

继续扫描,知道扫描结束,此时值栈中的数值就是计算的结果,取出返回计算结果。

2。

两个栈实现算法此算法需要两个栈，一个值栈od，一个操作符栈op。

将用户输入的数学表达式存入str数组中,对其数组进行逐个扫描。

当遇到数字或小数点，截取数值子串，将其转换成double类型的数值存入od栈中；当遇到左括号，直接入op栈；遇到右括号，op栈出栈，再从值栈od中取出两个数值，计算将其结果存入值栈中,一直进行此操作，直到操作符栈栈顶为左括号，将左括号丢掉。

如果遇到操作符，若op栈为空，直接入栈;若栈不为空，与栈顶元素比较优先等级,若比栈顶操作符优先等级高，直接入op栈,如果低于或等于栈顶优先等级，op栈出栈,再从值栈中取出两个数值，计算将其结果存入值栈中，一直进行此操作，直到栈顶优先等级低于扫描的操作符等级，将此操作符入op 栈。

算法笔记--中缀表达式转后缀表达式后缀表达式计算中缀表达式转后缀表达式规则中缀表达式a + b*c + (d * e + f) * g，转换成后缀表达式则为a b c * + d e * f + g * +转换过程需要⽤到栈，具体过程如下：1 如果遇到操作数，我们就直接将其输出。

2 如果遇到操作符，则我们将其放⼊到栈中，遇到左括号时我们也将其放⼊栈中。

3 如果遇到⼀个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为⽌。

注意，左括号只弹出并不输出。

4 如果遇到任何其他的操作符，如+, *, (等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为⽌。

弹出完这些元素后，才将遇到的操作符压⼊到栈中。

有⼀点需要注意，只有在遇到 )的情况下我们才弹出( ，其他情况我们都不会弹出( 。

即：若操作符op的优先级⾼于栈顶操作符的优先级，则压⼊操作符栈若操作符op的优先级⼩于等于栈顶操作符的优先级，则将操作栈的操作符不断弹出到后缀表达式中，直到op的优先级⾼于栈顶操作符的优先级5 如果我们读到了输⼊的末尾，则将栈中所有元素依次弹出。

实例a +b *c + (d *e + f) * g1. ⾸先读到a，直接输出。

2. 读到“+”，将其放⼊到栈中。

3. 读到b，直接输出。

此时栈和输出的情况如下：4. 读到“*”，因为栈顶元素"+"优先级⽐" * " 低，所以将" * "直接压⼊栈中。

5. 读到c，直接输出。

此时栈和输出情况如下：6. 读到" + "，因为栈顶元素" * "的优先级⽐它⾼，所以弹出" * "并输出，同理，栈中下⼀个元素" + "优先级与读到的操作符" + "⼀样，所以也要弹出并输出。

然后再将读到的" + "压⼊栈中。

一、设计思想第一种算法：将中缀表达式转为后缀表达式，然后通过后缀表达式计算出算术表达式的结果。

核心思想：第一步：中缀变后缀。

首先，我们做出一个统一的Node结构体，结构体内部包含四个属性，分别是操作符的字符‘op’，char类型；操作符的优先级‘level’，int 类型；数字的浮点数数值‘od’，float类型；Node的标识符，int类型。

然后，定义一个Node结构体类型的数组*listNode，这里的*listNode用的是全局变量，为了方便在得到后缀表达式后，不需再传递给计算的方法。

定义一个存放操作符的栈，遍历用户输入的算术表达式（不考虑错误情况），在遍历的过程中如果遇到数字，直接将数字存放在*listNode里面；如果遇到了操作符，则判断操作符栈目前是不是为空，如果为空，直接将遇到的操作符放入操作符栈中，如果操作符栈不为空，那么观察操作符栈中栈顶的操作符，然后再次判断当前遇到的操作符的优先级是不是比栈顶的操作符的优先级高，如果是，那么将当前的操作符入操作符栈；如果不是，那么将操作符栈的栈顶操作符取出，追加到*listNode中，然后继续观察栈顶操作符，直到当前的操作符的优先级比栈顶操作符的优先级高或者操作符栈为空时，将当前操作符入操作符栈。

如果遇到了左括号，那么定义其优先级为最低，然后直接将左括号入操作符栈。

如果遇到了右括号，那么开始从操作符栈中取出操作符追加到*listNode中，直到遇到了与之对应的左括号，然后将左括号和右括号一起销毁。

当遍历完成了算术表达式之后，这时判断操作符栈是否为空，如果不为空，那么从操作符栈中依次取出栈顶操作符追加到*listNode中，直到操作符栈为空，那么就代表我们将中缀表达式转变成为了后缀表达式。

第二步：通过得到的后缀表达式，计算算术表达式。

首先，定义一个数字栈用来存放数值。

然后，遍历*listNode中的每一个Node，如果Node是一个数字，那么就将数字入数字栈，如果Node是一个操作符，那么就从数字栈中依次取出栈顶的两个数字，然后根据操作符计算这两个数字，将得到的结果再次入数字栈，直到遍历*listNode完成，最终数字栈中会只剩下一个Node，那就是我们计算出算术表达式的结果，将结果返回给main 函数用来输出。

中缀表达式转后缀表达式中缀表达式转后缀表达式的规则。

1.遇到操作数：直接输入到后缀表达式栈2.遇到运算符，直接入操作符栈3.遇到左括号：直接将其入栈4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。

5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈6.最终将操作符栈中的元素依次出栈，输出到后缀表达式栈。

以下是自己写的代码。

亲测没有问题。

（模拟一个计算器，可以带括号，中间可以空格，只支持整数输入，但是输出结果精确到小数后6位）#include "stdio.h"#define MAX_LEN 100typedef struct cal{unsigned char isOper;//是否是操作数1，操作符0.操作数double Num; //值。

或者是操作符的ASCII值}STRUCT_CAL;#define IS_NUM 0x00#define IS_OPER 0x01STRUCT_CAL stackCal[MAX_LEN];STRUCT_CAL stackCalBack[MAX_LEN];unsigned char topCal;char stackOper[MAX_LEN];unsigned char topOper;/****************************************************************** 堆栈初始化*****************************************************************/void stackInit(void){int i;for(i=0;i<MAX_LEN;i++){stackCal[i].isOper = 0;stackCal[i].Num = 0;stackOper[i] = 0;}topCal = topOper = 0;}/***************************************************************** * 返回堆栈的栈顶，返回后栈顶减一*****************************************************************/ STRUCT_CAL * stackCalPop(void){if(topCal == 0)return (STRUCT_CAL *)0;return stackCal+(--topCal);}/***************************************************************** * 计算表达式入栈*****************************************************************/void stackCalPush(double num, unsigned char isOper){if(topCal>=MAX_LEN)return;stackCal[topCal].Num = num;stackCal[topCal].isOper= isOper;topCal++;}/***************************************************************** * 操作符出栈*****************************************************************/char stackOperPop(void){if(topOper == 0)return 0;return stackOper[--topOper];}/****************************************************************** 操作符入栈*****************************************************************/void stackOperPush(char oper){if(topOper >=MAX_LEN)return;stackOper[topOper++] = oper;}/****************************************************************** 比较两个sour sour1 的优先级* 1 sour >= sour1 直接入操作符栈* 0 sour < sour1 直接入计算表达式栈*****************************************************************/ unsigned char comparPrior(char sour, char sour1){if(sour =='\0' ||sour1 == '\0') return 1;switch(sour){case '+':case '-':if(sour1 == '*' ||sour1 == '/'||sour1 == '+' ||sour1 == '-' ){return 0;}else{return 1;}break;case '*':case '/':if(sour1 == '*' ||sour1 == '/'||sour1 == '+' ||sour1 == '-'||sour1 == '('){return 1;}else{return 0;}break;default:return 1;break;}}/****************************************************************** 将输入的字符串转换为栈*****************************************************************/void StrToCal(char *pStr){int tmpNum = 0;char tmpOper;char islastNum = 0;//判断上一个字符是什么。

c语言中缀表达式转后缀表达式在C语言中，可以使用栈的数据结构来实现中缀表达式转后缀表达式的操作。

下面是一个示例代码：```c#include <stdio.h>#include <stdlib.h>#include <string.h>#define MAX_SIZE 100// 定义运算符的优先级int getPriority(char operator) {switch(operator) {case '+':case '-':return 1;case '*':case '/':return 2;case '^':return 3;default:return 0;}}// 判断字符是否为操作符int isOperator(char character) {return (character == '+' || character == '-' || character == '*' ||character == '/' || character == '^');}// 中缀表达式转后缀表达式void infixToPostfix(char* infixExpression, char* postfixExpression) {char stack[MAX_SIZE];int top = -1;int infixLength = strlen(infixExpression);int postfixIndex = 0;for(int i = 0; i < infixLength; i++) {// 如果是操作数，直接输出到后缀表达式if(!isOperator(infixExpression[i]) && infixExpression[i] != '(' && infixExpression[i] != ')') {postfixExpression[postfixIndex] = infixExpression[i];postfixIndex++;}// 如果是‘（’，入栈if(infixExpression[i] == '(') {stack[++top] = infixExpression[i];}// 如果是操作符if(isOperator(infixExpression[i])) {// 当当前操作符的优先级小于等于栈顶操作符的优先级时，将栈顶操作符输出到后缀表达式，再将当前操作符入栈 while(top != -1 && getPriority(infixExpression[i]) <=getPriority(stack[top])) {postfixExpression[postfixIndex] = stack[top];postfixIndex++;top--;}stack[++top] = infixExpression[i];}// 如果是'）'，将栈中的操作符输出到后缀表达式直到遇到‘（’if(infixExpression[i] == ')') {while(top != -1 && stack[top] != '(') {postfixExpression[postfixIndex] = stack[top];postfixIndex++;top--;}// 弹出‘（’top--;}}// 输出栈中剩余的操作符while(top != -1) {postfixExpression[postfixIndex] = stack[top];postfixIndex++;top--;}postfixExpression[postfixIndex] = '\0';}int main() {char infixExpression[MAX_SIZE];char postfixExpression[MAX_SIZE];printf("请输入中缀表达式：");scanf("%s", infixExpression);infixToPostfix(infixExpression, postfixExpression);printf("后缀表达式：%s\n", postfixExpression);return 0;}```该程序通过读入一个中缀表达式，将其转换为后缀表达式并输出。

C语言实现中缀、后缀、前缀表达式相互转化并求值1.问题描述(1)表达式求值问题表达式是数据运算的基本形式。

人们的书写习惯是中缀式，如:11+22*(7-4)/3。

中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。

表达式还有后缀式(如:22 7 4 - * 3 / 11 +)和前缀式(如:+ 11 / * 22 –7 4 3)。

后缀表达式和前缀表达式中没有括号，给计算带来方便。

如后缀式计算时按运算符出现的先后进行计算。

本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。

2.数据结构设计(1)表达式求值问题由于表达式中有字符与数字两种类型，故定义结点一个标志域data，标志结点存储的为字符data=2还是数字data=1，再寻找结点中对应的存储位置，读取数字域data1,字符域data2。

而在前缀表达式时，存在表达式逆序，因表达式类型不统一，用栈逆序极不方便，选择构建双向链表，存储表达式。

typedef struct Node //定义存储中缀表达式的结点类型{int data;int data1;char data2;struct Node *next;}Lnode;typedef struct Node2 //定义存储前缀表达式的结点类型{int data;int data1;char data2;struct Node2 *next;struct Node2 *prior;}Lnode2;3.运行、测试与分析(1)表达式求值问题(1)按提示输入中缀表达式，如图1.1所示。

如输入中缀表达式不正确，提示输入有误，如图1.2,1.3所示。

图1.1图1.2图1.3(2)选择表达式转换并求值方式。

按“1”选择中缀表达式求值，如图1.4所示。

图1.4(3)按“2”选择中缀表达式转变为后缀表达式并求值，如图1.5所示。

图1.5(4)按“3”选择中缀表达式转变为前缀表达式并求值，如图1.6所示。

c语⾔表达式求值中缀表达式转后缀表达式求值中转后具体转换⽅式:1.从左到右遍历需要计算的字符串2.若是运算数,直接压⼊后缀表达式栈3.若是左括号,直接压⼊运算符栈,(括号是最⾼优先级,⽆需⽐较)(⼊栈后优先级降到最低,确保其他符号正常⼊栈)4.若是右括号,(意味着括号已结束)不断弹出运算符栈顶运算符并输出到后缀表达式栈直到遇到左括号(弹出但不输出)5.运算符,将该运算符与运算符栈顶运算符进⾏⽐较,如果优先级⾼于栈顶运算符则压⼊运算符栈(该部分运算还不能进⾏),如果优先级低于等于栈顶运算符则将栈顶运算符弹出到后缀表达式栈然后⽐较新的栈顶运算符.(低于弹出意味着前⾯部分可以运算,先输出到后缀表达式栈⼀定是⾼优先级运算符,等于弹出是因为同等优先级,从左到右运算)直到优先级⼤于栈顶运算符或者栈空,再将该运算符⼊运算符栈6.如果字符串处理完毕,则按顺序从运算符栈弹出所有运算符到后缀表达式栈使⽤后缀表达式计算的⽅法：1、按顺序取后缀表达式的每个值2、若是数字则⼊栈3、若是操作符则从栈取出两个数字进⾏运算运算之后再将结果⼊栈4、循环上述过程知道后缀表达式结束栈顶元素（栈中只有⼀个元素）即为结果1 #include <windows.h>2 #include <stdio.h>3 #include <string.h>4 #include <malloc.h>5#define NUM 06#define OPERATION 17 typedef struct {//栈中的结点8int val;9int type;10 } Node;11 typedef struct {//栈12const char* name;//栈名13 Node* sta;//结点14int size;//最多存储多少个元素15int cnt;//当前存储了多少个元素16 } MyStack;17void trace(MyStack* s)//栈的遍历18 {19int i;20 printf("%s栈中的元素为：", s->name);21for (i = 0; i < s->cnt; i++) {22if (s->sta[i].type == NUM) {//若是数字23 printf("%d ", s->sta[i].val);24 }25else {//若是字符26 printf("%c ", (char)s->sta[i].val);27 }28 }29 printf("\n");30 }31void sFree(MyStack* s)//释放栈32 {33if (s->sta != NULL) {34 free(s->sta);35 s->sta = NULL;36 }37return;38 }39int sInit(MyStack* s, const char* name, int size)//初始化栈40 {41 s->name = name;42 s->size = size;43 s->sta = (Node*)calloc(s->size, sizeof(Node));//calloc申请后其中存的都是044if (s->sta == NULL) {45return -1;//分配失败46 }47 s->cnt = 0;//当前栈中元素有0个48return0;//分配成功49 }50void sPush(MyStack* s, Node item)//⼊栈⼀个元素51 {52if (s->cnt == s->size) {53 printf("栈空间不⾜\n");54return;55 }56 s->sta[s->cnt] = item;57 s->cnt++;58return;59 }60bool sIsEmpty(MyStack* s)//判断栈是否为空61 {62return s->cnt == 0;63 }64void sPop(MyStack* s, Node* item)//删除栈顶元素并返回值到item65 {66if (sIsEmpty(s)) {67return;68 }69 *item = s->sta[s->cnt - 1];70 s->cnt--;71return;72 }73void sTop(MyStack* s, Node* item)//获得栈顶元素到item 不删除栈顶袁术74 {75if (sIsEmpty(s)) {76return;77 }78 *item = s->sta[s->cnt - 1];79return;80 }81bool myIsNum(char ch)//判断是否是数字82 {83return ch >= '0' && ch <= '9';84 }85bool myIsOper(char ch)//判断是否是运算符86 {87return ch == '+' || ch == '-' || ch == '*' || ch == '/'||ch=='('||ch==')';88 }89//处理数值90void procNum(MyStack* postfix_expression, char* s, int len, int* pi)91 {92int i = *pi;//令i等于当前在处理的元素的坐标93int num=0;//当前数字的值具体是多少94 Node item_num;95while (myIsNum(s[i]))96 {97 num = num * 10 + s[i]-'0';98 i++;99 }100//新建结点101 item_num.type = NUM;102 item_num.val = num;103//数字直接⼊后缀表达式的栈104 sPush(postfix_expression, item_num);105 *pi = i-1;//改变calculate_postfix_expression 中i的值106return;107 }108//处理运算符109void procOper(MyStack* postfix_expression, MyStack* s_oper, char* s, int len, int* pi) 110 {111int i = *pi;112 Node item;113 Node top_item;114 Node pop_item;115if (s[i] == '(')//如果是( 直接存⼊运算符栈116 {117 item.type = OPERATION;118 item.val = s[i];119 sPush(s_oper, item);120 }121else if (s[i] == ')')//若是) 则弹出到(为⽌122 {123int flag = 0;//是否找到了 (124while (!sIsEmpty(s_oper)) {125 sPop(s_oper, &pop_item);126if (pop_item.val == '(') {//若找到了左括号退出127 flag = 1;128break;129 }130 sPush(postfix_expression, pop_item);//若未找到左括号则⼀直从运算符栈中pop131 }132if (!flag)133 {134 printf("括号不匹配！");135 exit(0);136 }137 }138//如果是乘除139else if (s[i] == '*' || s[i] == '/')140 {141 item.type = OPERATION;142 item.val = s[i];143while (!sIsEmpty(s_oper)) {144 sTop(s_oper, &top_item);145//如果当前运算符栈的栈顶是+ - (146//则* /级别较⾼则跳出循环147if (top_item.val == '+' || top_item.val == '-' || top_item.val == '(') {148break;149 }150//若当前运算符栈顶不是+ - ( 则是* /151//则需先把* / pop完152 sPop(s_oper, &pop_item);153 sPush(postfix_expression, pop_item);154 }155//才能将当* /⼊栈156 sPush(s_oper, item);157 }158//如果是 + -159else if (s[i] == '+' || s[i] == '-')160 {161 item.type = OPERATION;162 item.val = s[i];163while (!sIsEmpty(s_oper)) {164 sTop(s_oper, &top_item);165//如果当前运算符栈的栈顶是 (166//则当前运算符级别较⾼则跳出循环167if (top_item.val == '(') {168break;169 }170//若当前运算符栈顶不是 ( 则是+ - * /171//则需先把+ - * /pop完172 sPop(s_oper, &pop_item);173 sPush(postfix_expression, pop_item);174 }175//才能将当+ - ⼊栈176 sPush(s_oper, item);177 }178else179 {180 printf("输⼊了⾮空格⾮数字⾮运算符的元素 %c\n", s[i]);181 exit(0);182 }183return;184 }185//计算后缀表达式存储在s_trans中186void calculate_postfix_expression(MyStack* postfix_expression, MyStack* s_oper, char* s, int len) 187 {188int i;189int ret;190int num;191 Node item;192for (i = 0; i < len; i++) {193if (s[i] == '') {//当前输⼊为空格时跳过194continue;195 }196if (myIsNum(s[i])) {//当前是数字时197 procNum(postfix_expression, s, len, &i);198continue;199 }200if (myIsOper(s[i])) {//当前是运算符时进⼊运算的处理程序201 procOper(postfix_expression, s_oper, s, len, &i);202continue;203 }204 printf("输⼊了⾮空格⾮数字⾮运算符的元素 %c\n", s[i]);205 exit(0);206 }207//若运算栈不为空依次pop出运算栈中的元素再push到后缀表达式栈208while (!sIsEmpty(s_oper)) {209 sPop(s_oper, &item);210 sPush(postfix_expression, item);211 }212return;213 }214int cal(MyStack* postfix_expression, MyStack* s_num)//进⾏计算215 {216int i;217 Node n1, n2;218 Node item;219//顺序取出栈中的每个元素220for (i = 0; i < postfix_expression->cnt; i++) {221//item为后缀表达式中顺序取的第i个元素222 item = postfix_expression->sta[i];223//若⼀直是数字则⼀直放进数字栈224if (item.type == NUM) {225 sPush(s_num, item);226continue;//开始下⼀次循环227 }228//执⾏到这⾥证明不是数字是运算符了229 sPop(s_num, &n2);//从栈中拿出两个元素到n2 n1中230 sPop(s_num, &n1);231if (item.val == '+') {232 n1.val += n2.val;233 }234else if (item.val == '-') {235 n1.val -= n2.val;236 }237else if (item.val == '*') {238 n1.val *= n2.val;239 }240else {241 n1.val /= n2.val;242 }243 sPush(s_num, n1);//再将此次运算结果⼊数字栈244 }245return s_num->sta[0].val;//最后数字栈中的第⼀个元素就是计算结果246 }247int calculate(char* s) {//进⾏计算248int ret;249int len;250if (s == NULL||(len=strlen(s))==0) {251return0;252 }253 MyStack s_num;//数字栈254 MyStack s_oper;//运算符栈255 MyStack postfix_expression;//后缀表达式栈256if (sInit(&s_num, "数字", len)==-1||257 sInit(&s_oper, "运算符", len)==-1||258 sInit(&postfix_expression, "后缀表达式", len)==-1259 ) //若初始化三个栈失败的话则释放内存 return 0260 {261 sFree(&s_num);262 sFree(&postfix_expression);263 sFree(&s_oper);264return0;265 }266//计算后缀表达式267 calculate_postfix_expression(&postfix_expression, &s_oper, s, len); 268//显⽰后缀表达式269 trace(&postfix_expression);270//使⽤后缀表达是进⾏计算271 ret = cal(&postfix_expression, &s_num);272//释放栈的空间273 sFree(&postfix_expression);274 sFree(&s_oper);275 sFree(&s_num);276//返回结果277return ret;278 }279int main()280 {281char str[10000];282 scanf("%[^\n]", str);//可以输⼊空格回车停⽌输⼊283 printf("计算结果为%d\n", calculate(str));284 }285//例⼦ (((50+20)+(2*3))/14)。

c 实现中缀表达式转后缀表达式比计算值C语言是一种广泛应用的编程语言，它具有高效、可移植、灵活等特点，在计算机科学领域有着广泛的应用。

中缀表达式是我们常见的数学表达方式，而将中缀表达式转换为后缀表达式是一项常见的任务。

本文将介绍如何使用C语言实现中缀表达式转后缀表达式，并计算其值。

我们需要了解中缀表达式和后缀表达式的概念。

中缀表达式是我们常见的数学表达方式，其中操作符位于操作数之间，如"3 + 4"。

而后缀表达式（也称为逆波兰表达式）是一种更加简洁的数学表达方式，其中操作符位于操作数之后，如"3 4 +"。

后缀表达式的计算更加简单直观，因此在计算机中更为常见。

接下来，我们需要实现一个函数来将中缀表达式转换为后缀表达式。

我们可以使用栈这一数据结构来辅助实现。

具体的步骤如下：1. 创建一个栈，用于存储操作符。

2. 遍历中缀表达式的每个字符。

3. 如果当前字符是操作数，直接输出。

4. 如果当前字符是操作符，并且栈为空，将操作符入栈。

5. 如果当前字符是操作符，并且栈不为空，比较当前操作符与栈顶操作符的优先级。

- 如果当前操作符的优先级大于栈顶操作符的优先级，将当前操作符入栈。

- 如果当前操作符的优先级小于等于栈顶操作符的优先级，将栈顶操作符出栈并输出，直到栈为空或者栈顶操作符的优先级小于当前操作符。

- 将当前操作符入栈。

6. 如果当前字符是左括号"("，将其入栈。

7. 如果当前字符是右括号")"，将栈顶操作符出栈并输出，直到栈顶操作符为左括号"("。

8. 遍历结束后，将栈中剩余的操作符依次出栈并输出。

通过上述步骤，我们可以将中缀表达式转换为后缀表达式。

接下来，我们需要计算后缀表达式的值。

为了计算后缀表达式的值，我们可以使用另一个栈来辅助实现。

具体的步骤如下：1. 创建一个栈，用于存储操作数。

2. 遍历后缀表达式的每个字符。

/*名称：中缀表达式转换为后缀表达式算法及后缀表达式计算算法的实现内容：1、掌握栈的存储结构的C语言描述2、掌握中缀表达式转换为后缀表达式的算法实现3、掌握后缀表达式计算算法的实现要求：程序功能包括：主程序；表达式的输入、转换；后缀表达式的输出、计算和数据的输出。

名称二叉树的建立与遍历及二叉树中序线索化及线索化遍历的实现内容掌握二叉树的建立与遍历的算法实现掌握二叉树中序线索化及线索化遍历的算法实现要求程序功能包括：主程序；二叉树的建立、二叉树的遍历(前序、中序、后序)、二叉树中序线索化、线索化遍历和输出等实验报告：程序流程图；上机通过的程序（清单）；总结二叉树遍历的特点*//*函数：1、线索二叉树（左孩子、右孩子、左线索标志、右线索标志、双亲、数据域）2、建立二叉树3、前、中、后序扫描二叉树4、中序线索化二叉树5、中序遍历线索二叉树6、线索二叉树查找7、线索二叉树插入功能：1、二叉树的输入实现（输入根、左、右的顺序，当左或右为空时输入0，以‘#’结束输入）（输入优化）2、前、中、后序扫描二叉树输出扫描结果3、二叉树中序线索化4、二叉树线索化遍历/*#include <stdio.h>#include <stdlib.h>#include <conio.h>#define maxsize 100typedef char datatype;typedef struct node{int ltag,rtag;datatype data;struct node *lchild,*rchild;//*parent;} bitree;bitree *root;bitree *pre;bitree *Q[maxsize];bitree *creatree(){char ch;int front,rear;//队头、队尾指针bitree *root,*s;root=NULL;//置空二叉树front=1;rear=0;//置空队列printf("\t\t>>>请输入二叉树(无孩子输入'@'并以'#'结束)：\n\t\t");ch=getchar();//输入第一个字符while(ch!='#')//不是结束符时重复做{s=NULL;if(ch!='@')//@表示虚结点，不是虚结点时建立新结点{s=(bitree *)malloc(sizeof(bitree));s->data=ch;s->lchild=NULL;s->rchild=NULL;s->ltag=0;s->rtag=0;}rear++;Q[rear]=s;//将虚结点指针NULL或新结点地址入队if(rear==1) root=s;//输入的第一个结点为根结点else{if(s && Q[front])//孩子和双亲结点均不是虚结点if(rear%2==0) Q[front]->lchild=s;//rear为偶数，新结点为左孩子else //rear为奇数Q[front]->rchild=s;//新结点是右孩子if(rear%2==1) front++;//结点*Q[front]的两个孩子已经处理完毕，出队列}ch=getchar();//输入下一个字符}return root;//返回根指针}//关于建立新树：输入处理（关于完全二叉树）//中序遍历void inorder(bitree *t){if(t)//二叉树非空{inorder(t->lchild);//中序遍历t的左子树printf("%c ",t->data);//访问结点tinorder(t->rchild);//中序遍历t的右子树}}//前序遍历void preorder(bitree *t){if(t)//二叉树非空{printf("%c ",t->data);//访问结点tpreorder(t->lchild);//中序遍历t的左子树preorder(t->rchild);//中序遍历t的右子树}}//后序遍历void postorder(bitree *t){if(t)//二叉树非空{postorder(t->lchild);//中序遍历t的左子树postorder(t->rchild);//中序遍历t的右子树printf("%c ",t->data);//访问结点t}}void inthread(bitree *p)//将二叉树p中序线索化，线索标志初值为0 {if(p!=NULL){inthread(p->lchild);//左子树线索化if(p->lchild==NULL) p->ltag=1;//建立左线索标志if(p->rchild==NULL) p->rtag=1;//建立右线索标志if(pre!=NULL){if(pre->rtag==1)//p无右子树pre->rchild=p;//右线索p->rchild为pif(pre->ltag==1)//p无左子树pre->lchild=pre;//左线索p->lchild为pre}pre=p;inthread(p->rchild);//右子树线索化}}//在中序线索树中找结点*p的中序后继bitree *inordernext(bitree *p){bitree *q;if(p->rtag==1)//p右子树为空return (p->rchild);//p->rchild是右线索，指向p的后继else //p的右子树非空{q=p->rchild;//从p的右孩子开始查找while(q->ltag==0)//当q不是左下结点时，继续查找q=q->lchild;return(q);}}//遍历中序线索二叉树pvoid travereinthread(bitree *p){if(p!=NULL)//非空树{while(p->ltag==0)//找中序序列的开始结点p=p->lchild;do{printf("%c ",p->data);//访问结点pp=inordernext(p);//找p的中序后继结点}while(p!=NULL);}}void main(){bitree *p;int a=0;printf("\t\t**********************************************\n");printf("\t\t ************二叉树************\n");printf("\t\t**********************************************\n\n");p=creatree();//创建二叉树printf("\n");printf("\t\t二叉树的前序遍历结果为：\n");//前序遍历printf("\t\t"); preorder(p); printf("\n");printf("\t\t二叉树的中序遍历结果为：\n");//中序遍历printf("\t\t"); inorder(p); printf("\n");printf("\t\t二叉树的后序遍历结果为：\n");//后序遍历printf("\t\t"); postorder(p); printf("\n");inthread(p);//中序线索化printf("\t\t二叉树的中序线索化遍历结果为：\n");//后序遍历printf("\t\t");travereinthread(p);//中序线索话遍历printf("\t\t");getch();}*//*//在结点p、p的右子树之间插入新结点qinsertright(bithptr *p,bithptr *q){bithptr *s;s=inordernext(p);//查找p的原中序后继结点q->ltag=1;//建立q的左线索标志q->lchild=p;//q的中序前趋为pq->rtag=p->rtag;q->rchild=p->rchild;//q的右子树或右线索等于原p的右子树或右线索p-ratag=0;p->rchild=q;//新结点q作为p的右孩子if((s!=NULL)&&(s->ltag==1))s->lchild=q;//结点s的左链是线索，s的前趋是p}*//*#include <stdio.h>#include <stdlib.h>#include <conio.h>#include <math.h>typedef struct node//定义栈结构体类型{bool n;//标志操作数和操作符char operate;//操作符float num; //操作数struct node *next;} stack;struct changenum//临时变量{bool w;float num;char op;stack *q;} ;stack *InitStack()//初始化堆栈{stack *S;S = (stack *)malloc(sizeof(stack));S->n=0;S->num=0;S->operate=0;S->next=NULL;return S;}stack *push(stack *top,bool n,float num,char operate)//进栈函数{stack *p;p=(stack *)malloc(sizeof(stack));//生成新节点if(n==0)//进栈的为浮点数{p->n=0;p->operate=NULL;p->num=num;}if(n==1)//进栈的为操作符{p->n=1;p->operate=operate;p->num=NULL;}p->next=top;top=p;return p;}changenum *pop(stack *top)//退栈函数{stack *p;changenum *sp;sp=(changenum *)malloc(sizeof(changenum));if(top->next==NULL) {printf("underflow!\n");return NULL;}//栈下溢else//退栈操作{p=top;top=top->next;sp->q=top;sp->num=p->num;sp->op=p->operate;sp->w=0;return sp;}}//*******************************************//****************栈定义及操作***************//后缀表达式的存储//*******************************************typedef struct node2{bool n;//标志操作数和操作符float num;//操作数char operate;//操作符struct node2 *front,*rear,*next;//队头队尾指针} squeue; //定义队列类型squeue *q;squeue *InitQueue()//初始化队列{squeue *Q;Q = (squeue *)malloc(sizeof (squeue));Q->n=0;Q->front=Q;Q->num=12345;Q->operate=0;Q->front->next=NULL;Q->rear =Q;return Q;}void enqueue(squeue *q,bool n,float number,char op)//入队操作{if(op==')') ;else{q->rear->next=(squeue *)malloc(sizeof(squeue));q->rear=q->rear->next;if(n==0){q->rear->n=0;q->rear->operate=NULL;q->rear->num=number;}if(n==1){q->rear->n=1;q->rear->operate=op;q->rear->num=NULL;}q->rear->next=NULL;}}changenum *dequeue(squeue *q)//出队操作{squeue *s;changenum *sp;sp=(changenum *)malloc(sizeof(changenum));if(q->front->next==NULL) {sp->num=q->num;sp->w=q->n;} else{s=q->front->next;q->front->next=s->next;sp->w=s->n;sp->num=s->num;sp->op=s->operate;}return sp;}//*******************************************//****************队定义及操作***************//实现表达式的临时存储//*******************************************int priority(char ch)//操作符及操作数优先级判断{switch(ch){case'+': case'-': return 2;case'*': case'/':return 3;case'(': case'#': return 1;case')': return 4;case ' ':return 10;case'.': case'0': case'1': case'2':case'3': case'4': case'5': case'6':case'7': case'8': case'9': return 0;default:printf("ERROR!"); return 5;}}changenum *getlist(char ch)//将字符数组转为float类型变量{changenum *sp;sp=(changenum *)malloc(sizeof(changenum));if(priority(ch)==0){sp->w=0;int p=1;float sum=0,point=0;char a[40];int m=0;int n=1;for(int i=0;i<=39;i++)a[i]=0;while(ch!='.'&&priority(ch)==0){a[m]=ch; sum=sum*10+(a[m]-'0'); m++;//整数部分ch=getchar();}if(ch=='.'){ch=getchar();while(priority(ch)==0)//小数部分处理{a[m+n]=ch; point=point*10+(a[m+n]-'0');p=p*10; n++;ch=getchar();}}sum=sum+point/p;//转为浮点数sp->num=sum;sp->op=ch;return sp;}else{sp->w=1;sp->num=100;sp->op=100;return sp;}}float change()//输入中缀表达式并转换为后缀表达式、输出后缀表达式并计算结果{stack *formula1;squeue *formula2,*formula4;stack *formula3;char a,ch;bool i; changenum *mark,*sign;formula2=InitQueue();formula4=InitQueue();formula1=InitStack();formula3=InitStack();formula3=push(formula3,1,0,'#');formula1=push(formula1,1,0,'#');printf("请输入表达式以#结束：\n");ch=getchar();do{mark=getlist(ch);i=mark->w;if(i==0){enqueue(formula2,0,mark->num,0);enqueue(formula4,0,mark->num,0);ch=mark->op;free(mark);/ /将操作数入队}else{switch(ch)//操作符处理{case '(' : formula1=push(formula1,1,0,ch); break; //将做括号压入栈Scase ')' :if(formula1->operate=='#') {printf("括号不匹配!!!\n");return 1;}else{do{sign=pop(formula1);formula1=sign->q;a=sign->op;if(a=='(') break;else if(priority(a)==4) ;else{enqueue(formula2,1,0,a);enqueue(formula4,1,0,a);}}while(a!='#');if(a=='#') {printf("括号不匹配!!!\n");return 1;}}case '+' :case '-' :case '*' :case '/' :while (formula1->operate!='#' && formula1->operate!='(' && priority(formula1->operate)>=priority(ch)){sign=pop(formula1);formula1=sign->q;enqueue(formula2,1,0,sign->op);enqueue(formula4,1,0, sign->op);}formula1=push(formula1,1,0,ch);break;case '#' : break;default: printf("ERROR!!!\n");return 1;}ch=getchar();}}while(ch!='#');//表达式扫描结束条件//表达式扫描结束后若栈中还有元素则依次弹出输入的后缀表达式中while (formula1->operate!='#'){sign=pop(formula1);formula1=sign->q;if(sign->op=='(') {printf("括号不匹配!!!\n");return 1;}else {enqueue(formula2,1,0,sign->op);enqueue(formula4,1,0,sign->op);}}printf("后缀表达式为:\n");do//后缀表达式的输出{mark=dequeue(formula2);if(mark->num==12345) break;if(mark->w==0){printf("%.3f",mark->num);free(mark);}else{printf("%c",mark->op);free(mark);}}while(1);printf("\n");/////////////////////////////////////////////////////////后缀表达式的计算////////////////////////////////////////////////////////float x,y;mark=dequeue(formula4);while (mark->num!=12345)//若队不为空{if (mark->w==0){formula3=push(formula3,0,mark->num,0);free(mark);}else{sign=pop(formula3);y =sign->num; formula3=sign->q;free(sign);//两次取操作数并交换次序sign=pop(formula3);x =sign->num; formula3=sign->q;free(sign);switch (mark->op)//计算周缀表达式的值{case '+' : formula3=push(formula3,0, x + y,0);break;case '-' : formula3=push(formula3,0, x - y,0);break;case '*' : formula3=push(formula3,0, x * y,0);break;case '/' : formula3=push(formula3,0, x / y,0);break;default:printf("ERROR!!!\n");return 0;}}mark = dequeue(formula4);//出队操作}printf("表达式的计算结果为：%.3f\n",pop(formula3)->num);return 0;}void main(){float sum;bool a;sum=change();//计算并转换后缀表达式getch();}*/。

《数据结构》课程设计报告课程设计题目：中缀表达式改后缀表达式并求值一. 实验目的·掌握栈的特征及基本操作，如入栈、出栈等，栈的顺序存储结构和链式存储结构的实现，以便在实际问题中灵活应用。

·掌握栈的典型应用——中缀表达式转后缀表达式，并利用后缀表达式求值。

二. 实验内容（一）中缀表达式转后缀表达式的方法：1.遇到操作数：直接输出（添加到后缀表达式中）2.栈为空时，遇到运算符，直接入栈3.遇到左括号：将其入栈4.遇到右括号：执行出栈操作，并将出栈的元素输出，直到弹出栈的是左括号，左括号不输出。

5.遇到其他运算符：加减乘除：弹出所有优先级大于或者等于该运算符的栈顶元素，然后将该运算符入栈6.最终将栈中的元素依次出栈，输出。

（二）三. 实验分析程序源码（要求对每个函数及主要代码加上注释语句），源码出处。

//// main.c// 后缀表达式求值//// Created by 颜彦闻on 14/12/2.// Copyright (c) 2014年颜彦闻. All rights reserved.//#include <stdio.h>#include <stdlib.h>#define StackSize 100#define QueueSize 100typedef char DataType;typedef struct{char data[100];int front,rear;}SeqQueue; //定义队列类型void InitQueue(SeqQueue *Q) //初始化队列{Q->front=0;Q->rear=0;}int QueueEmpty(SeqQueue Q) //判空{return Q.rear==Q.front;}void EnQueue(SeqQueue *Q,DataType x) //元素入队列函数{if((Q->rear+1)%QueueSize==Q->front)printf("Queue overflow");else{Q->data[Q->rear]=x;Q->rear=(Q->rear+1)%QueueSize;}}DataType DeQueue(SeqQueue *Q){char x;if(QueueEmpty(*Q))return0;else{x=Q->data[Q->front];Q->front=(Q->front+1)%QueueSize;return x;}}//栈的相关操作typedef struct{DataType data[100];int top;}SeqStack;void InitStack(SeqStack *S) //栈的初始化{S->top=-1;}void Push(SeqStack *S,DataType x) //进栈函数{if(S->top==StackSize-1)printf("stack overflow");else{S->top=S->top+1;S->data[S->top]=x;}}DataType Pop(SeqStack *S) //退栈顶指针函数{if(S->top==-1){printf("stack underflow");return0;}elsereturn S->data[S->top--];}DataType GetTop(SeqStack S) //取栈顶元素{if(S.top==-1){printf("stack empty");return0;}elsereturn S.data[S.top];}int Priority(DataType op) //求运算符优先级函数{switch(op){case'(':case'#':return0;case'-':case'+':return1;case'*':case'/':return2;}return -1;}void CTPostExp(SeqQueue *Q){SeqStack S;char c,t;InitStack(& S);Push(&S,'#');do{c=getchar();switch(c){case' ':break;case'1':case'2':case'3':case'4':case'5':case'6':case'7':case'8':case'9':EnQueue(Q ,c);break;case'(':Push(&S,c);break;case')':case'#':{do{t=Pop(&S);if(t!='('&&t!='#')EnQueue(Q ,t);}while(t!='('&&S.top!=-1);break;}case'+':case'-':case'*':case'/':while(Priority(c)<=Priority(GetTop(S))){t=Pop(&S);EnQueue(Q,t);}Push(&S,c);break;}}while(c!='#');}DataType CPostExp(SeqQueue Q){SeqStack S;char ch;int x,y;InitStack(&S);while(!QueueEmpty(Q)){ch=DeQueue(&Q);if(ch>='0'&&ch<='9')Push(&S,ch);else{y=Pop(&S)-'0';x=Pop(&S)-'0';switch(ch){case'+': Push(&S,(char)(x+y+'0'));break;case'-': Push(&S,(char)(x-y+'0'));break;case'*': Push(&S,(char)(x*y+'0'));break;case'/': Push(&S,(char)(x/y+'0'));break;}}}return GetTop(S);}int main(int argc, char *argv[]){SeqQueue Q;InitQueue(&Q);printf("输入表达式：\n");CTPostExp(&Q);printf("结果：%c\n",CPostExp(Q));printf("后缀表达式：");while(!QueueEmpty(Q))printf("%2c",DeQueue(&Q));printf("\n");system("PAUSE");return0;}四. 算法时间复杂度。

C语⾔计算器实现（中缀表⽰法后缀表⽰法）————————————————————————————————————————————实现原理：每个操作数都被依次压⼊栈中，当⼀个运算符到达时，从栈中弹出相应数⽬的操作数（对于⼆元运算符来说是两个操作数），把该运算符作⽤于弹出的操作数，并把运算结果再压⼊栈中- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -计算器（后缀表达式）相关知识：后缀表达式（逆波兰表⽰法）：在逆波兰中，所有运算符都跟在操作数后⾯，如下：(1 - 2) *(4 + 5) 采⽤逆波兰表⽰法表⽰为：1 2 - 4 5 + *，不需要圆括号，只要知道每个运算符需要⼏个操作数就不会引起歧义实现功能：输⼊后缀表达式，以换⾏结束，计算四则运算结果。

对于 1 2 - 4 5 + * 来说，⾸先把1和2压⼊到栈中，再⽤两者之差-1取代它们；然后将4和5压⼊到栈中，再⽤两者之和9取代它们。

最后从栈中取出栈顶的-1和9，并把它们的积-9压⼊到栈顶。

到达输⼊⾏的末尾时，把栈顶的值弹出来并打印。

伪代码：while 读⼊值不为换⾏时if 是数字压⼊栈中else if 是运算符弹出两个运算数，计算并压栈else 输⼊错误并退出end if读⼊值弹出最终结果并打印实现代码：1/* 实现功能：输⼊后缀表达式，以换⾏结束，计算四则运算结果 */2/* 这种后缀表⽰法只需要⼀个栈就可以了,遇到符号则弹运算数,但是中缀就不⼀样 */3 #include <stdio.h>4 #include <stdlib.h>5#define OK 16#define ERROR 07#define OVERFLOW -28#define STACK_INIT_SIZE 1009#define STACKINCREAMENT 1010 typedef int Status;11 typedef char SElemType;12 typedef struct13 {14 SElemType *top;15 SElemType *base;16int stacksize;17 } SqStack;18 Status InitStack(SqStack *s)19 {20 s->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));21if (!s->base) exit(OVERFLOW);22 s->top = s->base;23 s->stacksize = STACK_INIT_SIZE;24return OK;25 }26 Status Push(SqStack *s, SElemType e)27 {28if (s->top - s->base == s->stacksize)29 {30 s->base = (SElemType *)realloc(s->base, (s->stacksize + STACKINCREAMENT) * sizeof(SElemType)); 31if (!s->base) exit(OVERFLOW);32 s->top = s->base + s->stacksize;33 s->stacksize += STACKINCREAMENT;34 }35 s->top++;36 *(s->top) = e;37return OK;38 }39 Status Pop(SqStack *s, SElemType *e)40 {41if (s->top == s->base) exit(OVERFLOW);42 *e = *(s->top);43 s->top--;44return OK;45 }46 Status Empty(SqStack s)47 {48if (s.top - s.base == 0)49return OK;50else51return ERROR;52 }53int main()54 {55 SqStack OPND; //OPTR是运算符 OPND是运算数56char c, num1, num2;57 InitStack(&OPND);58while((c = getchar()) != '\n')59 {60switch(c)61 {62case'0':63case'1':64case'2':65case'3':66case'4':67case'5':68case'6':69case'7':70case'8':71case'9':72 Push(&OPND, c - '0');73break;74case'+':75 Pop(&OPND, &num2);76 Pop(&OPND, &num1);77 Push(&OPND, num1 + num2);78break;79case'-':80 Pop(&OPND, &num2);81 Pop(&OPND, &num1);82 Push(&OPND, num1 - num2);83break;84case'*':85 Pop(&OPND, &num2);86 Pop(&OPND, &num1);87 Push(&OPND, num1 * num2);88break;89case'/':90 Pop(&OPND, &num2);91 Pop(&OPND, &num1);92 Push(&OPND, num1 / num2);93break;94default:95break;96 }97 }98while(!Empty(OPND))99 {100 Pop(&OPND, &c);101 printf("%d ", c);102 }103return OK;104 }- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -计算器（中缀表⽰法）运算符优先级：+-*/()# +>><<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=0)>>>>0>>#<<<<<0=执⾏过程：在计算 #4+3*(5-10)/5# 时栈中的执⾏过程如下步骤输⼊字符执⾏操作OPTR OPND 1#Push(#)#24Push(4)#43+'#'<'+',Push(+)# +443Push(3)# + 4 35*'+'<'*',Push(*)# + * 4 36('*'<'(',Push(()# + * ( 4 375Push(5)# + * ( 4 3 58-'('<'-',Push(-)# + * ( - 4 3 5910Push(10)# + * ( - 4 3 5 1010)'-'>')',计算并压⼊结果# + * ( 4 3 -511'('=')',脱括号# + * 4 3 -5 12/'*'>'/'计算并压⼊结果# + 4 -1513'+'<'/',Push(/)# + / 4 -15145Push(5)# + / 4 -15 5 15#'/'>'#',计算并压⼊结果# + 4 -316'+'>'#',计算并压⼊结果#117'#'='#',脱括号1伪代码：初始化运算符栈；压⼊#；初始化运算数栈；获取输⼊；while 获取输⼊不为#或栈顶不为#if 输⼊的是数字压⼊运算数栈获取输⼊if 新输⼊的也是数字⼗位数百位数运算end ifelseswitch 运算符栈顶与当前输⼊优先级⽐较压⼊运算符栈获得输⼊弹出运算符栈顶（或#获得输⼊弹出运算符栈顶弹出两个运算数计算并将结果压⼊运算数栈//此时不获取新输⼊，该循环输⼊的运算符作为c重新进⼊循环end ifend while输出运算数栈中剩的运算数实现代码：1/* 只能运算-128~127之间的结果 */2 #include <stdio.h>3 #include <stdlib.h>4 #include <math.h>5#define OK 16#define ERROR 07#define SPILL -2 //math.h中已有OVERFLOW,则改⽤SPILL8#define STACK_INIT_SIZE 1009#define STACKINCREAMENT 1010 typedef char SElemType;11 typedef int Status;12 typedef struct13 {14 SElemType *top;15 SElemType *base;16int stacksize;17 } SqStack;18 Status InitStack(SqStack *s)19 {20 s->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));21if (!s->base)22 exit(SPILL);23 s->top = s->base;24 s->stacksize = STACK_INIT_SIZE;25return OK;26 }27 Status EmptyStack(SqStack s)28 {29if (s.top - s.base == 0)30return OK;31else32return ERROR;33 }34 Status Push(SqStack *s, SElemType e)35 {36if (s->top - s->base == s->stacksize)37 {38 s->base = (SElemType *)realloc(s->base, (s->stacksize + STACKINCREAMENT) * sizeof(SElemType)); 39if (!s->base)40 exit(SPILL);41 s->top = s->base + s->stacksize;42 s->stacksize += STACKINCREAMENT;43 }44 s->top ++;45 *(s->top) = e;46return OK;47 }48 Status Pop(SqStack *s, SElemType *e)49 {50if (s->top == s->base)51 exit(SPILL);52 *e = *(s->top);53 s->top--;54return OK;55 }56 SElemType GetTop(SqStack s)57 {58return *(s.top);59// *e = *(s.top);60// return OK;61 }62/* 判断如果是数字则返回OK,运算符返回ERROR,⾮法输⼊则退出 */63 Status InputJudge(SElemType c)64 {65switch(c)66 {67case'0':68case'1':69case'2':70case'3':71case'4':72case'5':73case'6':74case'7':75case'8':76case'9':77return OK;78break;79case'+':80case'-':81case'*':82case'/':83case'(':84case')':85case'#':86return ERROR;87break;88default:89 exit(SPILL);90break;91 }92 }93/* 当前输⼊的运算符和前⼀个运算符⽐较优先级 */94 SElemType PriorityJudge(SElemType optr1, SElemType optr2)95 {96int i, j;97char priorityTable[7][7] =98 {99 {'>', '>', '<', '<', '<', '>', '>'},100 {'>', '>', '<', '<', '<', '>', '>'},101 {'>', '>', '>', '>', '<', '>', '>'},102 {'>', '>', '>', '>', '<', '>', '>'},103 {'<', '<', '<', '<', '<', '=', '0'},104 {'>', '>', '>', '>', '0', '>', '>'},105 {'<', '<', '<', '<', '<', '0', '='}106 };107switch(optr1)108 {109case'+':110 i = 0;111break;112case'-':113 i = 1;114break;115case'*':116 i = 2;117break;118case'/':119 i = 3;120break;121case'(':122 i = 4;123break;124case')':125 i = 5;126break;127case'#':128 i = 6;129break;130 }131switch(optr2)132 {133case'+':134 j = 0;135break;136case'-':137 j = 1;138break;139case'*':140 j = 2;141break;142case'/':143 j = 3;144break;145case'(':146 j = 4;147break;148case')':149 j = 5;150break;151case'#':152 j = 6;153break;154 }155return priorityTable[i][j];156 }157/* 四则运算 */158 SElemType Calc(SElemType optr, SElemType num1, SElemType num2)159 {160switch(optr)161 {162case'+':163return (num1 + num2);164break;165case'-':166return (num1 - num2);167break;168case'*':169return (num1 * num2);170break;171case'/':172return (num1 / num2);173break;174 }175 }176int main()177 {178char c, optr, num1, num2, temp;179 SqStack OPND, OPTR;180 InitStack(&OPTR);181 Push(&OPTR, '#');182 InitStack(&OPND);183 c = getchar();184while(c != '#' || GetTop(OPTR) != '#')185// while(!EmptyStack(OPTR))186//严蔚敏⽼师书上的算法是判断输⼊⾮#或栈顶⾮#时循环,个⼈认为判断运算符栈不为空也可以,当初始化时压⼊的#闭合,结束运算187 {188if (InputJudge(c))189 {190 Push(&OPND, c - '0');191 c = getchar();192/* 当连续输⼊数字时,计算⼗位数和百位数 */193while(InputJudge(c))194 {195int i = 1;196 Pop(&OPND, &temp);197 Push(&OPND, temp * pow(10, i) + (c - '0'));198 i++;199 c = getchar();200 }201 }202else203switch(PriorityJudge(GetTop(OPTR), c))204 {205case'<':206 Push(&OPTR, c);207 c = getchar();208break;209case'=':210 Pop(&OPTR, &c);211 c = getchar();212break;213case'>':214 Pop(&OPTR, &optr);215 Pop(&OPND, &num2);216 Pop(&OPND, &num1);217 Push(&OPND, Calc(optr, num1, num2)); 218break;219 }220 }221while(!EmptyStack(OPND))222 {223 Pop(&OPND, &c);224 printf("%d\n", c);225 }226return OK;227 }。

实验三中缀表达式转换成后缀表达式，并按后缀表达式计算[实验目的]对中缀表达式转换成后缀表达式，然后按后缀表达式计算进行分析与设计，并上机运行。

使学生能通该实验理解对一个简单表达式的编译实现过程。

[实验要求]要求对中缀表达式转换成后缀表达式，然后按后缀表达式计算作设计性实验，并上机运行，写出实验报告。

[实验时数]2学时。

[实验内容]中缀表达式转换成后缀表达式，然后按后缀表达式计算，例如：A*(B+C)/D-E*(F+G)。

[实验环境]硬件坏境：实验室209、一人一台机子。

软件坏境：Windows XP、Visual studio 6.0[算法描述及实验步骤]根据本实验内容的要求，实验要实现的是一个中缀表达式转换成后缀表达式并输出。

通过设计一个算法来实现以上实验。

[调试过程]运行Visual studio 6.0。

打开事先编写的程序：中缀到后缀.cpp。

在Visual studio 6.0环境下进编译、调试、运行。

多次重复无错误后，输出结果。

[实验结果][实验总结][附录]#include<stack>#include<iostream>using namespace std;bool prior(char op1,char op2) {bool ret=false;switch (op1){case'+':case'-':switch(op2){case'+':case'-':case'*':case'/':ret= false;break;case'#':case'(':ret = true;break;}break;case'*':case'/':switch(op2){case'#':case'+':case'-':case'(':ret= true;break;case'*':case'/':ret= false;break;}break;}return ret;}int main(int argc, char* argv[]){char s[]="A*(B+C)/D-E*(F+G)";int k;for(k=0;k<17;k++){cout<<s[k];}cout<<endl;stack<char> operS;//操¨´作Á¡Â符¤?栈?int i=0;operS.push('#');while(s[i]!='\0'){if(s[i]==' '){i++;continue;}if(s[i]>='A' && s[i]<'Z' ) //是º?字Á?母?{cout<<s[i];}else//不?是º?字Á?母?{switch(s[i]){case'+':case'-':case'*':case'/':if(prior(s[i],operS.top()))//比À¨¨栈?顶£¤优®?先¨¨级?高?,直¡À接¨®进?栈?{operS.push(s[i]);}else if(operS.top()!='(') //比À¨¨栈?顶£¤优®?先¨¨级?低̨ª，ê?先¨¨出?栈?,s[i]进?栈?{cout<<operS.top();operS.pop();operS.push(s[i]);}break;case'(': //直¡À接¨®进?栈?operS.push(s[i]);break;case')': //匹£¤配?栈?内¨²的Ì?'(',都?出?栈?，ê?并¡é删¦?除y'(' while(operS.top()!='('){cout<<operS.top();operS.pop();}operS.pop();break;case'#':break;}}i++;}while(!operS.empty()){cout<<operS.top();operS.pop();}cout<<endl;int a;cin >> a;return 0;}[教师评语]。