考研笔记

板子：中缀转后缀与后缀求值

★ 级：会手算最重要，代码认得就行。中缀转后缀用的是运算符栈，后缀求值用的是操作数栈。

手算规则（中缀 → 后缀）

从左往右扫描中缀表达式：

遇到做法
操作数直接输出
(直接入栈
)依次弹出栈顶并输出，直到弹出 ( 为止（括号本身不输出）
运算符先把栈顶优先级 它的运算符依次弹出输出（碰到 ( 就停），再把它入栈
扫描结束栈里剩下的运算符全部弹出输出

例：a+b*(c-d)-e/f → abcd-*+ef/-。

另一种手算法（加括号法）：先按运算顺序给每一步加上括号，再把每个运算符移到自己那对括号的右括号后面，最后去掉所有括号。适合只要结果、不问栈状态的选择题。

代码

int prio(char op) {                          // 优先级：* / 为 2，+ - 为 1，'(' 为 0
    if (op == '*' || op == '/') return 2;
    if (op == '+' || op == '-') return 1;
    return 0;                                // '(' 最低：别的运算符来了都不会把它弹出
}
 
void toPostfix(char in[], char out[]) {      // 中缀转后缀；操作数都是单个字符
    char st[MaxSize];                        // 运算符栈
    int top = -1, k = 0;                     // k：out 的下一个写入位置
    for (int i = 0; in[i] != '\0'; i++) {
        char c = in[i];
        if (c == '(') st[++top] = c;                         // 左括号：直接入栈
        else if (c == ')') {                                 // 右括号：一直弹到左括号
            while (st[top] != '(') out[k++] = st[top--];
            top--;                                           // 左括号出栈，但不输出
        } else if (c == '+' || c == '-' || c == '*' || c == '/') {
            while (top != -1 && prio(st[top]) >= prio(c))    // 用 >=：同级的也要先弹，保证从左往右算
                out[k++] = st[top--];
            st[++top] = c;                                   // 比它高的弹完了，自己再入栈
        } else out[k++] = c;                                 // 操作数：直接输出
    }
    while (top != -1) out[k++] = st[top--];                  // 扫完后，栈里剩下的全部输出
    out[k] = '\0';
}
 
int evalPostfix(char s[]) {                  // 后缀表达式求值；操作数都是一位数字
    int st[MaxSize], top = -1;               // 操作数栈
    for (int i = 0; s[i] != '\0'; i++) {
        char c = s[i];
        if (c >= '0' && c <= '9') {          // 数字：入栈
            st[++top] = c - '0';
            continue;
        }
        int b = st[top--];                   // 运算符：先弹出的是右操作数
        int a = st[top--];                   // 后弹出的是左操作数
        if (c == '+') st[++top] = a + b;
        else if (c == '-') st[++top] = a - b;
        else if (c == '*') st[++top] = a * b;
        else st[++top] = a / b;
    }
    return st[top];                          // 最后栈里只剩一个数，就是结果
}

复杂度：两个函数都是时间 ，空间 。

关键边界

位置为什么
prio(st[top]) >= prio(c) 用 >=同级运算要从左往右算。写成 > 的话，a-b-c 会转成 abc--，意思就变成了
'(' 的优先级是 0左括号在栈里时，任何运算符都不会把它弹出，只有右括号能弹出它
先弹出的是右操作数a-b 的后缀是 ab-：b 后入栈、先出栈。写反了减法和除法会算错

易错点

  • 两个栈别弄混：中缀转后缀，栈里放运算符；后缀求值，栈里放操作数。
  • 选择题常问「转换过程中栈里最多同时有几个运算符」，按手算规则一步步模拟，每一步都记下栈的内容。
  • 前缀表达式（波兰式）求值是从右往左扫描，先弹出的是左操作数，和后缀正好相反。

链接

反向链接