使用栈实现中缀转后缀表达式及计算结果完整源码

c语言实现中缀,后缀,前缀表达式转换并求值c语言实现中缀,后缀,前缀表达式转换并求值九#include #include #define MAXNUM 100 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; 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(>=MAXNUM) 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(>=MAXNUM) 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); }voidhouzhuiqiuzhi(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(“结点有误”); brea k; } 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)//中缀表达式转化为后缀表达式{sqstack2OPTR; //运算符栈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(struct Node)); 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’{ switch (c) { case ‘+’: case ‘-’: case ‘*’: case ‘/’: case ‘%’: case ‘(‘:case ‘)’: case ‘\\n’: { if(n[0]>‘0’&&n[0]next=q; p=p->next; for(k=0;k{ for(j=0;j 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; }。

中缀表达式转后缀表达式（Java代码实现）后缀表达式求值后缀表达式⼜叫逆波兰表达式，其求值过程可以⽤到栈来辅助存储。

例如要求值的后缀表达式为：1 2 3 + 4 * + 5 -，则求值过程如下：1. 遍历表达式，遇到数字时直接⼊栈，栈结构如下 2.　接着读到 “+”操作符，则将栈顶和次栈顶元素出栈与操作符进⾏运算，执⾏ 2 + 3操作，并将结果5压⼊栈中，此时栈结构如下3. 继续读到4，是数字则直接压栈，此时栈结构如下 4. 继续向后读取，此时读取到操作符“*”，则将栈顶和次栈顶元素出栈与操作符进⾏运算，即执⾏ 5 * 4 ，然后将结果20压⼊栈中，此时栈结构如下 5. 继续向后读取，此时读到操作符“+”，则将栈顶和次栈顶元素出栈与操作符进⾏运算，即执⾏1 + 20，然后将结果21压⼊栈中，此时栈结构如下 6. 继续向后读取，此时读到数字5，则直接将数字压栈，栈结构如下 7. 读取到最后⼀个为操作符，将栈顶和次栈顶元素出栈与操作符进⾏运算，即执⾏ 21- 5（注意顺序次栈顶-栈顶）,然后将结果16压⼊栈中，此时栈结构如下 此时栈顶元素即为表达式的结果。

（注：为⽅便理解，这⾥栈顶指针向下移动后，上⾯元素直接去掉了，实际情况数据还会存在对应位置，只是通过栈顶指针读取不到，等待GC）中缀表达式转后缀表达式中缀表达式为我们⼈类能识别的⽅式，⽽后缀表达式是计算机进⾏运算的⽅式（即我们上述的过程)。

转换规则 1）我们使⽤⼀个stack栈结构存储操作符，⽤⼀个List结构存储后缀表达式结果 2）⾸先读取到数字，直接存⼊list中 3）当读取到左括号"("时，直接压栈，当读取到运算符时，分两种情况讨论 a.当运算符栈为空或者栈顶操作符的优先级⼩于当前运算符优先级时(如+和-的优先级低于 * 和 /)，直接⼊栈 b.当运算符不为空时且栈顶操作符的优先级⼤于或等于当前运算符优先级时，循环执⾏出栈操作并加⼊list中，直到遇到优先级⼩于当前运算符的元素为⽌。

#include<iostream>#include<string>using namespace std;template<class T>class arrStack{ //栈的定义,用来储存运算符private:int mSize;int top;T *arr;public:arrStack(int size){top=-1;mSize=size;arr=new T[mSize];}arrStack(){arr=new T[10];mSize=10;top=-1;}void clear(){top=-1;}bool push(const T item ){if(top==mSize-1){T*newArray=new T[mSize*2];for(int i=0;i<mSize;i++){newArray[i]=arr[i];}delete []arr;arr=newArray;top=mSize;mSize*=2;}arr[++top]=item;return true;}bool pop(T &item){if(top==-1){cout<<"This stack is empty,can't pop!"<<endl;return false;}else{item=arr[top--];return true;}}bool unpop(T &item){ //返回栈顶元素，不弹出if(top==-1){cout<<"This stack is empty,can't pop!"<<endl;return false;}else{item=arr[top];return true;}}bool isEmpty(){if(top==-1)return true;elsereturn false;}};bool isNumber(char ch){ //判断输入字符是否为数字 if(ch>='0'&&ch<='9')return true;elsereturn false;}bool isDecimalPoint(char ch){ //判断输入字符串是否为小数点if(ch=='.')return true;elsereturn false;}bool isOperator(char ch){ //判断输入字符是否为操作符if(ch=='+'||ch=='-'||ch=='*'||ch=='/')return true;elsereturn false;}bool isBracket(char ch){ //判断输入字符是否为括号if(ch=='('||ch==')')return true;elsereturn false;}int priority(char ch){ //判断优先级if(ch=='*'||ch=='/')return 2;else if(ch=='('||ch==')'){return 3;}else if(ch=='+'||ch=='-'){return 1;}else return -1;}bool postfixExp(string &infix,string &postfix){ //中缀转后缀/*char stackTopOperator='+';*/arrStack<char> stack;char stackTop=' '; //用来储存栈顶元素postfix="";if(infix.length()<1){cout<<"Wrong number of expression"<<endl;return false;}for(int i=0;i<(int)infix.length();i++){if(isNumber(infix[i])||infix[i]=='.'){postfix+=infix[i];}else if(infix[i]=='('){postfix+=" "; //除了数字，其他字符前面都加上空格，来合并数字。

数据结构代码中缀转后缀表达式算法及源代码#include<stdio.h>#include<stdlib.h>#include<math.h>#define MAX 100 /* 表达式最大长度 */ #define true 1#define false 0/* 定义数据栈 */typedef struct LinkStack1{float data;struct LinkStack1 *next; }LinkStack1,*Top1; nt initStack1(Top1 *t) /*数据栈初始化*/ i{*t=NULL;return true;}int push1(Top1 *t,float val) /*数据栈插入元素*/{Top1 p=(Top1)malloc(sizeof(LinkStack1));/* 开内存 */if(p==NULL)return false;p->data=val;p->next=*t;*t=p;return true;}float getTop1(Top1 *t) /*取数据栈元素*/ {return (*t)->data; }int pop1(Top1 *t,float *val) /*推出数据栈元素并存到*val中*/ {Top1 p=*t;if(p==0)return false;*t=p->next;*val=p->data;free(p); /* 释放所占内存 */return true;}/* 定义操作符栈 */typedef struct LinkStack2{int data;struct LinkStack2 *next; LinkStack2,*Top2; }int initStack2(Top2 *t) /*数据栈初始化*/ {*t=NULL;return true;}int push2(Top2 *t,char val) /*操作符栈插入元素*/ {Top2 p=(Top2)malloc(sizeof(LinkStack2)); /* 开内存 */ if(p==0)return false;p->data=val;p->next=*t;*t=p;return true;}int getTop2(Top2 *t) /*取操作符栈元素*/ {return (*t)->data; }int pop2(Top2 *t,char *val)Top2 p=*t;if(p==0)return false;*t=p->next;*val=p->data;free(p); /* 释放所占内存 */return true;}/* 计算 */float calc(float a, char op, float b) { int d,e; switch(op){case '+':return a+b; /* 计算+ */case '-':return a-b; /* 计算- */case '*':return a*b; /* 计算* */case '/': /* 计算/，若被除数为零，报错 */if(b==0){printf("Error Divisor is 0\n");return false;}return a/b;case '%': /* 计算%，若被取余数为零报错 */d=(int)a;e=(int)b;if(e==0){printf("Error Divisor is 0\n");return false;}return (float)(d%e);default:printf("Error !! not oprater\n"); /* 非操作符报错 */ return false;}}/* 判断操作符优先级 */char priority(char a,char b) {if(a=='='&&b=='\n')return'*'; /* '*' 表示结束 */if(a=='('&&b==')')return'#'; /* '#' 表示左右括号相遇 */ /* '<'、'>'、'=' 分别表示优先级:小于、大于、相等 */if(a=='=')return'<';if(b=='\n')return'>';if(a==')')return'>';if(a=='(')return'<';if(b=='(')return'<';if(b==')'&&a!='(')return'>';if((a=='+'||a=='-')&&(b=='/'||b=='*'||b=='%'))return'<';if((b=='+'||b=='-')&&(a=='/'||a=='*'||a=='%'))return'>';if((a=='+'||a=='-')&&(b=='+'||b=='-'))return'=';if((a=='*'||a=='/'||a=='%')&&(b=='*'||b=='/'||b=='%'))return'='; } /* 是否操作符 */int isOp(char m){if(m=='*'||m=='/'||m=='%'||m=='('||m==')'||m=='+'||m=='-'||m=='\n') return true;return false;}/* 中缀变后缀 */void Infix(char a[],char b[]) {char c,p,x;int i=0,j=0;Top2 op;initStack2(&op); /*初始化操作符栈*/push2(&op,'='); /* '='作为栈底元素 */while(a[i]!='\0'){if(!isOp(a[i])) /*是操作数，直接输出*/{b[j++]=a[i];}else{b[j++]=' '; /* 数字和数字用空格隔开 */switch(priority(getTop2(&op),a[i])) /*比较两个算符的优先级*/ {case'<':push2(&op,a[i]);/*当前算符优先级高，将其入操作符栈*/break;case'>':case'=':while((priority(getTop2(&op),a[i])=='=')||(priority(getTop2(&op),a[i])=='>')){pop2(&op,&c); /*当前算符优先级低，则取栈顶*/b[j++]=c;}if(priority(getTop2(&op),a[i])=='<')push2(&op,a[i]); /*出栈*/else{if(priority(getTop2(&op),a[i])=='#'){pop2(&op,&c); /*当前算符优先级低，则取栈顶*/i++;break;}else break;}break;case'#':/*左右括号相遇，则推出栈顶，并原表达式数组下标加1*/ pop2(&op,&c);i++;break;case'*': /*结束*/break;}}i++;}if(a[i]=='\0'){while(op->data!='=')/* 字符栈元素全都放到b数组中 */ {pop2(&op,&p);b[j++]=p;i++;}for(i=0;i<j;i++) /* 输出后缀表达式 */printf("%c",b[i]);}b[j]='\0'; /*为字符数组置结束标志 */}/*将数字字符转变成相应的数*/float charToNum(char a[],int *i) {float x=0.0;int k=0;while(a[*i]>='0'&&a[*i]<='9') /* 整数部分 */{x=x*10+a[*i]-'0';(*i)++;}if(a[*i]=='.') /*小数部分*/{(*i)++;while(a[*i]>='0'&&a[*i]<='9'){x=x*10+a[*i]-'0';(*i)++;k++; /*记录多少小数位数*/}}while(k!=0){x=x/10;k=k-1;}return x;}/* 第一种:后缀表达式计算 */float the_fir_Exp(char c[]){int i=0;float a,b,n;Top1 dig;initStack1(&dig); /*初始化操作数栈*/ push1(&dig,0);while(c[i]!='\0') /*为表达式的结束标志*/{if(!isOp(c[i])&&c[i]!=' ') /*为操作数*/{n=charToNum(c,&i);i=i-1; /*转换后 i值应该减一否则丢掉一个字符*/ push1(&dig,n);}else if(isOp(c[i])) /*为操作符*/{pop1(&dig,&a);/*取一操作数*/pop1(&dig,&b); /*取另一操作数*/push1(&dig,(calc(b,c[i],a))); /*计算，并压入栈*/ }i++;}return getTop1(&dig);}/* 第二种计算方法 */float the_sec_Exp(char a[]) {int i=0,j;char b[MAX],c;float m,n;Top2 op;Top1 dig;initStack2(&op); /*初始化操作符栈*/push2(&op,'=');initStack1(&dig); /*初始化操作数栈*/push1(&dig,0);while(a[i]!='\0'){if(!isOp(a[i])) /*是操作数*/{j=0;for(;!isOp(a[i])&&a[i]!='\0';i++)b[j++]=a[i];b[j]='+'; /*‘+’结束*/j=0;push1(&dig,(charToNum(b,&j))); /*转换，并压入栈*/}else{switch(priority(getTop2(&op),a[i]))/*比较两个算符的优先级*/ {case'<':push2(&op,a[i]); i++;break;case'>':case'=':pop2(&op,&c); /*取出操作符*/pop1(&dig,&m);/*取一操作数*/pop1(&dig,&n); /*取另一操作数*/push1(&dig,(calc(n,c,m))); /*计算，并压入栈*/ break;case'#':pop2(&op,&c);i++;break;case'*':break;}}}pop2(&op,&c); /*取出操作符*/while(c!='=') /*‘=’为操作符栈的结束标志*/ {pop1(&dig,&m); /*取一操作数*/pop1(&dig,&n); /*取另一操作数*/push1(&dig,(calc(n,c,m))); /*计算，并压入栈*/ pop2(&op,&c); /*取出操作符*/}return getTop1(&dig); /*返回值为数字栈栈顶*/ } /* 主函数 */void main(){loop: /* 确定再次输入数据计算，及输入错误时循环 */{int i,k,j;int z[MAX],y[MAX];char a[MAX]={""},b[MAX],ch;float m;z[MAX]="";y[MAX]=""; /* 初始化a[]/,z[],y[]*/printf("\nInput:");scanf("%s",&a); /* 输入表达式 *//* 容错四种情况 */for(i=0;a[i]!='\0';i++){if(!(a[i]>='0'&&a[i]<='9'||isOp(a[i])||a[i]=='.'))/* 1 非数字、小数点和操作符 */{printf("------");for(j=0;j<i;j++)printf("-");printf("^\n");printf("input wrong!!! intput again.\n");goto loop;}if(i>=MAX-1) /* 2 表达式越界 */{printf("input too long!!! intput again.\n");goto loop;}}for(i=0,j=0,k=0;a[i]!='\0';i++){if(a[i]=='(') z[k++]=i; /*z[k]为记录'('的位置 k表示(的数目*/ if(a[i]==')') y[j++]=i; /*y[k]为记录')'的位置 y表示 )的数目*/ }if(k!=j)/* 3 左右括号不相等 */{printf("------");if(k>j){for(i=0;i<z[k-1];i++)printf("-"); }elseif(k<j){ for(i=0;i<y[j-1];i++)printf("-");}printf("^\n");printf("input wrong!!! the NO. of '(' != ')'intput again:\n"); goto loop;}k=0; j=0; i=0;for(;a[i]!='\0';i++) /* 4 左括号在右括号右面 */{if(z[k++]>y[j++]){printf("------");for(i=0;i<z[k-1];i++)printf("-");printf("^\n");printf("input wrong!!! ')'first then '(' intput again:\n"); goto loop;}}/* 中缀变后缀,再计算 */printf("postfix expressions is:");Infix(a,b); /* 中缀变后缀 */m=the_fir_Exp(b); /* 后缀表达式计算 */printf("\nthe first method result is :%lf\n",m);/* 直接计算 */m=the_sec_Exp(a);printf("the second method result is :%lf\n",m);/* 是否再次输入数据计算 */printf("again?(y or n)\ninput:");loop_1:{ch=getch();if(ch=='y') /* y 再次输入 */goto loop;else if(ch=='n') /* n 退出 */exit(0);else /* 都不是提示输入错误 */{printf("\ninput wrong!again please!!!\ninput:"); goto loop_1;}}getch();}}。

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

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

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

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

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

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

【主要代码】#include <assert.h>#include <iostream.h>//#include <stdlib.h>const int stackIncreament=20;class SeqStack{private:char *elements;int top;int maxSize;void overflowProcess();public:SeqStack(int sz=50);~SeqStack(){ delete []elements; }void Push(const char &x);bool Pop(char &x);bool getTop(char &x);int isdigit(char ch);int isp(char ch1);int icp(char ch2);bool IsEmpty() const{ return (top == -1)? true:false; }bool IsFull() const{ return (top == maxSize-1)? true:false; }int getSize() const { return top+1; }void MakeEmpty() { top= -1; }};SeqStack::SeqStack(int sz){ top = -1; maxSize = sz; elements = new char[maxSize];assert(elements!=NULL);}void SeqStack::overflowProcess(){ char*newArray=new char[maxSize+stackIncreament];/* if (newArray==NULL){cerr<<"存储分配失败！"<<endl;exit(1);}*/for (int i = 0; i <= top; i++) newArray[i] = elements[i];maxSize= maxSize+stackIncreament;delete []elements; elements = newArray; }void SeqStack::Push(const char &x){if (IsFull()==true) overflowProcess();elements[++top]=x;}bool SeqStack::Pop(char &x){ if (IsEmpty() == true) return false;x = elements[top--]; return true;}bool SeqStack::getTop(char &x){ if (IsEmpty()==true) return false;x=elements[top]; return true;}int SeqStack::isdigit(char ch){ if(ch>='0'&&ch<='9'||ch=='.'||ch>='a'&&ch<='z'||ch>='A'&&ch<='Z') return 1; e lse return 0;}int SeqStack::isp(char ch1){ int val; switch(ch1){ case '#': val=0; break;case '(': val=1; break;case '*': case '/': case '%': val=5; break;case '+': case '-': val=3; break;case ')': val=6; break;}return val;}int SeqStack::icp(char ch2){ int val; switch(ch2){ case '#': val=0; break;case '(': val=6; break;case '*': case '/': case '%': val=4; break;case '+': case '-': val=2; break;case ')': val=1; break;} return val;}class Show:public SeqStack{ public:Show(int sz):opst(sz){} void Clear(); void Postfix();void Input();void Output(); private:SeqStack opst; char *infix; char *postfix;};void Show::Clear(){ opst.MakeEmpty();}void Show::Input(){ infix=new char[20];cout<<"请输入中缀表达式:"<<endl; cin>>infix;}void Show::Postfix(){ postfix=new char[20];cout<<"输出的后缀表达式为:"<<endl;SeqStack opst;char ch='#',ch1,op;opst.Push(ch);int i=0; ch=infix[i];while(opst.IsEmpty()==false&&ch!='#')if(opst.isdigit(ch)==1){ cout<<ch; i++;ch=infix[i];}else { cout<<" ";opst.getTop(ch1);if(opst.isp(ch1)<opst.icp(ch)){opst.Push(ch); i++;ch=infix[i];}elseif(opst.isp(ch1)>opst.icp(ch)){opst.Pop(op); if(op!='#') cout<<op;}else{opst.Pop(op); i++; c h=infix[i]; }} cout<<endl;}void main(){ Show Sh(100); Sh.Input(); Sh.Postfix();}【实验过程】【实验体会】一直都不理解为什么要加语句“if (newArray==NULL) {cerr<<"存储分配失败！"<<endl; exit(1); }*/”觉得此举可有可无，到现在为止去掉了此举后的程序照样运行。

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

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;//判断上一个字符是什么。

#include<stdio.h>#include<malloc.h>#include<string.h>#include<stdlib.h>#define MAX 100char string1[100]; //*定义字符数组，存放后缀表达式*//char string2[100];int j=0;struct node //*定义链栈结构*//{char data;int num;struct node *next;};struct node *Initialization() //*建立链栈*//{struct node *top;top=(struct node *)malloc(sizeof(struct node));top->data='@';top->num=0;top->next=NULL;return top;}struct node *tran(struct node *s) //*输入表达式，并将中缀表达式转化为后缀表达式函数*//{struct node *p,*top;int i;top=s;int m;char a;m=strlen(string1);for(i=0;i<=m;i++){a=string1[i];if('0'<=string1[i]&&string1[i]<='9'){string2[j]=string1[i];j++;}else{switch(a){case '(':{p=(struct node *)malloc(sizeof(struct node));p->data=a;p->next=top;top=p;break;}case '*':case '/':string2[j]=' ';j++;if((top->data=='*')||(top->data=='/')){string2[j]=top->data;j++; //比较输入运算符与栈顶的运算符优先级，若输入元素优先级高，先将栈顶运算符出栈，输入元素再进栈*//。

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;}```该程序通过读入一个中缀表达式，将其转换为后缀表达式并输出。