我们都知道给计算机一个运算式时计算机可以迅速计算出其结果，若运算式有错误，计算机也能立刻检查出错误并报告，那么计算机是如何做到的呢？
其实计算机在进行运算的过程中，将运算表达式换成了逆波兰表达式，这是一种不需要括号的后缀表达式（我们常用的是中缀表达式），再对该后缀表达式进行计算，进而得出答案；在中缀表达式转换的过程中，这些数据保存在栈中，需要计算时再利用栈先进后出的特点进行字符的匹配检查。
一，中缀表达式转后缀表达式
1，中缀表达式转后缀表达式遵循的原则
中缀表达式转后缀表达式的数据用栈来存储，在遍历中缀表达式的时遵循以下原则：
●对于数字，直接输出
●对于符号：
左括号：不管栈中是否有元素直接进栈
运算符：若栈为空：直接进栈
若栈中有元素，则与栈顶符号进行优先级比较；
若新符号优先级高（默认左括号优先级最低），则直接入栈；
否则就需要弹 出并输出栈顶元素，并将新符号压栈，
右括号：不断将栈顶符号弹出并输出，直到栈顶符号与右括号匹配（即栈顶符号 是左括号），再讲栈顶的左括号弹出即可（只需要弹出，不需要输出）
优先级大小：乘除号>加减号>左括号
●遍历结束后，将栈内的元素全部弹出并输出
2，中缀表达式转后缀表达式的图文举例（超详细）
下面以中缀表达式“1+3*(2+5)”转换为后缀表达式的过程为例
第一步：遍历中缀表达式，第一个读取到的字符是1，按照转换的原则“数字直接输出”，所以将‘1’直接添加到我们的结果中，如图：
第二步： 第二个读取到的字符是‘+’,为运算符，此时栈中为空，所以直接将‘+’入栈，如图：
第三步：遍历到‘3’，与第一步同理，数字直接输出，所以将‘3’添加到结果中，此时结果为1 3；
第四步：遍历到‘*’，栈不为空，所以与栈顶元素比较优先级，此时栈顶元素为‘+’，‘*’的优先级比‘+’号高，所以还是将‘*’直接入栈，与第二步步操作相同，这里就不多画图了。
第五步： 此时遍历到了‘（’，因为“左括号直接入栈”，所以同前一步一样，将‘（’入栈即可。
第六步：此时遍历到了‘’2”，是数字，同理与，第一步一样，将‘2’添加到结果中，此时结果为1 3 2
第七步：此时遍历到了‘+’，是运算符，所以需要与栈顶的‘（’比较优先级大小，‘+’的优先级高，所以将‘+’直接压栈即可。
第八步：此时遍历到了‘5’，是数字所以继续将‘5’添加到结果，此时遍历情况与结果如图：
第九步：遍历到了‘)’ ,所以需要进行括号匹配,从栈中不断弹出并输出栈顶元素,直到匹配到的栈顶元素是左括号，再将左括号弹出即可，具体步骤如图：
第十步：中缀表达式已经遍历完，但栈中还有元素，所以将栈中全部元素弹出并输出（添加到结果中）即可，最后如图：
此时的结果“1 3 2 5 + * +”就是我们的中缀表达式 “1+3*(2+5)”转换的后缀的表达式
3,编程实现中缀表达式转后缀表达式
1，引入链栈
因为该转换我是用的链栈实现的，所以我们先引入使用链栈需要的函数，方便待会进行操作，这里就不多讲了，对链栈不太熟悉的同学也可以看我的上一篇博客，链接如下：C语言数据结构篇——栈的链式存储_Grande joie的博客-CSDN博客_c语言栈的链式存储结构
下面为此题需要的链栈相关封装函数：
typedef struct node//数据节点，压栈和出栈都在栈顶进行(这里的栈顶指与头结点连接第一个数据节点) { char val;//数据域 struct node* next;//指针域 }pnode; typedef struct seqstack { int size;//记录栈的大小 pnode* top;//指向栈顶元素 }phead; phead* initstack()//创建栈 { phead* istack=(phead*)malloc(sizeof(phead));//为头节点分配空间 if(istack!=NULL)//健壮性判断 { istack->top=NULL; istack->size=0; } return istack;//返回创建好的头结点 } int isempty(phead* istack)//判断栈为是否空 { if(istack->top==NULL) { return 1;//栈为空 } return 0;//栈不为空 } pnode* seqstack_top(phead* istack)//获取栈顶元素的数据节点 { if(istack->size!=0)//栈不为空 { return istack->top;//返回的是栈顶的数据节点而不是栈顶的元素 } return NULL; } pnode* seqstack_pop(phead* istack)//弹出栈顶元素 { if(isempty(istack)==0)//栈不为空 { pnode* account=istack->top;//记录栈顶的数据节点 istack->top=istack->top->next;//指向栈顶下一个元素 istack->size--;//记录栈的大小 return account;//返回弹出的数据节点 } return NULL; } void seqstack_push(phead* istack,char x)//将字符压栈(入栈) { pnode* temp;//进行压栈的数据节点 temp=(pnode*)malloc(sizeof(pnode)); temp->val=x;//填充数据域 temp->next=istack->top;//连接栈顶的数据节点 istack->top=temp;//充当栈顶 istack->size++;//记录栈大小的变化 return; }
2，封装中缀转后缀需要的相关函数
链栈的相关函数我们已经引入，让我们再来封装中缀转后缀需要的函数，如下：
char buffer[256]={0};//即对数组中每个数据都初始化为'\0'(\0的ascill码是0) //上方的例子中始终有一个“结果”用来保存输出的数据，这里的buffer就充当“结果”，用来保存输出的数据 void char_put(char ch)//用来将字符放入结果串，方便使用 { static int index=0;//static定义静态变量,放函数中表示index只初始化一次,只保留index的改变 buffer[index++]=ch; } int priority(char ch)//返回该字符的优先级 { int ret=0;//可以达到题目中'('默认优先级最小的要求 switch(ch) { case '+'://case穿透,即上一个case没有break语句时会继续向下执行 case '-': ret=1; break; case '*': case '/': ret=2; break; default://这里直接break也可以 break; } return ret; } int is_number(char ch)//判断遍历到的字符是不是数字 { return(ch>='0'&&ch<='9');//数字返回1，否则返回0 } int is_operator(char ch)//判断遍历到的字符是不是运算符 { return(ch=='+'||ch=='-'||ch=='*'||ch=='/'); } int is_left(char ch)//是不是左括号 { return(ch=='('); } int is_right(char ch)//是不是右括号 { return(ch==')'); } int transform(char str[])//使用const保护数据,函数用来将中缀转换成后缀,str[]是中缀表达式 { phead* istack=initstack();//创建一个栈 int i=0;//作为遍历字符串的索引（下标） while(str[i]!='\0')//遍历整个字符串 { //判断是不是数字 if(is_number(str[i])==1) { if(is_number(str[i+1])==1)//后面1也是数字,则直接放 { char_put(str[i]);//数字直接放入结果串(即输出) } else//后面不是数字,添加一个空格作为分隔符（数字与运算符间加空格以解决多位数问题） { char_put(str[i]); char_put(' '); } } //判断是不是运算符 else if(is_operator((str[i]))==1) { if(str[i+1]=='0'&&str[i]=='/') { printf("ILLEGAL");//解决除数为0的问题 return 0; } if(isempty(istack)==0)//栈不为空 { while((isempty(istack)==0)&&(priority(str[i])<=(priority(seqstack_top(istack)->val))))//栈不为空并且新运算符优先级不高于栈顶 { char_put(seqstack_pop(istack)->val);//满足条件的栈顶就弹出直到不满足 char_put(' ');//同样为了解决多位数问题 } } seqstack_push(istack,str[i]);//再将该运算符入栈 } else if(is_left(str[i]))//左括号则直接入栈 { seqstack_push(istack,str[i]); } else if(is_right(str[i]))//判断是不是右括号 { while(is_left(seqstack_top(istack)->val)!=1)//栈顶不是左括号的情况 { char_put(seqstack_pop(istack)->val);//将栈顶元素弹出并存储到结果串 if(isempty(istack)==1)//栈为空仍未找到左括号 { printf("没有匹配到左括号\n"); return -1; } } //执行到此时则代表匹配到了左括号 seqstack_pop(istack); //弹出左括号,这里并不用保存,即两个括号相抵消 } else { printf("有不能识别的字符\n"); return -1; } i++; } //遍历完了已经 if(str[i]=='\0')//成功遍历到字符串末尾 { while(isempty(istack)==0)//弹出全部栈中元素 { if(seqstack_top(istack)->val=='(')//栈顶元素为左括号 { printf("有没有匹配到的'(',缺少')'\n"); return -1; } char_put(seqstack_pop(istack)->val);//将栈中元素放入最终串 } } else { printf("遍历没有完成！\n"); } return 1; }
3，完整代码
到这里我们中缀表达式换后缀表达式就完成了，让我们来试试：
#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct node//压栈和出栈都在栈顶进行(这里的栈顶指前一段) { char val;//数据 struct node* next;//指针 }pnode; typedef struct seqstack { int size;//记录栈的大小 pnode* top;//指向栈顶元素 }phead; phead* initstack()//创建栈 { phead* istack=(phead*)malloc(sizeof(phead));//为头节点分配空间 if(istack!=NULL)//健壮性判断 { istack->top=NULL; istack->size=0; } return istack; } int isempty(phead* istack)//判断栈为空 { if(istack->top==NULL) { return 1;//栈为空 } return 0;//栈不为空 } pnode* seqstack_top(phead* istack)//获取栈顶元素的数据节点 { if(istack->size!=0)//栈不为空 { return istack->top;//返回的是栈顶的数据节点而不是栈顶的元素 } return NULL; } pnode* seqstack_pop(phead* istack)//弹出栈顶元素 { if(isempty(istack)==0)//栈不为空 { pnode* account=istack->top;//记录栈顶的数据节点 istack->top=istack->top->next;//指向栈顶下一个元素 istack->size--;//记录栈的大小 return account;//返回弹出的数据节点 } return NULL; } void seqstack_push(phead* istack,char x)//压栈(入栈) { pnode* temp;//进行压栈的数据节点 temp=(pnode*)malloc(sizeof(pnode)); temp->val=x;//填充数据域 temp->next=istack->top;//连接栈顶的数据节点 istack->top=temp;//充当栈顶 istack->size++;//记录栈大小的变化 return; } //下面是中缀表达式转后缀表达式的函数 char buffer[256]={0};//即对数组中每个数据都初始化为'\0'(\0的ascill码是0) //buffer为结果串 void char_put(char ch)//用来将字符放入放入结果串 { static int index=0;//static定义静态变量,放函数中表示index只初始化一次,只保留index的改变 buffer[index++]=ch; } int priority(char ch)//用来比较优先级 { int ret=0; switch(ch) { case '+'://case穿透,即上一个case没有break语句时会继续向下执行 case '-': ret=1; break; case '*': case '/': ret=2; break; default://这里直接break也可以 break; } return ret; } int is_number(char ch)//是不是数字 { return(ch>='0'&&ch<='9');//数字返回1，否则返回0 } int is_operator(char ch)//是不是运算符 { return(ch=='+'||ch=='-'||ch=='*'||ch=='/'); } int is_left(char ch)//是不是左括号 { return(ch=='('); } int is_right(char ch)//是不是右括号 { return(ch==')'); } int transform(char str[])//使用const保护数据,函数用来将中缀转换成后缀 { phead* istack=initstack();//创建一个栈 int i=0; while(str[i]!='\0')//遍历整个字符串 { //判断是不是数字 if(is_number(str[i])==1) { if(is_number(str[i+1])==1)//后面1也是数字,则直接放 { char_put(str[i]);//数字直接放入结果串(即输出) } else//后面不是数字,添加一个空格作为分隔符 { char_put(str[i]); char_put(' '); } } else if(is_operator((str[i]))==1) { if(str[i+1]=='0'&&str[i]=='/') { printf("ILLEGAL"); return 0; } if(isempty(istack)==0)//栈不为空 { while((isempty(istack)==0)&&(priority(str[i])<=(priority(seqstack_top(istack)->val))))//栈不为空并且新运算符优先级不高于栈顶 { char_put(seqstack_pop(istack)->val);//满足条件的栈顶就弹出直到不满足条件 char_put(' '); } } seqstack_push(istack,str[i]);//再将该运算符入栈 } else if(is_left(str[i]))//左括号直接入栈 { seqstack_push(istack,str[i]); } else if(is_right(str[i]))//判断是不是右括号 { while(is_left(seqstack_top(istack)->val)!=1)//栈顶不是左括号的情况 { char_put(seqstack_pop(istack)->val);//弹出并存储到结果串 if(isempty(istack)==1)//栈为空仍未找到左括号 { printf("没有匹配到左括号\n"); return -1; } } //此时匹配到了左括号 seqstack_pop(istack); //弹出左括号,这里并不用保存,即两个括号相抵消 } else { printf("有不能识别的字符\n"); return -1; } i++; } //遍历完了已经 if(str[i]=='\0')//成功遍历到字符串末尾 { while(isempty(istack)==0)//弹出全部栈中元素 { if(seqstack_top(istack)->val=='(')//栈顶元素为左括号 { printf("有没有匹配到的'(',缺少')'\n"); return -1; } char_put(seqstack_pop(istack)->val);//将栈中元素放入最终串 } } else { printf("遍历没有完成！\n"); } return 1; } int main() { char str[1024]={0};//将数组每个元素赋值为'\0' printf("请输入四则运算表达式:\n"); scanf("%s",str); int number=transform(str); if(number==-1) { printf("表达式转换错误:\n"); } else if(number==1) { printf("转化后的表达式: %s\n",buffer); } else { return 0; } }
随便写一个中缀表达式看看效果吧。效果如下：
请输入四则运算表达式:
2*(1+2)-3
转化后的表达式: 2 1 2 +* 3 -
到这里我们的中缀表达式换后缀表达式就完成了，接下来就是对后缀表达式的计算了
二，后缀表达式的计算
将中缀表达式换成后缀表达式后，计算机会根据后缀表达式进行求值运算，计算过程中的数据也是存储在栈中，但相比中缀表达式转后缀表达式会更简单一点。
1，后缀表达式的计算原则
●对于数字，直接进栈
●对于符号，先弹出一个栈顶元素作为右操作数（即待会运算时放在运算符右边），再弹出一个元素作为左操作数，根据符号运算出结果，再将结果压入栈中。
●遍历结束，栈中剩下的最后一个数就是运算结果
2，后缀表达式计算的图文举例：
这里以刚转换好的后缀表达式“1 3 2 5 + * +”为例进行计算，对后缀表达式进行遍历；
第一~四步： 前四位都是数字，按照原则直接全部进栈，如图：
第五步：此时遍历到了‘+’号，所以将栈顶的‘5’弹出作为右操作数，再将‘2’弹出作为左操作数，计算2+5的运算结果为7，再将7压栈，此时栈中数据从栈顶到栈尾依次是为“7 3 1”，如图：
第六步：此时遍历到“*”号，则依次弹出两个元素并计算，即3*7=21，在将21入栈，此时栈中元素按栈顶到栈底为“21 1”；
第七步: 此时遍历到‘+’号，即的1+21=22；将22压栈
第八步：此时后缀表达式遍历完了且栈中只有一个元素，所以栈中的元素即为最后答案，所以结果为22
再回想一下我们原来的中缀表达式“1+3*（2+5）”，也等于22，说明我们的计算没有问题
3，编程实现后缀表达式的计算
引入链栈（整型）
因为计算过程中我们数据存在栈中，所以我们也要引入链栈，但是这里因为要计算压栈，以及把运算结果压栈等操作，这里链栈的数据节点的数据域为int类型更合适，对应的部分函数也需要更改返回值，所以需要对上方封装的链栈函数进行部分修改，这里我们就复制下来，改一小部分地方，再给这些函数改一个新的名字就可以了,此处栈涉及到的封装函数如下：
typedef struct node1//这里的栈是整型栈 { int val;//数据 struct node1* next;//指针 }pnode1; typedef struct seqstack1 { int size;//记录栈的大小 pnode1* top;//指向栈顶元素 }phead1; phead1* initstack1()//创建栈 { phead1* istack=(phead1*)malloc(sizeof(phead1));//为头节点分配空间 if(istack!=NULL)//健壮性判断 { istack->top=NULL; istack->size=0; } return istack; } int isempty1(phead1* istack)//判断栈为空 { if(istack->top==NULL) { return 1;//栈为空 } return 0;//栈不为空 } int seqstack_top1(phead1* istack)//获取栈顶元素 { if(istack->size!=0)//栈不为空 { return istack->top->val;//返回的是栈顶的数据 } return 99999; } int seqstack_pop1(phead1* istack)//弹出栈顶元素 { if(isempty1(istack)==0)//栈不为空 { int account=istack->top->val;//记录栈顶的数据节点 istack->top=istack->top->next;//指向栈顶下一个元素 istack->size--;//记录栈的大小 return account;//返回弹出的数据节点 } return 99999; } void seqstack_push1(phead1* istack,int x)//压栈(入栈) { pnode1* temp;//进行压栈的数据节点 temp=(pnode1*)malloc(sizeof(pnode1)); temp->val=x;//填充数据域 temp->next=istack->top;//连接栈顶的数据节点 istack->top=temp;//充当栈顶 istack->size++;//记录栈大小的变化 return; }
计算后缀表达式涉及的函数
int express(int left,int right,char op)//op为运算符,返回运算结果 { switch (op) { case '+': return left+right; case '-': return left-right; case '*': return left*right; case '/': if(right==0) { return 999; } return left/right; default: break; } return -1; } int getsize(phead1* stack)//获取链栈的大小 { return stack->size; } int calculate(char str[])//计算后缀表达式 { phead1* istack2=initstack1();//创建栈 int i=0; while(str[i]!='\0')//遍历整个后缀表达式 { char a[6]={0}; int index=0; if(is_number(str[i])==1) { while(is_number(str[i])==1) { a[index]=str[i]; index++; i++; } //成功读取数字 seqstack_push1(istack2,atoi(a));//将该整数入栈，stoi函数可以将字符串改成数字形式 } else if(is_operator(str[i])==1) { int right=seqstack_pop1(istack2); int left=seqstack_pop1(istack2); int ret=express(left,right,str[i]); if(ret==999)//被除数为0了 { printf("ILLEGAL"); return 999; } seqstack_push1(istack2,ret);//运算结果入栈 } else if(str[i]==' ')//因为多位数的原因，我们的中缀表达式会有空格出现，直接遍历过去就行 { } else { printf("error\n"); break; } i++; } if(str[i]=='\0'&&getsize(istack2)) { return seqstack_top1(istack2); } return 0; }
注意 ，计算后缀表达式涉及的函数包括前面的判断某个字符是不是数字，是不是操作符等函数，这里没有再多写
三，用栈实现四则运算的完整代码（先把中缀表达式换成后缀表达式，再计算后缀表达式）
#include<stdio.h> #include<stdlib.h> #include<string.h> typedef struct node//压栈和出栈都在栈顶进行(这里的栈顶指前一段) { char val;//数据 struct node* next;//指针 }pnode; typedef struct seqstack { int size;//记录栈的大小 pnode* top;//指向栈顶元素 }phead; phead* initstack()//创建栈 { phead* istack=(phead*)malloc(sizeof(phead));//为头节点分配空间 if(istack!=NULL)//健壮性判断 { istack->top=NULL; istack->size=0; } return istack; } int isempty(phead* istack)//判断栈为空 { if(istack->top==NULL) { return 1;//栈为空 } return 0;//栈不为空 } pnode* seqstack_top(phead* istack)//获取栈顶元素的数据节点 { if(istack->size!=0)//栈不为空 { return istack->top;//返回的是栈顶的数据节点而不是栈顶的元素 } return NULL; } pnode* seqstack_pop(phead* istack)//弹出栈顶元素 { if(isempty(istack)==0)//栈不为空 { pnode* account=istack->top;//记录栈顶的数据节点 istack->top=istack->top->next;//指向栈顶下一个元素 istack->size--;//记录栈的大小 return account;//返回弹出的数据节点 } return NULL; } void seqstack_push(phead* istack,char x)//压栈(入栈) { pnode* temp;//进行压栈的数据节点 temp=(pnode*)malloc(sizeof(pnode)); temp->val=x;//填充数据域 temp->next=istack->top;//连接栈顶的数据节点 istack->top=temp;//充当栈顶 istack->size++;//记录栈大小的变化 return; } //下面是中缀表达式转后缀表达式的函数 char buffer[256]={0};//即对数组中每个数据都初始化为'\0'(\0的ascill码是0) //buffer为结果串 void char_put(char ch)//用来将字符放入放入结果串 { static int index=0;//static定义静态变量,放函数中表示index只初始化一次,只保留index的改变 buffer[index++]=ch; } int priority(char ch)//用来比较优先级 { int ret=0; switch(ch) { case '+'://case穿透,即上一个case没有break语句时会继续向下执行 case '-': ret=1; break; case '*': case '/': ret=2; break; default://这里直接break也可以 break; } return ret; } int is_number(char ch)//是不是数字 { return(ch>='0'&&ch<='9');//数字返回1，否则返回0 } int is_operator(char ch)//是不是运算符 { return(ch=='+'||ch=='-'||ch=='*'||ch=='/'); } int is_left(char ch)//是不是左括号 { return(ch=='('); } int is_right(char ch)//是不是右括号 { return(ch==')'); } int transform(char str[])//使用const保护数据,函数用来将中缀转换成后缀 { phead* istack=initstack();//创建一个栈 int i=0; while(str[i]!='\0')//遍历整个字符串 { //判断是不是数字 if(is_number(str[i])==1) { if(is_number(str[i+1])==1)//后面1也是数字,则直接放 { char_put(str[i]);//数字直接放入结果串(即输出) } else//后面不是数字,添加一个空格作为分隔符 { char_put(str[i]); char_put(' '); } } else if(is_operator((str[i]))==1) { if(str[i+1]=='0'&&str[i]=='/') { printf("ILLEGAL"); return 0; } if(isempty(istack)==0)//栈不为空 { while((isempty(istack)==0)&&(priority(str[i])<=(priority(seqstack_top(istack)->val))))//栈不为空并且新运算符优先级不高于栈顶 { char_put(seqstack_pop(istack)->val);//满足条件的栈顶就弹出直到不满足条件 char_put(' '); } } seqstack_push(istack,str[i]);//再将该运算符入栈 } else if(is_left(str[i]))//左括号直接入栈 { seqstack_push(istack,str[i]); } else if(is_right(str[i]))//判断是不是右括号 { while(is_left(seqstack_top(istack)->val)!=1)//栈顶不是左括号的情况 { char_put(seqstack_pop(istack)->val);//弹出并存储到结果串 if(isempty(istack)==1)//栈为空仍未找到左括号 { printf("没有匹配到左括号\n"); return -1; } } //此时匹配到了左括号 seqstack_pop(istack); //弹出左括号,这里并不用保存,即两个括号相抵消 } else { printf("有不能识别的字符\n"); return -1; } i++; } //遍历完了已经 if(str[i]=='\0')//成功遍历到字符串末尾 { while(isempty(istack)==0)//弹出全部栈中元素 { if(seqstack_top(istack)->val=='(')//栈顶元素为左括号 { printf("有没有匹配到的'(',缺少')'\n"); return -1; } char_put(seqstack_pop(istack)->val);//将栈中元素放入最终串 } } else { printf("遍历没有完成！\n"); } return 1; } //下方为计算后缀表达式需要的函数 typedef struct node1//这里的栈是整型栈 { int val;//数据 struct node1* next;//指针 }pnode1; typedef struct seqstack1 { int size;//记录栈的大小 pnode1* top;//指向栈顶元素 }phead1; phead1* initstack1()//创建栈 { phead1* istack=(phead1*)malloc(sizeof(phead1));//为头节点分配空间 if(istack!=NULL)//健壮性判断 { istack->top=NULL; istack->size=0; } return istack; } int isempty1(phead1* istack)//判断栈为空 { if(istack->top==NULL) { return 1;//栈为空 } return 0;//栈不为空 } int seqstack_top1(phead1* istack)//获取栈顶元素 { if(istack->size!=0)//栈不为空 { return istack->top->val;//返回的是栈顶的数据 } return 99999; } int seqstack_pop1(phead1* istack)//弹出栈顶元素 { if(isempty1(istack)==0)//栈不为空 { int account=istack->top->val;//记录栈顶的数据节点 istack->top=istack->top->next;//指向栈顶下一个元素 istack->size--;//记录栈的大小 return account;//返回弹出的数据节点 } return 99999; } void seqstack_push1(phead1* istack,int x)//压栈(入栈) { pnode1* temp;//进行压栈的数据节点 temp=(pnode1*)malloc(sizeof(pnode1)); temp->val=x;//填充数据域 temp->next=istack->top;//连接栈顶的数据节点 istack->top=temp;//充当栈顶 istack->size++;//记录栈大小的变化 return; } int express(int left,int right,char op)//op为运算符,返回运算结果 { switch (op) { case '+': return left+right; case '-': return left-right; case '*': return left*right; case '/': if(right==0) { return 999; } return left/right; default: break; } return -1; } int getsize(phead1* stack) { return stack->size; } int calculate(char str[])//计算后缀表达式 { phead1* istack2=initstack1();//创建栈 int i=0; while(str[i]!='\0')//遍历整个后缀表达式 { char a[6]={0}; int index=0; if(is_number(str[i])==1) { while(is_number(str[i])==1) { a[index]=str[i]; index++; i++; } //成功读取数字 seqstack_push1(istack2,atoi(a));//将该整数入栈 } else if(is_operator(str[i])==1) { int right=seqstack_pop1(istack2); int left=seqstack_pop1(istack2); int ret=express(left,right,str[i]); if(ret==999)//被除数为0了 { printf("ILLEGAL"); return 999; } seqstack_push1(istack2,ret);//运算结果入栈 } else if(str[i]==' ') { } else { printf("error\n"); break; } i++; } if(str[i]=='\0'&&getsize(istack2)) { return seqstack_top1(istack2); } return 0; } int main() { char str[1024]={0};//将数组每个元素赋值为'\0' printf("请输入四则运算表达式:\n"); scanf("%s",str); int number=transform(str); if(number==-1) { printf("表达式转换错误:\n"); } else if(number==1) { printf("转化后的表达式: %s\n",buffer); } else { return 0; } //成功换成后缀表达式 //下方计算后缀表达式 int num=calculate(buffer); if(num==999) { return 0; } printf("%d\n",num); }
到这里我们终于完成了题目的要求，让我们随便写个中缀表达式运行一下，效果就是下面这样啦。
请输入四则运算表达式:
1+3*(2+5)
转化后的表达式: 1 3 2 5 +*+
22
大一学生数据结构学习中，如果有什么不对的地方或者更好的见解欢迎大家提出来，有什么疑问也欢迎私信，感谢阅读；
