C++：前缀、中缀、后缀表达式互相转换详解

您所在的位置：网站首页 › 浮世绘代表作 › C++：前缀、中缀、后缀表达式互相转换详解

C++：前缀、中缀、后缀表达式互相转换详解

#C++：前缀、中缀、后缀表达式互相转换详解| 来源: 网络整理| 查看: 265

文章目录中缀表达式转为前缀表达式（波兰式）前缀表达式逆向求解中缀表达式中缀表达式转为后缀表达式（逆波兰式）后缀表达式逆向求解中缀表达式图解示例：代码实现：一个中缀式到其他式子的转换方法(超级简易)~~相关习题：

表达式定义示例前缀表达式运算符位于操作数之前- × + 3 4 5 6中缀表达式操作符以中缀形式处于操作数的中间(3 + 4) × 5 - 6后缀表达式运算符位于操作数之后3 4 + 5 × 6 -

前缀式，后缀式是不需要用括号来进行优先级的确定的。

中缀表达式转为前缀表达式（波兰式）

遵循以下步骤：

初始化两个栈：运算符栈S1和储存中间结果的栈S2；从右至左扫描中缀表达式；遇到操作数时，将其压入S2；遇到运算符时，比较其与S1栈顶运算符的优先级： 4.1 如果S1为空，或栈顶运算符为右括号“)”，则直接将此运算符入栈； 4.2 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1； 4.3 否则，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较遇到括号时： 5.1 如果是右括号“)”，则直接压入S1； 5.2 如果是左括号“(”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到右括号为止，此时将这一对括号丢弃重复步骤(2)至(5)，直到表达式的最左边；将S1中剩余的运算符依次弹出并压入S2；依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。前缀表达式逆向求解中缀表达式

-+1*+2345

思路：递归，碰到操作符就进入递归。

从右往左扫描先碰到+号，取+号后面两个操作数：2，3 得到：2+3.继续往左扫碰到*号，取2+3和 4 得到：（2+3）*4继续往左扫碰到+号，取1和（2+3）*4得到：1+（2+3）*4继续往左扫碰到-号，取1+（2+3）*4和5得到：1+（2+3）*4-5 中缀表达式转为后缀表达式（逆波兰式）

与转换为前缀表达式相似，遵循以下步骤：

初始化两个栈：运算符栈S1和储存中间结果的栈S2；从左至右扫描中缀表达式；遇到操作数时，将其压入S2；遇到运算符时，比较其与S1栈顶运算符的优先级： 4.1 如果S1为空，或栈顶运算符为左括号“(”，则直接将此运算符入栈； 4.2 比栈顶高，也将运算符压入S1 （注意转换为前缀表达式时是优先级较高或相同，而这里则不包括相同的情况）； 4.3 比栈顶低或相同，将S1栈顶的运算符弹出并压入到S2中，再次转到(4-1)与S1中新的栈顶运算符相比较；遇到括号时: 5.1 如果是左括号“(”，则直接压入S1； 5.2 如果是右括号“)”，则依次弹出S1栈顶的运算符，并压入S2，直到遇到左括号为止，此时将这一对括号丢弃；可以想象成“（”比任何运算符都高，“）”比任何运算符都低。重复步骤(2)至(5)，直到表达式的最右边；将S1中剩余的运算符依次弹出并压入S2；依次弹出S2中的元素并输出，结果的逆序即为中缀表达式对应的后缀表达式（转换为前缀表达式时不用逆序）。后缀表达式逆向求解中缀表达式

1 2 3 + 4* 5 - +

基本思路和上面的一样：递归，碰到操作符就进入递归

从左往右扫描先碰到+号，取+号前面两个操作数：2，3 得到：2+3.继续往右扫碰到*号，取2+3 和 4 得到：（2+3）*4继续往右扫碰到-号，取（2+3）*4和5得到：（2+3）*4-5继续往右扫碰到+号：取（2+3）*4-5和1得到：1+（2+3）*4-5 图解示例：

在这里插入图片描述

代码实现： // 判断是否为括号 bool isPra(char c) { return (c == '(' || c == ')') ? true : false; } // 获得符号的优先性 int getPri(char c) { switch (c) { case '+': case '-': return 0; // 如果是加减，返回0 break; case '*': case '/': return 1; // 如果是乘除，返回1 break; case '(': case ')': return -1; // 这里将括号设为最低优先级，因此括号不会被弹出，除非遇到右括号 break; default: cout operator_s.push(c); return; } if (isPra(c)) { if (c == '(') { operator_s.push(c); } else { // 弹出所有元素直到遇到左括号 while (operator_s.top() != '(') { suffix += operator_s.top(); operator_s.pop(); } // 遇到左括号，弹出且不加入后缀表达式 operator_s.pop(); } } else { // 如果不是括号，比较当前元素，与栈顶元素的优先级 if (getPri(c) > getPri(operator_s.top())) { operator_s.push(c); } else { suffix += operator_s.top(); operator_s.pop(); // 递归调用，比较当前符号c与下一个栈顶符号的优先性 check(c, operator_s, suffix); } } } // 中缀表达式转后缀表达式 string infixToSuffix(string& infix) { stack operator_s; // 运算符栈 string suffix; // 后缀表达式 //int num = 0; for (int i = 0; i suffix += infix[i]; } else { check(infix[i], operator_s, suffix); } } // 对中缀表达式的遍历结束，将栈中元素加入后缀表达式 while (!operator_s.empty()) { suffix += operator_s.top(); operator_s.pop(); } return suffix; } 一个中缀式到其他式子的转换方法(超级简易)~~

这里给出中缀表达式：a+b*c-(d+e)

按照运算符的优先级对所有的运算单位加括号~

式子变成：((a+(b* c))-(d+e))

转换成前缀表达式与后缀表达式

前缀：把运算符号移动到对应的括号前面则变成：-( +(a* (bc))+(de)) 把括号去掉：-+a* bc+de 前缀式子出现后缀：把运算符号移动到对应的括号后面则变成：((a(bc)* )+(de)+)- 把括号去掉：abc* +de+ - 后缀式子出现相关习题：假定有中缀表达式A：1 + (( 2 + 3)* 4 ) – 5，请将它转化为前缀，后缀表达式。中缀转前缀：（直接转换法）

首先确定表达式表达式A的运算顺序，然后加括号：（（1 + (( 2 + 3)* 4 )） – 5 ）从最里面的一层括号开始运算，转换成前缀表达式的方法为：（忽略括号）符号在前，数字在后。

演示过程如下：

( 2 + 3) => +23(( 2 + 3)* 4 ) => *+234(1 + (( 2 + 3) * 4 ))=> +1*+234((1 + (( 2 + 3)* 4 )) – 5 )=> -+1*+2345

前缀表达式为：-+1*+2345

中缀转后缀：（直接转换法）

首先确定表达式表达式A的运算顺序，然后加括号：（（1 + (( 2 + 3)* 4 )） – 5 ）从最里面的一层括号开始运算，转换成后缀表达式的方法为：（忽略括号）数字在前，符号在后。

演示过程如下：

( 2 + 3) => 23+(( 2 + 3)* 4 ) => 23+4*（1 + (( 2 + 3)* 4 )）=> 123+4*+ [按照运算次序，从左到右排列]（（1 + (( 2 + 3)* 4 )） – 5 ）=> 123+4*+ 5-

后缀表达式为：123 + 4*+ 5 –

【本文地址】

C++：前缀、中缀、后缀表达式互相转换详解

C++：前缀、中缀、后缀表达式互相转换详解

今日新闻

推荐新闻