---

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

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

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

遵循以下步骤：

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

中缀表达式 转为 后缀表达式（逆波兰式）

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

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

//判断符号的优先性
void check(char c, stack<char>& operator_s, string& suffix) {
    if (operator_s.empty()) {
        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<char> operator_s; // 运算符栈
    string suffix;          // 后缀表达式

    //int num = 0;
    for (int i = 0; i < infix.size(); ++i) {
        if (infix[i] >= '0' && infix[i] <= '9') {
            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)

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

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

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

   • 前缀：把运算符号移动到对应的括号前面
     则变成：-( +(a* (bc))+(de))
     把括号去掉：-+a* bc+de 前缀式子出现
   • 后缀：把运算符号移动到对应的括号后面
     则变成：((a(bc)* )+(de)+)-
     把括号去掉：abc* +de+ - 后缀式子出现

---

相关习题：

1. 假定有中缀表达式A：1 + (( 2 + 3)* 4 ) – 5，请将它转化为前缀，后缀表达式。

• 中缀转前缀：（直接转换法）

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

演示过程如下：

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

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

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

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

演示过程如下：

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

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