【Note详细图解】中缀表达式如何转为后缀表达式？数据结构

大家好，欢迎来到IT知识分享网。

中缀表达式

中缀表达式（中缀记法）是一个通用的算术或逻辑公式表示方法，操作符是以中缀形式处于操作数的中间（例：3 + 4），中缀表达式是人们常用的算术表示方法。

前缀或后缀记法不同的是，中缀记法中括号是必需的。计算过程中必须用括号将操作符和对应的操作数括起来，用于指示运算的次序。

后缀表达式

逆波兰表示法（Reverse Polish notation，RPN，或逆波兰记法），是一种是由波兰数学家扬·武卡谢维奇1920年引入的数学表达式方式，在逆波兰记法中，所有操作符置于操作数的后面，因此也被称为后缀表示法。逆波兰记法不需要括号来标识操作符的优先级。

中缀表达式转后缀表达式

中缀转后缀思路

1. 初始化两个栈：运算符栈S1；操作数栈S2
2. 从左向右扫描中缀表达式
3. 遇到操作数时，将其压入到操作数栈S2
4. 遇到运算符时，比较其与运算符栈S1栈顶运算符的优先级
5. 如果运算符栈S1为空，或栈顶运算符为左括号“ ( ”，或者优先级比栈顶运算符的优先级较高，则直接将此运算符压入栈中
6. 否则，将运算符栈S1中栈顶的运算符弹入并压到操作数栈S2中，再次进行与运算符栈S1栈顶运算符的优先级比较
7. 遇到括号时，如果遇到了左括号“ ( ”，则直接压入运算符栈S1；
8. 如果遇到右括号“ ) ”，则依次弹出运算符栈S1栈顶的运算符，并压入操作数栈S2，直到遇到左括号” ( “为止，此时将这一对括号丢弃
9. 重复步骤2至8，直到表达式的最右边
10. 将运算符栈S1剩余的运算符依次弹出并压入操作数栈S2
11. 拼接操作数栈S2中的元素并输出，结果即为中缀表达式所对应的后缀表达式

中缀转后缀图示

下图是以9-2*3+(5-2)*2为例子的完整过程。

中缀转后缀流程图

中缀转后缀代码分析

主函数

先初始化一下需要转化为后缀记法的字符串，然后给一个用来存储后缀表达式的数组，假设中缀转后缀的函数为MidtoLast，给这个函数传入中缀表达式的字符数组midstr，以及存储后缀表达式的字符数组laststr：

int main() { char midstr[] = "9-2*3+(5-2)*2";//中缀表达式 printf("中缀表达式为：%s\n", midstr); char laststr[100];//后缀表达式 MidtoLast(laststr, midstr); printf("后缀表达式为：%s\n", laststr); return 0; }

遇到操作数

遍历整个中缀字符串数组，遇到数字字符就直接进行存储，这里我们利用isdigit函数来判断是否数字字符，在下面相关总结的部分，会为大家详细讲解函数的使用方式，这里只先需要知道它的头文件是#include <ctype.h>；

for (int i = 0; midstr[i] != '\0';)//i有的情况是不++的 { if (isdigit(midstr[i]))//数字字符直接放到后缀表达式里 { laststr[j++] = midstr[i++]; } }

遇到运算符

在遇到运算符的时候：遇到第一个操作符就直接压入栈中，根据优先级来判断是谁先出栈谁后出栈，“*”“/”的优先级高于“+”“-”的优先级：

遇到括号

并且在遇到操作符（不是“)”）想要进栈，并且栈顶是“(”，就直接压入栈中：

for (int i = 0; midstr[i] != '\0';)//i有的情况是不++的 { else if ( top == 0 || midstr[i] == '(' || (midstr[i] == '*' || midstr[i] == '/') && (mystack[top - 1] == '+' || mystack[top - 1] == '-') || mystack[top - 1] == '(' && midstr[i] != ')') { mystack[top++] = midstr[i++]; } }

出栈

 遇到“)”，并且栈顶元素为“(”，则直接抵消：

for (int i = 0; midstr[i] != '\0';)//i有的情况是不++的 { else if (midstr[i] == ')' && mystack[top - 1] == '(')//直接抵消 { i++; top--; } }

剩余运算符全部出栈

将栈中的剩余元素都全部依次出栈：

else//直接出栈 { laststr[j++] = mystack[--top]; } while (top > 0) { laststr[j++] = mystack[--top]; } laststr[j] = '\0';//变为字符串

中缀转后缀完整代码

#include <stdio.h> #include <ctype.h> void MidtoLast(char* laststr, const char* midstr) { int j = 0;//后缀表达式 char mystack[100];//模拟栈 int top = 0;//栈顶指针，当前可以存放数据的下标 for (int i = 0; midstr[i] != '\0';)//i有的情况是不++的 { if (isdigit(midstr[i]))//数字字符直接放到后缀表达式里 laststr[j++] = midstr[i++]; else if (top == 0 || midstr[i] == '(' || (midstr[i] == '*' || midstr[i] == '/') && (mystack[top - 1] == '+' || mystack[top - 1] == '-') || mystack[top - 1] == '(' && midstr[i] != ')') mystack[top++] = midstr[i++]; else if (midstr[i] == ')' && mystack[top - 1] == '(')//直接抵消 { i++; top--; } else//直接出栈 laststr[j++] = mystack[--top]; } while (top > 0) { laststr[j++] = mystack[--top]; } laststr[j] = '\0';//变为字符串 } int main() { char midstr[] = "9-2*3+(5-2)*2";//中缀表达式 printf("中缀表达式为：%s\n", midstr); char laststr[100];//后缀表达式 MidtoLast(laststr, midstr); printf("后缀表达式为：%s\n", laststr); return 0; } 

相关知识点

isdigit函数：

实例：

#include <stdio.h> #include <stdlib.h> #include <ctype.h> int main() { char str[] = "1776ad"; int year; if (isdigit(str[0])) { year = atoi(str); printf("The year that followed %d was %d.\n", year, year + 1); } return 0; } 

运行结果：