P4817 后缀表达式（提高）

解题思路

1. 什么是后缀表达式。 中缀是我们平时写的 (a+b)f（运算符在中间），后缀把运算符写到两个操作数之后：ab+f。转换的原则是"运算次序和原式完全一致"，所以要处理运算符优先级和括号。
2. 准备一个运算符栈。 扫描中缀表达式，遇到不同的字符做不同的事：
   • 遇到英文字母（大写小写都要算）说明是操作数，直接输出；
   • 遇到左括号 ( 就压入栈，表示进入一小块"优先"的区域；
   • 遇到右括号 ) 就把栈里的运算符一直弹出输出，直到弹出左括号为止（左括号本身不输出）；
   • 遇到运算符 + - * /，只要栈顶运算符优先级不低于当前运算符（乘除的优先级高于加减），就先弹出输出，然后把当前运算符压入栈。
3. 为什么这样能保证顺序？ 乘除像"关系更紧密"的运算，要更早结合，所以它们在后缀里出现得晚，需要先压栈、后弹出；栈顶优先级不低于当前运算符时先弹出，是为了让已经可以确定的运算先输出。
4. 扫尾。 整个表达式扫描完后，把栈里剩余的运算符依次全部弹出输出，就得到了完整的后缀表达式。
5. 边界提醒。 操作数可能是大写字母（比如 Z、M、L），不能只判断小写。左括号只负责"框住"范围，不会出现在输出里。

参考代码

// 后缀表达式：中缀表达式转后缀表达式，用运算符栈保证先乘除后加减，括号优先级最高
// 注意：操作数是英文字母，既包括小写 a-z 也包括大写 A-Z，都要直接输出
#include <iostream>
using namespace std;

int main() {
    char expr[205];     // 输入的中缀表达式
    char stack[205];    // 运算符栈
    int top = 0;
    char result[205];   // 输出的后缀表达式
    int len = 0;
    cin >> expr;
    for (int i = 0; expr[i] != '\0'; i++) {
        char ch = expr[i];
        if ((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z')) {   // 操作数是英文字母，直接输出
            result[len++] = ch;
        } else if (ch == '(') {
            stack[top++] = ch;
        } else if (ch == ')') {
            // 把左括号上面的运算符全部弹出输出
            while (top > 0 && stack[top - 1] != '(') {
                result[len++] = stack[--top];
            }
            top--;   // 弹出左括号本身，不输出
        } else {
            // 普通运算符：栈顶运算符优先级不低于当前运算符时，先弹出
            int pri = (ch == '*' || ch == '/') ? 2 : 1;
            while (top > 0 && stack[top - 1] != '(') {
                char topOp = stack[top - 1];
                int topPri = (topOp == '*' || topOp == '/') ? 2 : 1;
                if (topPri >= pri) {
                    result[len++] = stack[--top];
                } else {
                    break;
                }
            }
            stack[top++] = ch;
        }
    }
    while (top > 0) {   // 把栈里剩下的运算符全部输出
        result[len++] = stack[--top];
    }
    result[len] = '\0';
    cout << result << endl;
    return 0;
}

复杂度分析

每个字符最多进栈一次、出栈一次，所以时间复杂度是 O(len)，len 是中缀表达式的长度（不超过 200）。空间上用一个长度 205 的数组当栈，也是 O(len)。整个算法非常高效。