有趣的数据结构算法11——实现中缀表达式到后缀表达式的转换

解题思路实现代码GITHUB下载连接

这是学习栈的最后一篇blog了，在上一篇博客里，讲述了如何利用栈计算后缀表达式的结果，但是谁会无缘无故用后缀表达式写一个式子在那里计算呢？这么仔细一想，岂不是…… 其实也不是完蛋，只要在写个程序完成中缀表达式到后缀表达式的转换即可。

解题思路

在上一篇博客里我已经简要介绍了什么是后缀表达式。还不了解的朋友可以看看我的上一篇博客。 https://blog.csdn.net/weixin_44791964/article/details/97143790 中缀表达式向后缀表达式的转换公式如下：

转换规则是这样的，转换时也需要利用到栈。 1、如果遇到的是数字，直接将其输出。 2、如果遇到操作符’(’、’*’、’/’，由于其优先级较高，直接进行入栈。 3、如果遇到操作符’)’，则取出其与’(‘之间的所有操作符，同时取出’(’。 4、如果遇到操作符’+’、’-’，如果之前曾经将’(‘压入栈，则取出其与’(‘之间的所有操作符，不取出’(’；如果之前未将’(‘压入栈，则取出所有操作符，因为在栈中的所有操作符的优先级都比最后一个’+’、’-'高。 5、如果输入到达末尾，弹出所有操作符。

假定待求后缀表达式的中缀表达式为：1+2+5*(3+6)-7。其转换结果为1 2 + 5 3 6 + * + 7 - ，其转换过程如下： 1、遍历表达式，遇到1，直接输出，此时输出为：1 2、接着读到‘+’号，压入栈。

3、接着读到2，直接输出，此时输出为：1 2 4、接着读到‘+’号，由于栈中的操作符优先级较高，所以首先元素出栈并输出，此时输出为1 2 +，再将新的‘+’号入栈。

5、接着读到5，直接输出，此时输出为：1 2 + 5 6、接着读到‘*’号和‘(’左括号，以此入栈。

7、接着读到3，直接输出，此时输出为：1 2 + 5 3 8、接着读到‘+’号，由于栈顶元素为’(’，无需读出任何元素，直接入栈。

9、接着读到6，直接输出，此时输出为：1 2 + 5 3 6 10、接着读到‘)’右括号，取出其与’(‘之间的所有操作符，同时取出’(’，此时输出为1 2 + 5 3 6 +

11、接着读到‘-’号，由于栈内已经没有’(’，读出所有栈内元素，此时输出为1 2 + 5 3 6 + * +，再将’-'号压入栈。

12、接着读到7，直接输出，此时输出为：1 2 + 5 3 6 + * + 7 13、由于输入完成，所有元素出栈，得到输出：1 2 + 5 3 6 + * + 7 -

实现代码

#include <stdio.h> #include <stdlib.h> #include <string.h> #define Initsize 30 #define Newsize 30 typedef char Ele; struct Stack{ Ele* Top; Ele* Base; int Stacksize; }; typedef struct Stack* stk; void init(stk); //函数声明 void push(stk p, Ele e); Ele pop(stk p); void init(stk p){ //初始化函数 p->Base = (Ele*)malloc(Initsize*sizeof(Ele)); if (p->Base == NULL){ printf("内存分配失败。"); exit(1); } p->Top = p->Base; p->Stacksize = Initsize; } void push(stk p, Ele e){ //入栈 int len; len = p->Top - p->Base; if ( len >= p->Stacksize) { //动态分配空间 p->Base = (Ele*)realloc(p->Base, (p->Stacksize + Newsize)*sizeof(Ele)); if (p->Base == NULL){ printf("内存分配失败。"); exit(1); } p->Stacksize = p->Stacksize + Newsize; p->Top = p->Base + len; } *(p->Top) = e; p->Top++; } Ele pop(stk p){ //出栈 Ele e; if (p->Top == p->Base){ printf("已经到达底端"); exit(0); } (p->Top)--; e = *(p->Top); return e; } int main(){ struct Stack p; //定义栈 Ele c,e[3]="0 "; //c用于接收键盘字符 //定义e[]是因为使用strcat函数要求两个输入量都是字符串，需要以\0结尾，不可以直接加入一个字符 Ele str[10],all[200]=""; //str用于保存输入小鼠，all用于存储得到的输出后缀表达式。 int i = 0; //temp量 init(&p); //初始化 printf("请输入一个算式："); scanf("%c", &c); while (c != '#') { while ((c <= '9' && c >= '0') || c == '.'){ //输入一个小数 str[i++] = c; if (i >= 10){ printf("输入数据过大"); exit(1); } scanf("%c", &c); if (!(c <= '9' && c >= '0') && c != '.'){ str[i++] = ' '; str[i] = '\0'; strcat(all, str); i = 0; break; } } if (c == '#') break; switch (c) //操作符判断 { case '(': case '*': case '/': //如果遇到操作符'('、'*'、'/'，由于其优先级较高，直接进行入栈。 push(&p, c); break; case '+': case '-': //如果是+号或者-号，如果之前曾经将'('压入栈，则取出其与'('之间的所有操作符，不取出'('； //如果之前未将'('压入栈，则取出所有操作符，因为在栈中的所有操作符的优先级都比最后一个'+'、'-'高。 while (p.Base != p.Top){ e[0] = pop(&p); if (e[0] == '*' || e[0] == '/' || e[0] == '+' || e[0] == '-'){ strcat(all, e); } else{ push(&p, e[0]); break; } } push(&p, c); break; case')': //如果遇到操作符')'，则取出其与'('之间的所有操作符，同时取出'('。 while ((e[0] = pop(&p)) != '('){ strcat(all, e); } default: break; } scanf("%c", &c); } //如果输入到达末尾，弹出所有操作符。 while (p.Base != p.Top){ e[0] = pop(&p); strcat(all, e); } printf("%s", all); return 0; }

GITHUB下载连接

https://github.com/bubbliiiing/Data-Structure-and-Algorithm

希望得到朋友们的喜欢。 有问题的朋友可以提问噢。