中缀表达式转换为后缀表达式

中缀转后缀表达式中缀表达式是我们平时最常见的表达式形式，例如：1 + 2 * 3。

但是在计算机中，我们更常使用后缀表达式来进行计算。

因此，将中缀表达式转换为后缀表达式是非常重要的。

一、中缀表达式中缀表达式是指运算符位于两个操作数之间的表达式。

例如：1 + 2 * 3。

在中缀表达式中，运算符的优先级是由括号来确定的。

括号内的表达式优先计算，同级别的运算符按照从左到右的顺序计算。

二、后缀表达式后缀表达式是指运算符位于两个操作数之后的表达式。

例如：1 2 3 * +。

在后缀表达式中，运算符的优先级是由运算符本身来确定的。

同级别的运算符按照从左到右的顺序计算。

三、中缀转后缀中缀表达式转换为后缀表达式的过程可以使用栈来实现。

具体步骤如下：1. 初始化两个栈：运算符栈和结果栈。

2. 从左到右扫描中缀表达式。

3. 如果遇到操作数，直接将其压入结果栈。

4. 如果遇到运算符，比较其与运算符栈栈顶的优先级。

5. 如果运算符栈为空，或栈顶运算符为左括号“（”，则直接将此运算符入栈。

6. 否则，若优先级比栈顶运算符的优先级高或相等，也将运算符压入运算符栈。

7. 否则，将运算符栈顶的运算符弹出并压入结果栈中，再次转到步骤4与新的栈顶运算符比较。

8. 如果遇到括号，如果是左括号“（”，则直接压入运算符栈；如果是右括号“）”，则依次弹出运算符栈顶的运算符，并压入结果栈中，直到遇到左括号为止，此时将这一对括号丢弃。

9. 重复步骤2至8，直到表达式的最右边。

10. 将运算符栈中剩余的运算符依次弹出并压入结果栈中。

11. 最后将结果栈中的元素依次弹出，即可得到后缀表达式。

四、总结中缀表达式转换为后缀表达式是一个非常重要的算法，它可以使我们更方便地进行计算。

在实际应用中，我们可以使用栈来实现这个算法。

通过这个算法的学习，我们可以更深入地理解计算机中的表达式计算过程。

中缀转后缀表达式算法
中缀表达式转后缀表达式（也称为逆波兰表达式）是一种将中缀表达式转换为后缀表达式的算法。

它的基本思想是将中缀表达式转换为一个后缀表达式，其中操作符位于操作数之后，而不是操作数之前。

中缀表达式转后缀表达式的算法步骤如下：
1. 从左到右扫描中缀表达式；
2. 如果读取的是操作数，则将其压入堆栈；
3. 如果读取的是运算符，则比较其与栈顶运算符的优先级：
（1）如果栈顶运算符的优先级高于或等于读取的运算符，则将栈顶运算符弹出，并将其压入输出队列；
（2）如果栈顶运算符的优先级低于读取的运算符，则将读取的运算符压入堆栈；
4. 重复步骤2和3，直到表达式末尾；
5. 将栈中所有元素依次弹出，压入输出队列，完成中缀表达式到后缀表达式的转换。

中缀表达式转后缀表达式算法的优点是它可以有效地将中缀表达式转换为后缀表达式，从而简化表达式的计算过程。

它的缺点是它需要记住操作符的优先级，并且需要使用堆栈来存储操作符，这可能会增加算法的复杂度。

总之，中缀表达式转后缀表达式算法是一种有效的算法，它可以有效地将中缀表达式转换为后缀表达式，从而简化表达式的计算过程。

将中缀表达式转换成后缀表达式的三种方法中缀表达式是我们平常最常见的表达式形式，但在计算机的运算过程中，我们常常需要将中缀表达式转换成后缀表达式，因为后缀表达式具有易于计算的特点。

那么，接下来我们将介绍三种将中缀表达式转换成后缀表达式的方法。

一、栈的方法这种方法是最常见的一种方法，也是比较易理解的一种方法。

我们可以借助栈来完成中缀表达式转换成后缀表达式的过程。

具体的操作如下：1. 声明一个操作符的栈stack（栈中存放操作符）和一个后缀表达式的列表res（列表中存放转换后的后缀表达式）。

2. 从左到右遍历中缀表达式。

3. 若当前字符为数字，则直接将该数字添加到res中。

4. 若当前字符为左括号“（”，则将其压入stack栈中。

5. 若当前字符为右括号“）”，则依次弹出stack栈中的操作符并加入到res中，直到遇到左括号为止。

6. 若当前字符为操作符，那么则需判断当前操作符与stack栈顶操作符的优先级，若当前操作符的优先级小于等于栈顶操作符，则弹出栈顶操作符并加入到res中，重复此步骤，直到当前操作符大于栈顶操作符优先级，最后将当前操作符压入stack栈。

7. 当遍历完整个中缀表达式后，若stack栈中还有剩余操作符，则依次弹出栈顶操作符并加入到res中。

8. 最终，res中的表达式就是转换后的后缀表达式。

二、递归调用方法这种方法是使用递归的方式来完成。

具体的操作如下：1. 若当前遍历的字符为数字，则直接输出该数字。

2. 若当前遍历的字符为左括号“（”，则递归读取该括号内的表达式。

3. 若当前遍历的字符为右括号“）”，则返回。

4. 若当前遍历的字符为操作符，“x”，“/”，“+”，“-”，则递归调用该表达式右边的操作符，比如“x”，“/”，然后再递归调用左边的操作符，比如“+”，“-”，然后输出左操作数和右操作数，最后输出当前操作符。

5. 最终，输出的表达式即为转换后的后缀表达式。

三、判断法这种方法也是比较常见的一种方法。

中缀表达式转后缀表达式---栈--⼆叉树---四则运算 我们平常书写的四则运算表达式属于中缀表达式，形式为"9+（3-1）*3+10/2"，因为所有的运算符号都在两操作数之间，所以称为中缀表达式。

我们使⽤中缀表达式来计算表达式的值，不过这种形式并不适合计算机求解。

接下来，我们将中缀表达式转化为后缀表达式，所谓的后缀表达式就是操作符位于操作数后⾯的不包含括号的算数表达式，也叫做逆波兰表达式。

1）⾸先介绍⼀种⼈⼯的转化⽅法()。

以"9+（3-1）*3+10/2"为例，按照运算的规则，找出⾸先计算的部分，这部分包含两个操作数和⼀个操作符，将操作符移动到两个操作数右侧，这就完成了第⼀部分的转换，将这部分看作⼀个操作数，按照运算规则，以相同的⽅法转换，转换过程如下：2）还可以利⽤⼆叉树求得后缀表达式，⾸先利⽤中缀表达式构造⼆叉树，数字是叶⼦节点，操作符为根节点。

每次找到“最后计算”的运算符，作为当前根节点，运算符左侧表达式作为左节点，右侧表达式作为右节点，然后递归处理()。

9+（3-1）*3+10/2对应的⼆叉树的构造过程如下图所⽰： 此⼆叉树做后序遍历就得到了后缀表达式。

对应代码：3）还可以利⽤栈来实现中缀表达式转化为后缀表达式。

转化⽅法如下所述：a.从左向右扫描表达式，如果是数字就输出，否则转b。

b.如果当前扫描的字符是")"，则栈顶元素出栈并输出⼀直到栈顶元素为"("，然后删除栈顶元素"("，并不输出。

c.如果扫描的字符或者栈顶元素是“(”，扫描的字符直接⼊栈。

即使扫描的字符是")"也不会⼊栈，因为如果是")"，会出栈⾄栈顶元素是"("。

d.如果扫描字符是"+"或者"-",则⼀直出栈⾄栈顶元素为"+"或者"-"或者"("。

算术表达式（中缀表达式）转换为后缀表达式将后缀表达式exp转换为postexp的过程如下：while(从exp读取字符ch，ch!='\0'){ 若ch为数字，将后继的数字都⼀次存放到postexp中，并以字符'#'标志数值串的结束； 若ch为左括号“（”，将此括号进栈到运算符栈op中； 若ch为右括号“）”，将运算符栈op依次出栈，直到“（”，并将“（”也出栈； 若ch为运算符，优先级不⼤于运算符op的栈顶运算符（除栈顶运算符为“（”外）的优先级，则依次出栈并存⼊到postexp中，然后将ch 进栈}若中缀表达式exp扫描完毕，将运算符栈op中的所有运算符依次出栈并存放到postexp中，就得到了后缀表达式。

完整代码：#include <stdio.h>#define MAXSIZE 50typedef char elemType;//运算符栈typedef struct{elemType data[MAXSIZE];int top;}OP;OP op;//中缀表达式转为后缀表达式void trans(char exp[],char postexp[]){op.top=-1;int i=0,j=0;char ch=exp[i];while(ch!='\0'){switch(ch){case'(':{op.top++;op.data[op.top] = ch;break;}case')':{while(op.data[op.top]!='('){postexp[j++]=op.data[op.top--];}op.top--; //去除 '('break;}case'+':case'-':{while(op.top!=-1&&op.data[op.top]!='('){postexp[j++]=op.data[op.top--];}op.top++;op.data[op.top]=ch;break;}case'*':case'/':{while(op.top!=-1&&(op.data[op.top]=='*'||op.data[op.top]=='/')){postexp[j++]=op.data[op.top];op.top--;}op.top++;op.data[op.top]=ch;break;}case'':break;default :{while(ch>='0'&&ch<='9'){postexp[j++]=ch;i++;ch=exp[i];}i--; //不是数字退后⼀个，⽤switch来进⾏判断 postexp[j++]='#'; //在数字结束后添加'#'以便区分}}i++;ch=exp[i];}while(op.top!=-1){ //将运算符栈中postexp[j++]=op.data[op.top--];}postexp[j]='\0';}。

中缀表达式转后缀表达式逆波兰表达式先说⼀下中缀表达式，平时我们使⽤的运算表达式就是中缀表达式，例如1+3*2，中缀表达式的特点就是：⼆元运算符总是置于与之相关的两个运算对象之间⼈读起来⽐较好理解，但是计算机处理起来就很⿇烦，运算顺序往往因表达式的内容⽽定，不具规律性后缀表达式，后缀表达式的特点就是：每⼀运算符都置于其运算对象之后，以上⾯的中缀表达式1+2*3为例⼦，转为后缀表达式就是123*+下⾯先分析怎么把中缀表达式转换为后缀表达式，这⾥我们考虑六种操作符'+'、'-'、'*'、'/'、'('、')'，完成中缀转后缀我们需要两个数组，都以栈的⽅式来操作，⼀个数组⽤来存放后缀表达式（char num[100]），⼀个数组⽤来临时存放操作数（char opera[100]）（这⾥说临时存放，是因为最后都要⼊栈到后缀表达式数组num中，这个数组就相当于⼀个中转站）1、从左往右扫描中缀表达式（这⾥我们以1*(2+3)为例）2、如果是数字那么将其直接⼊栈到数组num中3、如果是操作数，需要进⼀步判断（1）如果是左括号'('直接⼊栈到数组opera中（2）如果是运算符（'+'、'-'、'*'、'/'），先判断数组opera的栈顶的操作数的优先级（如果是空栈那么直接⼊栈到数组opera），如果是左括号那么直接⼊栈到数组opera中，如果栈顶是运算符，且栈顶运算符的优先级⼤于该运算符那么将栈顶的运算符出栈，并⼊栈到数组num中，重复步骤3，如果栈顶运算符优先级⼩于该运算符，那么直接将该运算符⼊栈到opera中（3）如果是右括号')'，那么说明在opera数组中⼀定有⼀个左括号与之对应（在你没输错的情况下），那么将opera中的运算符依次出栈，并⼊栈到num中，直到遇到左括号'('（注意左括号不⽤⼊栈到num）4、如果中缀表达式扫描完了，那么将opera中的操作数依次出栈，并⼊栈到num中就可以了，如果没有没有扫描完重复1-3步上⾯就是中缀表达式转后缀表达式的步骤了，下⾯⽤图来直观的了解⼀下这个过程需要注意的是：opera中操作数，越靠近栈顶，优先级越⾼，下⾯附上实现代码View Code后缀表达式的计算完成了中缀表达式转后缀表达式，接下来就是后缀表达式的计算了，后缀表达式的计算⽐中缀转后缀要稍微简单⼀点，只需要对我们转换好的后缀表达式从左往右依次扫描，并依次⼊栈就⾏了，意思是只需要⽤⼀个数组（double num[100]）就OK了需要考虑的情况如下1、如果是数字，那么直接⼊栈到num中2、如果是运算符，将栈顶的两个数字出栈（因为我们考虑的运算符加、减、乘、除都是双⽬运算符，只需要两个操作数），出栈后对两个数字进⾏相应的运算，并将运算结果⼊栈3、直到遇到'\0'下⾯⽤⼏张图，来直观了解下这个过程，以上⾯转换好的后缀表达式"123+*"为例（这⾥⽤ss来存储后缀表达式，num来存储计算结果，注意不要与上⾯图中num搞混淆了）（注意：这⾥将计算结果5⼊栈后，栈顶从之前的[3]变成[2]）到这⾥后缀表达式的计算就结束了，下⾯附上实现代码[](javascript:void(0)1 #include <stdio.h>2 #include <stdlib.h>34 #define MAX 10056 void JudgeFopen_s(errno_t err); /* 判断⽂件打开是否成功 */7 void ReadFile(FILE *fp, char *ss); /* 读取⽂件内容 */8 double TransformCtoD(char ch); /* 将char类型数组的每⼀个元素转换为double */9 void CalculateAndPush(double *num, int *i, int *j, char mm); /* 计算结果并⼊栈 */1011 int main()12 {13 FILE *fp;14 errno_t err;1516 char ss[MAX]; /* 存储逆波兰表达式 */17 int i = 0;18 int j = 0;19 double num[MAX]; /* 栈 */2021 err = fopen_s(&fp, "E:\\ww.txt", "r");2223 JudgeFopen_s(err); /* 判断⽂件打开是否成功 */24 ReadFile(fp, ss); /* 读取⽂件内容，存储到ss中*/2526 while (ss[i] != '\0')27 {28 if (ss[i] >= '0' && ss[i] <= '9') /* 如果是数字 */29 {30 /* 因为num是char类型的，需要转换为double类型⽅便计算 */31 num[j] = TransformCtoD(ss[i]); /* 将数字存储到栈中 */32 j++;33 i++;34 }35 else if (ss[i] == '+' || ss[i] == '-' || ss[i] == '*' || ss[i] == '/')36 {37 CalculateAndPush(num, &i, &j, ss[i]); /* 计算结果并⼊栈 */38 }39 else if (ss[i] == '\n') /* 如果是换⾏符，结束循环*/40 {41 break;42 }43 }4445 printf("%lf", num[0]);4647 return 0;48 }4950 /* Function: 计算结果并⼊栈 */51 void CalculateAndPush(double *num, int *i, int *j, char mm)52 {53 switch (mm)54 {55 case '+':56 {57 num[(*j)-2] = num[(*j)-1] + num[(*j)-2];58 (*j)--;59 (*i)++;60 break;61 }62 case '-':63 {64 num[(*j)-2] = num[(*j)-1] - num[(*j)-2];65 (*j)--;66 (*i)++;67 break;68 }69 case '*':70 {71 num[(*j)-2] = num[(*j)-1] * num[(*j)-2];72 (*j)--;73 (*i)++;74 break;75 }76 case '/':77 {78 num[(*j)-2] = num[(*j)-1] / num[(*j)-2];79 (*j)--;80 (*i)++;81 break;82 }83 default:84 {85 exit(0);86 }87 }88 }89 /* Function: 判断⽂件打开是否成功 */90 void JudgeFopen_s(errno_t err)91 {92 if (err != 0)93 {94 printf("⽂件打开失败\n");95 system("pause");96 exit(0);97 }98 }99100 /* Function: 读取⽂件内容*/101 void ReadFile(FILE *fp, char *ss)102 {103 int i = 0;104105 while (!feof(fp))106 {107 fscanf_s(fp, "%c", &ss[i]);108 i++;109 }110 ss[i-1] = '\0';111 }112113 /* Function: 将char类型数组的每⼀个元素转换为double */ 114 double TransformCtoD(char ch)115 {116 return (double)(ch - '0');117 }。

将中缀表达式转换为后缀表达式需要使用栈数据结构。

具体步骤如下：1. 读入中缀表达式，遇到数字时将其输出，遇到左括号时将其压入栈中。

2. 读入运算符，如果该运算符优先级高于栈顶运算符的优先级，则将栈顶元素弹出并输出，直到遇到优先级更高的运算符或遇到右括号为止。

3. 如果该运算符优先级等于栈顶运算符的优先级，则将该运算符压入栈中。

4. 如果该运算符优先级低于栈顶运算符的优先级，则忽略该运算符。

5. 重复上述步骤，直到读完整个中缀表达式。

6. 将栈中的元素依次弹出并输出，即为转换后的后缀表达式。

例如，对于中缀表达式a + b * c + (d * e + f) * g，其转换成后缀表达式的步骤如下：1. 读到a，直接输出。

2. 读到+，将+ 压入栈中。

3. 读到b，直接输出。

4. 读到*，将* 压入栈中。

5. 读到c，直接输出。

6. 读到+，将栈顶的* 弹出并输出，然后将+ 压入栈中。

7. 读到(，将( 压入栈中。

8. 读到d，直接输出。

9. 读到*，将* 压入栈中。

10. 读到e，直接输出。

11. 读到+，将栈顶的* 弹出并输出，然后将+ 压入栈中。

12. 读到f，直接输出。

13. 读到)，将栈顶的+ 弹出并输出，直到遇到左括号为止。

此时右括号")" 的优先级最高，所以直接将其弹出并输出。

然后继续弹出并输出左括号"(" 前遇到的运算符和操作数，直到遇到右括号为止。

此时右括号")" 前已经没有运算符和操作数了，所以直接将其弹出并输出。

14. 读到*，将* 压入栈中。

15. 读到g，直接输出。

16. 中缀表达式已经读完，将栈中的元素依次弹出并输出，得到后缀表达式a b * c + d * e + f * g + 。

中缀表达式转后缀表达式 先看⼏个中缀表达式和它们对应的后缀表达式的例⼦ 可以看到操作数a, b, c 在中缀表达式中的顺序和在后缀表达式中的顺序是⼀致的，但操作符的顺序可能不⼀致，因为在中缀表达式中操作符有优先级，括号也能改变运算的优先级，这些都要在后缀表达式中体现出来，后缀表达式中没有括号。

那怎么转化呢？ 1，创建⼀个变量，初始化为空的字符串，来表⽰要完成的后缀表达式，创建⼀个字符栈，⽤来存储操作符 2，从左向右依次扫描中缀表达式， 遇到操作数，直接加到后缀表达式的后⾯，因为，在中缀表达式和后缀表达式中，操作数的顺序是⼀样的， 遇到操作符，要先存起来，存到栈中，因为操作符有优先级，它要和后⾯的操作符⽐较优先级，然后才能决定把它放到什么哪个位置。

如果栈为空，直接把操作符放⼊栈中 如果栈不为空，⽐较优先级。

如果遇到的操作符⽐栈顶中的操作符优先级⾼，把遇到的操作符放⼊栈中。

如果遇到的操作符和栈顶操作符的优先级相等，这要考虑操作符的结合性，它是从左到右结合，还是从右到左结合。

从左到右接合，就是操作数属于它前⾯的操作符⽽不是它后⾯操作符。

+, - , * , / 就是从左向右结合，⽐如a-b+c中的b 是-的操作数，⽽不是+的操作数，整个表达式，也是从左向右计算的。

从右向左结合，操作数属于它前⾯的操作符⽽不是它后⾯操作符，⽐如阶乘。

a ^ b ^ c， b是第⼆个^的操作数，⽽不是第⼀个^的操作数，整个表达式也是从右向左计算，a ^ (b ^ c)。

如果从左向右接合，那就弹栈，把操作符放到后缀表达式中，如果从右向左结合，则把遇到的操作符放⼊栈中(和优先级⾼的情况⼀致) 如果遇到的操作符⽐栈顶中的操作符优先级低，那就弹栈，把操作符放到后缀表达式中 遇到(，放到字符栈，因为要等到)才能知道怎么操作。

遇到)，依次从字栈中弹栈，放到后缀表达式中，直到遇到(, 遇到(, 要把它弹栈，然后舍弃掉。

3，循环完毕，如果字符栈中还有操作符，依次弹栈放到后缀表达式中，最终栈为空，得到完整的后缀表达式。

中缀转后缀并输出运算步骤从中缀表达式转换为后缀表达式的过程中，需要遵循一定的规则和算法。

下面将具体介绍中缀转后缀的步骤及其运算过程。

一、引言中缀表达式是我们日常生活中最常见的表达式形式，例如：2 + 3 * 4。

但是，对于计算机来说，中缀表达式并不方便进行计算，因此需要将其转换为后缀表达式。

后缀表达式也被称为逆波兰表达式，它的计算规则更加简单明了。

二、中缀转后缀的规则和算法1. 创建一个空的栈，用于存储运算符。

2. 从左到右遍历中缀表达式的每个元素。

3. 如果当前元素是操作数，则直接输出到后缀表达式。

4. 如果当前元素是左括号"("，则将其压入栈中。

5. 如果当前元素是右括号")"，则将栈中的运算符依次弹出并输出到后缀表达式，直到遇到左括号为止。

注意：左括号不输出。

6. 如果当前元素是运算符，则判断栈顶运算符的优先级：- 若栈为空，则直接将当前运算符压入栈中。

- 若栈不为空，且当前运算符的优先级小于等于栈顶运算符的优先级，则将栈顶运算符弹出并输出到后缀表达式，直到栈为空或者栈顶运算符的优先级小于当前运算符。

- 将当前运算符压入栈中。

7. 遍历完中缀表达式后，如果栈中还有运算符，则依次弹出并输出到后缀表达式。

三、运算过程示例考虑中缀表达式："2 + 3 * 4 - (5 + 6) / 7"1. 创建空栈和空后缀表达式。

2. 从左到右遍历中缀表达式的每个元素：- 遇到"2"，为操作数，直接输出到后缀表达式。

- 遇到"+"，为运算符，将其压入栈中。

- 遇到"3"，为操作数，直接输出到后缀表达式。

- 遇到"*"，为运算符，将其压入栈中。

- 遇到"4"，为操作数，直接输出到后缀表达式。

- 遇到"-"，为运算符，栈顶为"*"，优先级高于"-"，因此将"*"弹出并输出到后缀表达式，然后将"-"压入栈中。

中缀式和后缀式的相互转换中缀式和后缀式是数学表达式的两种常见表示方式。

中缀式是我们常见的表达式形式，例如"3 + 4 * 5"，而后缀式是将运算符放在操作数后面表示，例如"3 4 5 * +"。

将中缀式转换为后缀式可以通过使用栈和优先级规则来完成。

具体步骤如下：1. 创建一个空栈和一个空字符串后缀表达式2. 从左到右扫描中缀表达式的每个元素3. 如果遇到操作数，则将其添加到后缀表达式中4. 如果遇到运算符，则将其与栈顶运算符进行比较：- 如果栈为空或栈顶是左括号"("，则将运算符入栈- 如果运算符优先级高于栈顶运算符，则将运算符入栈- 否则，将栈顶运算符弹出并添加到后缀表达式中，直到栈为空或栈顶是左括号为止，然后将当前运算符入栈5. 如果遇到左括号"("，则将其入栈6. 如果遇到右括号")"，则将栈顶运算符弹出并添加到后缀表达式中，直到遇到左括号为止，然后将左括号弹出（左括号不添加到后缀表达式中）7. 扫描完整个中缀表达式后，将栈中剩余的运算符依次弹出并添加到后缀表达式中8. 后缀表达式即为转换结果例如，将中缀式"3 + 4 * 5"转换为后缀式的过程如下：中缀表达式： 3 + 4 * 5初始化：栈为空，后缀表达式为空扫描 3：后缀表达式：3扫描 +：栈为空，运算符入栈扫描 4：后缀表达式：3 4扫描 *：栈顶运算符优先级低于当前运算符，运算符入栈扫描 5：后缀表达式：3 4 5扫描完毕，将栈中剩余运算符弹出：后缀表达式：3 4 5 * +因此，中缀式"3 + 4 * 5"转化为后缀式"3 4 5 * +"。

将后缀式转换为中缀式可以通过使用栈和逆序扫描后缀表达式的方式来完成。

具体步骤如下：1. 创建一个空栈2. 从左到右逆序扫描后缀表达式的每个元素3. 如果遇到操作数，则将其入栈4. 如果遇到运算符，则从栈中弹出两个操作数，并将运算符与操作数组合成一个中缀表达式，并将该中缀表达式入栈5. 扫描完整个后缀表达式后，栈顶的中缀表达式即为转换结果例如，将后缀式"3 4 5 * +"转换为中缀式的过程如下：后缀表达式：3 4 5 * +初始化：栈为空从右到左逆序扫描：扫描 +：弹出操作数5和4，组合为中缀表达式"4 + 5"，入栈扫描 *：弹出操作数4和中缀表达式"4 + 5"，组合为中缀表达式"(4 + 5) * 4"，入栈扫描 3：入栈扫描完毕，栈顶的中缀表达式即为转换结果：中缀表达式："(4 + 5) * 3"因此，后缀式"3 4 5 * +"转化为中缀式"(4 + 5) * 3"。

算法笔记--中缀表达式转后缀表达式后缀表达式计算中缀表达式转后缀表达式规则中缀表达式a + b*c + (d * e + f) * g，转换成后缀表达式则为a b c * + d e * f + g * +转换过程需要⽤到栈，具体过程如下：1 如果遇到操作数，我们就直接将其输出。

2 如果遇到操作符，则我们将其放⼊到栈中，遇到左括号时我们也将其放⼊栈中。

3 如果遇到⼀个右括号，则将栈元素弹出，将弹出的操作符输出直到遇到左括号为⽌。

注意，左括号只弹出并不输出。

4 如果遇到任何其他的操作符，如+, *, (等，从栈中弹出元素直到遇到发现更低优先级的元素(或者栈为空)为⽌。

弹出完这些元素后，才将遇到的操作符压⼊到栈中。

有⼀点需要注意，只有在遇到 )的情况下我们才弹出( ，其他情况我们都不会弹出( 。

即：若操作符op的优先级⾼于栈顶操作符的优先级，则压⼊操作符栈若操作符op的优先级⼩于等于栈顶操作符的优先级，则将操作栈的操作符不断弹出到后缀表达式中，直到op的优先级⾼于栈顶操作符的优先级5 如果我们读到了输⼊的末尾，则将栈中所有元素依次弹出。

实例a +b *c + (d *e + f) * g1. ⾸先读到a，直接输出。

2. 读到“+”，将其放⼊到栈中。

3. 读到b，直接输出。

此时栈和输出的情况如下：4. 读到“*”，因为栈顶元素"+"优先级⽐" * " 低，所以将" * "直接压⼊栈中。

5. 读到c，直接输出。

此时栈和输出情况如下：6. 读到" + "，因为栈顶元素" * "的优先级⽐它⾼，所以弹出" * "并输出，同理，栈中下⼀个元素" + "优先级与读到的操作符" + "⼀样，所以也要弹出并输出。

然后再将读到的" + "压⼊栈中。

中缀表达式转换为后缀表达式中缀表达式转换成后缀表达式 1、概述 可以看到，后缀表达式适合计算式进⾏运算，但是⼈却不太容易写出来，尤其是表达式很长得情况下，因此在开发中，需要将中缀表达式转成后缀表达式。

2、具体步骤1.初始化两个栈：运算符栈s1和储存中间结果的栈s2；2.从左⾄右扫描中缀表达式；3.遇到操作数时，将其压s2；4.遇到运算符时，⽐较其与s1栈顶运算符的优先级：　（1）如果s1为空，或栈顶运算符为左括号“(”，则直接将此运算符⼊栈；　（2）否则，若优先级⽐栈顶运算符的⾼，也将运算符压⼊s1；　（3）否则，将s1栈顶的运算符弹出并压⼊到s2中，再次转到(4.1)与s1中新的栈顶运算符相⽐较；5.遇到括号时：　（1）如果是左括号"("，则直接压⼊s1　（2）如果是右括号")"，则依次弹出s1栈顶的运算符，并压⼊s2，直到遇到左括号为⽌，此时将这⼀对括号丢弃6.重复步骤2⾄5，直到表达式的最右边7.将s1中剩余的运算符依次弹出并压⼊s28.依次弹出s2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式 3、案例 将中缀表达式 "1+((2+3)*4)-5" 转换为后缀表达式的过程如下： 结果为："1 2 3 + 4 * 5 - " 4、思路分析⽰意图 5、代码实现1import java.util.ArrayList;2import java.util.List;3import java.util.Stack;45/**6 * 把中缀表达式转成后缀表达式7 *8*/9public class ToSuffixExpression {1011public static void main(String[] args) {12// 完成⼀个中缀表达式转成后缀表达式13// 说明14// 1. 1+((2+3)*4)-5 => 转成 123 + 4 * + 5-15// 2. 因为对 str进⾏操作不⽅便，先将中缀表达式存⼊ list16// 3.将得到的中缀表达式对应的 list转成 =>后缀表达式对应的list17// 即[1,+,(,(,2,+,3,),*,4,),-,5] => [1,2,3,+,4,*,+,5,-]1819 String expression = "1+((2+3)*4)-5";20 List<String> list = toInfixExpressionList(expression);21 System.out.println("中缀表达式对应的list="+list);22 List<String> list2 = parseSuffixExpressionList(list);23 System.out.println("后缀表达式对应的list="+list2);24 }2526//⽅法：将得到的中缀表达式对应的 list转成 =>后缀表达式对应的list27public static List<String> parseSuffixExpressionList(List<String> ls) {28//定义两个栈29 Stack<String> s1 = new Stack<String>(); // 符号栈3031//说明：因为 s2这个栈，在整个转换过程中，没有pop操作，后⾯还需要逆序输出 32//所以，把 s2 这个栈换成 List<String> 即可33//Stack<String> s2 = new Stack<String>(); // 存储中间结果的栈34 List<String> s2 = new ArrayList<String>(); //存储中间结果的list3536//遍历 ls37for(String item : ls) {38//如果是⼀个栈，就加⼊到s239if(item.matches("\\d+")) {40 s2.add(item);41 } else if (item.equals("(")) {42 s1.push(item);43 } else if (item.equals(")")) {44// 如果是右括号，则依次弹出s1栈顶的运算符，并压⼊ s2,知道遇到左括号为⽌，此时将这⼀对括号丢弃4546while(!s1.peek().equals("(")) {47 s2.add(s1.pop());48 }49 s1.pop(); // 将左括号弹出，消除⼩括号50 } else {51// 当 item 的优先级⼩于或等于栈顶运算符，将s1栈顶的运算符弹出并压⼊s2中，再次转到4.1与s1中新的栈顶运算符相⽐较 52//问题：缺少⽐较优先级⾼低的⽅法53while(s1.size() != 0 && Operation.getValue(s1.peek()) >= Operation.getValue(item)) {54 s2.add(s1.pop());55 }56//还需要将 item 压⼊栈中57 s1.push(item);58 }59 }6061//将s1中剩余的运算符依次弹出加⼊s262while(s1.size()!=0) {63 s2.add(s1.pop());64 }6566return s2; //因为存放到list中，因此，按顺序输出就是对应的后缀表达式对应的 list67 }686970// ⽅法：将中缀表达式转成对应的 list71public static List<String> toInfixExpressionList(String s) {72// 定义⼀个 list，存放中缀表达式对应的内容73 List<String> ls = new ArrayList<String>();74int i = 0; // 指针，⽤于遍历中缀表达式字符串75 String str; // 做对多位数的拼接⼯作76char c; // 每遍历到⼀个字符，就放⼊到 c7778do {79// 如果c是⼀个⾮数字,就需要加⼊到 ls80if ((c = s.charAt(i)) < 48 || (c = s.charAt(i)) > 57) {81 ls.add("" + c);82 i++; // i后移83 } else { // 如果是数字，考虑多位数问题84 str = ""; // 将 str置空85while (i < s.length() && (c = s.charAt(i)) >= 48 && (c = s.charAt(i)) <= 57) {86 str += c; // 拼接87 i++;88 }89 ls.add(str);90 }9192 } while (i < s.length());93return ls; // 返回94 }95 }9697/**98 * 可以返回⼀个运算符的对应的优先级99 *100*/101public class Operation {102private static int ADD = 1;103private static int SUB = 1;104private static int MUL = 2;105private static int DIV = 2;106107// 写⼀个⽅法，返回对应的优先级数字108public static int getValue(String operation) { 109int result = 0;110switch(operation) {111case "+":112 result = ADD;113break;114case "-":115 result = SUB;116break;117case "*":118 result = MUL;119break;120case "/":121 result = DIV;122break;123default:124 System.out.println("不存在该运算符"); 125break;126 }127return result;128 }129 }。

中缀表达式转后缀表达式 c++代码中缀表达式是人类表达算术运算的一种方式，但是对于计算机来说却不那么方便，因为计算机更容易处理后缀表达式。

因此，我们需要找到一种转换方法，将中缀表达式转换为后缀表达式。

本文将介绍一种使用栈来实现中缀表达式转后缀表达式的方法，并提供相关的C++代码参考。

1. 什么是中缀表达式中缀表达式是一种常用的算术表达式表示法，它使用操作符在两个操作数中间，例如：2 + 3(a + b) * c(a > b) && (c < d)这种表示方法是人类思考数学问题时使用的方式，但是对于计算机来说，它不是最方便的表示方法，因为需要考虑运算符优先级和结合性等问题。

2. 什么是后缀表达式后缀表达式也被称为逆波兰表达式，它使用操作符在两个操作数之后，例如：2 3 +a b + c *a b > c d < &&后缀表达式消除了括号和运算符优先级等问题，因此非常适合计算机使用。

3. 中缀表达式转换为后缀表达式的过程中缀表达式转后缀表达式的过程可以使用栈来实现。

具体步骤如下：1) 创建一个空栈，并将后缀表达式的结果存储在一个空字符串中。

2) 从左向右遍历中缀表达式，每次遇到一个运算符或操作数时执行以下操作：- 如果是操作数，将其添加到结果字符串中。

- 如果是左括号，将其压入栈中。

- 如果是右括号，则弹出栈中的元素，直到遇到左括号。

每个弹出的元素都添加到结果字符串中，但不包括左括号。

- 如果是运算符，则比较其与栈顶元素的优先级。

如果栈顶元素的优先级大于或等于当前运算符的优先级，则弹出栈顶元素并添加到结果字符串中。

重复此步骤直到栈为空或栈顶元素的优先级小于当前运算符的优先级。

然后将当前运算符压入栈中。

3) 如果所有输入都已处理，则弹出栈中所有元素并将其添加到结果字符串中，直到栈为空。

4. 栈的实现在使用栈来实现中缀表达式转换为后缀表达式时，我们需要实现以下三个基本操作：- push: 在栈顶添加一个元素。

中缀表达式转后缀表达式详解中缀表达式和后缀表达式是两种常见的数学表达式形式。

中缀表达式是我们通常使用的表达式形式，即运算符位于操作数的中间，例如：'2 + 3'。

而后缀表达式（也称为逆波兰表达式）是一种更为简洁和易于计算机处理的表达式形式，其中运算符位于操作数的后面，例如：'2 3 +'。

将中缀表达式转换为后缀表达式的主要目的是减少表达式的复杂性，使其更容易被计算机处理。

转换过程涉及使用栈来保存运算符，并按照一定的规则重新排列表达式中的元素。

下面是将中缀表达式转换为后缀表达式的步骤：1. 创建一个空栈和一个空列表，用于保存转换后的后缀表达式。

2. 从左到右遍历中缀表达式的每个元素。

3. 如果遇到操作数（数字），将其添加到后缀表达式列表中。

4. 如果遇到左括号'('，将其推入栈中。

5. 如果遇到操作符，比较其与栈顶操作符的优先级。

a. 如果栈为空或栈顶为左括号'('，则将操作符推入栈中。

b. 如果操作符的优先级大于栈顶操作符的优先级，将其推入栈中。

c. 如果操作符的优先级小于或等于栈顶操作符的优先级，将栈顶操作符弹出并添加到后缀表达式列表中，然后将操作符推入栈中。

6. 如果遇到右括号')'，将栈中的操作符弹出并添加到后缀表达式列表中，直到遇到左括号'('。

注意，左右括号不会被添加到后缀表达式中。

7. 当中缀表达式遍历完毕后，将栈中剩余的操作符依次弹出并添加到后缀表达式列表中。

8. 后缀表达式列表即为转换后的后缀表达式。

例如，将中缀表达式 '2 + 3 * 4' 转换为后缀表达式的步骤如下：中缀表达式：2 + 3 * 4后缀表达式列表（初始为空）：[]遍历中缀表达式的每个元素：1. 遇到操作数2，添加到后缀表达式列表中：[2]2. 遇到操作符+，将其推入栈中：[+]3. 遇到操作数3，添加到后缀表达式列表中：[2, 3]4. 遇到操作符*，将其推入栈中：[+, *]5. 遇到操作数4，添加到后缀表达式列表中：[2, 3, 4]6. 中缀表达式遍历完毕，将栈中剩余的操作符弹出并添加到后缀表达式列表中：[2, 3, 4, *]最终转换后的后缀表达式为：'2 3 4 * +'后缀表达式的计算可以通过遍历列表中的元素来完成。

中缀表达式转后缀表达式的方法中缀表达式是我们日常数学运算中最常用的表达方式，它是以操作符放在两个操作数之间的形式表示算式的。

例如，2+3就是一个中缀表达式。

但是在计算机程序中，中缀表达式存在着很多问题，我们需要把它转换成后缀表达式来方便计算机程序的处理。

本文将介绍中缀表达式转换成后缀表达式的方法。

一、什么是后缀表达式后缀表达式是一种更加容易计算机处理的表达方式，它就是把中缀表达式中的每个操作符放到操作数之后。

例如，2+3变成2 3+，3*4+5变成3 4*5+。

后缀表达式没有括号，更加简洁明了。

这种表达方式被广泛应用在计算器、编译器等领域。

二、为什么需要把中缀表达式转换成后缀表达式计算机程序在处理中缀表达式时，需要考虑优先级和括号等复杂的问题，因此非常费时间。

而把中缀表达式转换成后缀表达式之后，计算机程序就可以直接读取后缀表达式，不需要再考虑优先级和括号等问题，计算速度更快，程序也更加简单。

三、中缀表达式转后缀表达式的方法1.用栈实现中缀表达式转后缀表达式的方法中，最常用的就是用栈来实现。

具体步骤如下：（1）遍历中缀表达式中的每一个元素；（2）运用以下规则：a.如果该元素为数字，则直接加入到结果序列中；b.如果该元素为左括号，将其入栈；c.如果该元素为右括号，将栈中元素依次弹出，直到遇到左括号，将弹出的操作符依次加入到结果序列中；d.如果该元素为操作符，则将其与栈顶元素比较，如果其优先级大于等于栈顶操作符的优先级，则直接入栈，否则将栈顶操作符弹出加入到结果序列中，再将该操作符入栈；e.重复以上步骤，直到遍历完所有元素。

（3）最终将栈中剩余的操作符全部弹出，加入到结果序列中。

下面通过一个例子来演示以下使用栈实现中缀表达式转后缀表达式的过程：中缀表达式： A + B * C - D / E1.初始化栈S。

2.扫描中缀表达式从左到右，若读到的是操作数，则直接输出到后缀表达式中。

3.若遇到操作符，则判断当前操作符与栈顶操作符的优先级，若优先级低于等于栈顶操作符，则弹出栈顶操作符并输出到后缀表达式中，直到扫描到栈顶操作符优先级低于当前操作符或栈为空。

c++ 中缀转后缀表达式摘要：1.C++中缀转后缀表达式的概念2.中缀转后缀的转换方法3.转换过程中的数据结构和算法4.实际应用案例和注意事项正文：C++中缀转后缀表达式在C++编程语言中，表达式是程序设计中常见的概念。

表达式分为中缀表达式和后缀表达式两种形式。

中缀表达式是运算符写在运算对象的中间，而后缀表达式则是运算对象写在运算符的后面。

为了方便编程和计算，有时候需要将中缀表达式转换为后缀表达式。

下面我们来探讨一下C++中缀转后缀表达式的相关知识。

一、C++中缀转后缀表达式的概念中缀转后缀表达式是指将一个中缀表达式转换为一个后缀表达式的过程。

例如，给定中缀表达式"a + b * c"，转换后的后缀表达式为"ab + c *"。

在后缀表达式中，运算符位于运算对象的后面，这样可以方便计算。

二、中缀转后缀的转换方法中缀转后缀的转换方法有多种，其中一种比较常见的方法是采用栈来实现。

具体步骤如下：1.初始化一个空栈。

2.从中缀表达式的左端开始，依次将每个运算对象和运算符入栈。

3.当遇到运算对象时，将其入栈；当遇到运算符时，进行以下操作：a.弹出栈顶的两个运算对象，记为a 和b。

b.将弹出的运算对象a 和当前运算符进行运算，得到一个新的运算对象。

c.将新运算对象入栈。

4.当栈为空时，转换完成。

此时栈中的元素就是后缀表达式的运算对象序列。

三、转换过程中的数据结构和算法在转换过程中，需要使用栈这种数据结构来存储运算对象。

栈是一种遵循后进先出（LIFO）原则的数据结构，可以用来存储序列中的运算对象。

算法方面，主要是通过栈的入栈和出栈操作来实现中缀表达式到后缀表达式的转换。

在遇到运算对象时，将其入栈；在遇到运算符时，弹出栈顶的两个运算对象进行运算，并将新的运算对象入栈。

这样，当栈为空时，就完成了中缀转后缀的转换。

四、实际应用案例和注意事项中缀转后缀表达式在实际编程中有很多应用，例如表达式求值、中缀表达式遍历等。

中缀表达式转后缀表达式并计算结果⽬录1 栈的概念容器，先进后出规则；如图为表达式：a+(b*c) 逐个操作符、操作数⼊栈过程；出栈为该过程逆序2 何谓中缀表达式型如：a - b + c 的普通算术表达式，我们称之为中缀表达式。

3 后缀表达式(逆波兰)3.1 概念以及案例中缀表达式：a - b + c ，转化为后缀表达式：ab-c+；后缀表达式运算规则：1. 遇到操作数直接⼊栈，遇到操作符，从栈顶弹出两个操作数，并计算如下表达式结果压栈，直⾄最终弹出栈中最后⼀个数即停⽌算法，该记法的表达式称为后缀表达式后出栈操作数(两数中更靠近栈底者) （操作符[+_*/]）先出栈操作数(栈顶)2. ab-c+计算过程如下图：3.2 求解⽅法⼊栈优先级{ [ ( > 乘= 除> 加= 减3.2.1 流程图弹出案例：扫描位优先级较⼩，扫描位为 " - "。

左括号虽然优先级⼤，但是左括号只在碰到，匹配的右括号时弹出3.2.2 推导相等优先级为何弹出栈顶只关注相同有优先级下是否弹出栈顶先加，后加减中缀表达式后缀表达式a +b +c abc++ 或 ab+c+a +b -c ab+c- 或 abc-+中缀表达式后缀表达式此例中，当需要判断操作符间优先级：栈顶为：+(加)，栈外判断位：+ 或 - 。

此时若优先级相等，既可弹出栈顶操作符，也可不弹直接当前位压栈。

先减，后加减中缀表达式后缀表达式a -b +c ab-c+a -b -c ab-c-此例中，当需要判断操作符间优先级：栈顶为：-(减)，栈外判断位：+ 或 - 。

此时若优先级相等，则只能弹出当前栈顶操作符。

先乘，后乘除中缀表达式后缀表达式a *b *c abc** 或 ab ca *b /c ab c/ 或 abc/此例中，当需要判断操作符间优先级：栈顶为：(乘)，栈外判断位：或 / 。

此时若优先级相等，既可弹出栈顶操作符，也可不弹直接当前位压栈。

用C语言写解释器（三）——中缀转后缀用C语言写解释器（三）——中缀转后缀分类：用C语言写解释器算法讨论拍拍脑袋 2009-11-01 22:25 4983人阅读评论(4) 收藏举报语言ctokennulllist数据结构声明为提高教学质量，我所在的学院正在筹划编写C语言教材。

《用C语言写解释器》系列文章经整理后将收入书中“综合实验”一章。

因此该系列的文章主要阅读对象定为刚学完C语言的学生（不要求有数据结构等其他知识），所以行文比较罗嗦，请勿见怪。

本人水平有限，如有描述不恰当或错误之处请不吝赐教！特此声明。

操作符排序如果你忘记了后缀表达式的概念，赶紧翻回上一篇《用C语言写解释器（二）》回顾一下。

简单地说，将中缀表达式转换成后缀表达式，就是将操作符的执行顺序由“优先级顺序”转换成“在表达式中的先后顺序”。

因此，所谓的中缀转后缀，其实就是给原表达式中的操作符排序。

比如将中缀表达式 5 * ((10 - 1) / 3) 转换成后缀表达式为 5 10 1 - 3 / *。

其中数字 5 10 1 3 仍然按照原先的顺序排列，而操作符的顺序变为 - / ×，这意味着减号最先计算、其次是除号、最后才是乘号。

也许你还在担心如何将操作符从两个操作数的中间移到它们的后边。

其实不用担心，在完成了排序工作后你就发现它已经跑到操作数的后面了 ^_^。

从中缀表达式1+2×3+4 中逐个获取操作符，依次是+ × +。

如果当前操作符的优先级不大于前面的操作符时，前面操作符就要先输出。

比如例子中的第二个加号，它前面是乘号，因此乘号从这个队伍中跑到输出的队伍中当了“老大”；此时第二个加号再前面的加号比较，仍然没有比它大，因此第一个加号也排到新队伍中去了；最后队伍中只剩下加号自己了，所以它也走了。

得到新队伍里的顺序× + + 就是所求解。

下面的表格中详细展示每一个步骤。

序号输入临时空间输出1 +2 ×+3 + + ×4 + × +5 + + ×6 + × +7 × + +相信你心里还是牵挂着那些操作数。