P4821 中缀转后缀表达式（提高）

解题思路

这道题要我们把中缀表达式（比如 x+a*(y-b)-z/f）转换成后缀表达式（xayb-*+zf/-）。后缀表达式的特点是运算符跟在两个操作数后面，不用括号也能确定运算顺序。

第一步，认识“优先级”和“括号”。 加减的优先级是 1，乘除的优先级是 2，左括号先压栈、等着被右括号配对。转换的核心问题是：一个运算符什么时候该输出？当它前面的运算符优先级不低于它，说明前面的运算要先做，就要先把前面的运算符输出。

第二步，把算法拆成四句话。

1. 遇到英文字母（操作数），直接输出；
2. 遇到左括号，压进栈里；
3. 遇到右括号，把栈里直到左括号为止的运算符全部弹出输出，再把左括号丢掉；
4. 遇到运算符，先把栈顶优先级不低于它的运算符弹出输出，再把自己压进栈。

第三步，为什么要“优先级不低于它”就弹？ 比如 x+a*(y-b) 里，乘号优先级比加号高，遇到乘号时不能把加号弹出，否则加号会跑到乘号前面，顺序就错了。反过来，如果栈顶是乘号、新来的是加号，说明乘号要先算，必须先输出乘号。

第四步，拿样例走一遍。 x+a*(y-b)-z/f：x 直接输出；+ 入栈；a 输出；* 入栈；( 入栈；y 输出；- 入栈；b 输出；) 把 - 弹出输出、丢掉 (；- 把 * 和 + 弹出输出、自己入栈；z 输出；/ 入栈；f 输出；最后把栈里剩下的 / 和 - 弹出输出。得到 xayb-*+zf/-，和题目完全一致。

第五步，别忘了最后清空栈。 扫描结束后栈里可能还压着运算符，要全部弹出输出。这样转换后的后缀表达式就和原中缀式的运算次序一致。

参考代码

// 用途：把中缀表达式转换成后缀表达式，操作数是单个英文字母，运算符含 + - * / 和括号
#include <iostream>
using namespace std;

// 运算符栈，保存 '(' 和 '+','-','*','/'
char st[205];
int top = 0;

// 返回运算符优先级：+ - 是 1，* / 是 2，左括号最低是 0
int pri(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;  // 左括号
}

int main() {
    char s[205];
    cin >> s;
    for (int i = 0; s[i] != '\0'; i++) {
        char ch = s[i];
        // 英文字母是操作数，直接输出
        if ((ch >= 'a' && ch <= 'z') ||
            (ch >= 'A' && ch <= 'Z')) {
            cout << ch;
        } else if (ch == '(') {
            // 左括号直接压栈
            st[top++] = ch;
        } else if (ch == ')') {
            // 遇到右括号，把栈里直到左括号的运算符全部弹出输出
            while (top > 0 && st[top - 1] != '(') {
                cout << st[--top];
            }
            top--;  // 把左括号弹出丢弃
        } else {
            // 遇到运算符：栈里优先级不低于它的运算符先弹出输出，再压入自己
            while (top > 0 && st[top - 1] != '(' &&
                   pri(st[top - 1]) >= pri(ch)) {
                cout << st[--top];
            }
            st[top++] = ch;
        }
    }
    // 最后把栈里剩下的运算符全部弹出输出
    while (top > 0) {
        cout << st[--top];
    }
    cout << endl;
    return 0;
}

复杂度分析

中缀表达式长度不超过 200。每个字符最多进栈一次、出栈一次，每次操作都是 $O(1)$，所以总时间是 $O(L)$，其中 $L$ 是表达式长度。空间上，栈里最多存放括号和运算符，同样只有 $O(L)$。$L\le200$，效率非常高。