提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档
文章目录
前言一、中缀表达式？后缀表达式？二、实现思路1.中缀表达式转后缀表达式2.计算后缀表达式 三、代码实现总结前言
作为我们最熟悉的表达式1+1而言，你是否知道其还被称为中缀表达式？
一、中缀表达式？后缀表达式？
中缀表达式中缀表达式实际上就是我们日常生活中常用的运算表达式，例如1+2+3,1+2x3等等。那么我们是如何计算的？
对于1+2+3，因为+和-的优先级相同，所以我们一般是从左向右依次进行加法计算。
对于1+2x3，因为x的优先级大于+，所以我们先进行乘法再进行加法计算。
在我们人看来这样中缀表达式(操作符在中间，操作数在两边)十分好计算，我们一下就知道(表达式并不很复杂的情况)，那一步应该计算，那一步后计算。但对于计算机而言，其处理中缀表达式，就只能一遍一遍的遍历表达式，在根据操作符的优先级来进行计算。这样效率太低，于是就有了后缀表达式(逆波兰表达式)的产生。后缀表达式
我们将操作数在前，操作符在后的表达式称为后缀表达式。
如下：
那么其是如何转换的？
1.确定中缀表达式中操作符的运算顺序
2.选择优先性最高的操作符，以(操作数 操作数 操作符)[第一个操作数是操作符左边的，第二个操作数是操作符右边的]的形式组成新的操作数。
重复以上操作，直到操作符全部排序完成。
如下：
现在我们知道了，中缀表达式如何转换为后缀表达式，那么如何对后缀表达式进行计算？
如下：
我们会发现，计算后缀表达式，并不需要考虑操作符的运算顺序问题，只需要从左向右遍历，遇到操作符就执行相应的操作即可。 那么如何用代码实现？
二、实现思路
我们这用栈的结构来实现下面两个问题。
1.中缀表达式转后缀表达式
我们用一个栈(s2)来存储还不能确定运算顺序的操作符，一个栈(s1)[当然使用数组也可以]来保存以确定顺序的字符串。
遇到操作数，直接压入s1中。遇到操作符，如果s2是空栈，直接压栈，不是则判断栈顶操作符的优先级是否大于或等于该操作符，如果优先级大于或等于，那么将栈顶元素出栈，继续判断栈顶元素的优先级。重复此过程，直到栈顶操作符的优先级小于该操作符或s2为空，那么将该操作符直接压栈。遇到’ ( '直接压入s2中。遇到’ ) ‘，开始弹出s2中栈顶元素，压入s1中，直到栈顶元素为’ ( '，弹出该字符。如果中缀表达式遍历完成，那么直接将s2中所以元素，压入s1中。
如下：
2.计算后缀表达式
我们创建一个栈(numsStack)来存放计算结果。
直接按从左向右的顺序依次读取后缀表达式
遇到操作数，直接压栈遇到操作符，弹出栈顶元素，做为左操作数，再次弹出栈顶元素，作为右操作数。让两个操作数执行相应的操作，并将操作结果作为新的操作数压栈
重复上述两步，最后在栈(numsStack)中只会有一个元素，也就是运算结果。
三、代码实现
我这里用Stack.h存放栈结构的创建，有关栈函数操作的声明，头文件的引用。Stack.c存放栈相关函数的实现。test.c存放中缀表达式转换后缀表达式并计算的实现
Stack.h
#pragma once#define _CRT_SECURE_NO_WARNINGS 1#include <stdio.h>#include <stdlib.h>#include <string.h>#include <assert.h>#include <stdbool.h>#define MaxSize 10#define MaxString 100typedef char STDataType;typedef struct Stack{STDataType* a;int top;int capacity;}ST;//初始化void StackInit(ST* ps);//销毁void StackDestroy(ST* ps);//压栈void StackPush(ST* ps, STDataType x);//弹栈void StackPop(ST* ps);//读取栈顶元素STDataType StackTop(ST* ps);//读取栈中元素个数int StackSize(ST* ps);//判空bool StackEmpty(ST* ps);
Stack.c
#include "stack.h"//void StackInit(ST* ps){ps->a = (STDataType*)malloc(sizeof(STDataType) * (MaxSize));ps->capacity = MaxSize;ps->top = 0;}//void StackPush(ST* ps, STDataType x){if (ps->capacity == ps->top){ps->a = (STDataType*)realloc(ps->a, sizeof(STDataType)*(2 * ps->capacity));ps->capacity *= 2;if (ps->a == NULL){return;}}ps->a[ps->top] = x;ps->top++;}//void StackPop(ST* ps){if (ps->top == 0){return;}ps->top--;}//STDataType StackTop(ST* ps){STDataType x = ps->a[ps->top - 1];return x;}//void StackDestroy(ST* ps){if (ps->a){free(ps->a);ps->a = NULL;ps->capacity = 0;ps->top = 0;}}//int StackSize(ST* ps){return ps->top;}//bool StackEmpty(ST* ps){return (ps->top == 0);}
test.c
#include "stack.h"//只能进行个位数的中缀转后缀并计算，因为数字10，是字符1和字符0的组合//直接顺序读取，遇到数字压栈，遇到操作符，pop前两个数字并进行相关计算，再将计算结果压栈int calPostfix(char* str){ST numsStack;StackInit(&numsStack);for (int i = 0; i < (int)strlen(str); i++){if (str[i] >= '0' && str[i] <= '9'){int x = str[i] - '0';StackPush(&numsStack, x);}else{//x右操作数int x = StackTop(&numsStack);StackPop(&numsStack);//y左操作数int y = StackTop(&numsStack);StackPop(&numsStack);switch (str[i]){case '+':y += x;break;case '-':y -= x;break;case '*':y *= x;break;case '/':y /= x;break;}StackPush(&numsStack, y);}}return StackTop(&numsStack);}//假定+,-的优先级是1， *,/的优先级是2，数字是-1 int compare(char ch){if (ch == '+' || ch == '-'){return 1;}else if (ch == '*' || ch == '/'){return 2;}else if (ch == '(' || ch == ')'){return 0;}else{return -1;}}//转换为后缀表达式//s1保存结果，s2临时保存操作符(优先级)//遇到数字，直接保存到s1中// 遇到操作符，如果此时s2为空，则直接push进s1中，否则比较s2中top处操作符优先级与此操作符的优先级// 如果top优先级大于和等于，再看s2下一个操作符。// 如果top优先级小于，将该操作符直接push进s2.//char* postfixNotation(char* str){//s1保存结果，s2临时保存操作符ST s1;ST s2;StackInit(&s1);StackInit(&s2);for (int i = 0; i < (int)strlen(str); i++){if (compare(str[i]) == -1){StackPush(&s1, str[i]);}else if (str[i] == '('){StackPush(&s2, str[i]);}else if (str[i] == ')'){while (StackTop(&s2) != '('){char x = StackTop(&s2);StackPush(&s1, x);StackPop(&s2);}StackPop(&s2);}else{if (!StackEmpty(&s2) && compare(StackTop(&s2)) >= compare(str[i])){while (!StackEmpty(&s2) && compare(StackTop(&s2)) >= compare(str[i])){char x = StackTop(&s2);StackPop(&s2);StackPush(&s1, x);}StackPush(&s2, str[i]);}else{StackPush(&s2, str[i]);}}}while (!StackEmpty(&s2)){char x = StackTop(&s2);StackPush(&s1, x);StackPop(&s2);}StackPush(&s1, '\0');return (char*)s1.a;}int main(){char str[MaxString];gets(str);strcpy(str, postfixNotation(str));printf("%s\n", str);int ret = calPostfix(str);printf("%d\n", ret);return 0;}
总结
以上就是我对于中缀表达式转后缀表达式的理解。如果那步有问题，感谢大佬们指点！！！
最后感谢观看！！！
