表达式求值：栈的经典实战

表达式求值，说白了就是让计算机像人一样算算术。你想想看，我们写 3 + 5 * 2 一眼就知道先算乘法，但计算机从左往右扫过去就懵了——凭什么先算后面的？

这个问题，我当年刚学数据结构时也困惑过。后来在做一个简易计算器项目时，被中缀转后缀折腾了一整天，才真正理解了栈的妙用。今天咱们就把这个经典问题彻底讲透。

核心思路：中缀 vs 后缀

我们平时写的 3 + 5 * 2 叫中缀表达式——运算符在中间。计算机更喜欢后缀表达式（也叫逆波兰式），比如 3 5 2 * +，运算符在后面。

为什么后缀好算？因为没有括号，没有优先级，从左到右扫一遍就出结果。我早期做表达式解析时，试过直接算中缀，结果代码写得跟意大利面一样。后来老老实实走「中缀→后缀→求值」这条路，清爽多了。

整体流程

三步走：

  1. 中缀表达式 → 后缀表达式（用栈处理运算符和括号）
  2. 后缀表达式 → 计算结果（用栈处理操作数）
  3. 输出结果

下面这张图把核心逻辑串起来了，建议你先看一遍，再往下读代码。

表达式求值核心流程 中缀表达式 扫描 中缀转后缀（运算符栈） 后缀表达式 后缀求值（操作数栈）→ 结果

第一步：中缀转后缀

规则其实不复杂，但细节容易翻车。我直接给你总结成四条：

遇到什么 怎么做
操作数（数字） 直接输出到后缀表达式
左括号 ( 压入运算符栈
右括号 ) 弹出栈顶运算符直到遇到左括号（左括号不输出）
运算符（+ - * /） 弹出栈中所有优先级 大于等于 当前运算符的，再压入当前运算符

💡 我的经验：优先级比较时，很多人忘了「等于」的情况。比如 3 - 2 + 1，如果遇到 + 时不弹出 -，结果就错了。因为加减是左结合，从左往右算。

来看代码实现：

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
#include <cctype>

int precedence(char op) {
    if (op == '+' || op == '-') return 1;
    if (op == '*' || op == '/') return 2;
    return 0;
}

std::string infixToPostfix(const std::string& expr) {
    std::stack<char> ops;
    std::string postfix;
    
    for (size_t i = 0; i < expr.length(); ++i) {
        char ch = expr[i];
        
        if (isspace(ch)) continue;
        
        if (isdigit(ch)) {
            // 处理多位数
            while (i < expr.length() && isdigit(expr[i])) {
                postfix += expr[i];
                ++i;
            }
            postfix += ' ';
            --i;
        }
        else if (ch == '(') {
            ops.push(ch);
        }
        else if (ch == ')') {
            while (!ops.empty() && ops.top() != '(') {
                postfix += ops.top();
                postfix += ' ';
                ops.pop();
            }
            if (!ops.empty()) ops.pop(); // 弹出 '('
        }
        else { // 运算符
            while (!ops.empty() && precedence(ops.top()) >= precedence(ch)) {
                postfix += ops.top();
                postfix += ' ';
                ops.pop();
            }
            ops.push(ch);
        }
    }
    
    while (!ops.empty()) {
        postfix += ops.top();
        postfix += ' ';
        ops.pop();
    }
    
    return postfix;
}

⚠️ 注意：处理多位数时，我习惯在数字后面加空格分隔。否则 12 3 + 和 1 23 + 就分不清了。曾经有个同事没加分隔符，调试了一下午才发现是解析问题。

第二步：后缀表达式求值

这一步就简单多了。扫一遍后缀表达式：

  • 遇到数字 → 压入操作数栈
  • 遇到运算符 → 弹出两个操作数，计算，结果压回栈

这里有个坑：弹出时先弹出的是右操作数，后弹出的是左操作数。减法和除法顺序错了结果就反了。

int evaluatePostfix(const std::string& postfix) {
    std::stack<int> st;
    std::stringstream ss(postfix);
    std::string token;
    
    while (ss >> token) {
        if (isdigit(token[0])) {
            st.push(std::stoi(token));
        } else {
            int right = st.top(); st.pop();
            int left = st.top(); st.pop();
            
            switch (token[0]) {
                case '+': st.push(left + right); break;
                case '-': st.push(left - right); break;
                case '*': st.push(left * right); break;
                case '/': st.push(left / right); break;
            }
        }
    }
    
    return st.top();
}

第三步：整合测试

把两步串起来：

int main() {
    std::string expr = "3 + 5 * 2 - 8 / 4";
    std::cout << "中缀: " << expr << std::endl;
    
    std::string postfix = infixToPostfix(expr);
    std::cout << "后缀: " << postfix << std::endl;
    
    int result = evaluatePostfix(postfix);
    std::cout << "结果: " << result << std::endl;
    
    return 0;
}

输出：

中缀: 3 + 5 * 2 - 8 / 4
后缀: 3 5 2 * + 8 4 / - 
结果: 11

手动验算一下：5 * 2 = 10，3 + 10 = 13，8 / 4 = 2，13 - 2 = 11。没问题。

避坑指南

我这些年做表达式求值踩过的坑，列出来给你参考：

  • 括号不匹配：右括号弹出时，如果栈空了或者没遇到左括号，说明表达式有问题。我习惯在解析时就做合法性检查。
  • 除零错误：整数除法遇到 / 0 会崩溃。实际项目中一定要加判断。
  • 负数处理：比如 -3 + 5，这里的 - 是一元运算符。我通常把它当作 0 - 3 来处理，或者单独标记一元负号。
  • 浮点数支持：上面代码只处理了整数。如果要支持小数，解析数字时得处理小数点。

📌 核心要点回顾：

  • 栈是解决表达式求值的利器——一个管运算符，一个管操作数
  • 中缀转后缀时，优先级比较要包含「等于」的情况
  • 后缀求值时注意操作数弹出顺序
  • 实际开发中别忘了做合法性校验和异常处理

表达式求值这个案例，虽然看起来基础，但栈、优先级、状态转换这些思想，在很多地方都能复用。我后来做 SQL 解析、模板引擎，都或多或少用到了这里的思路。把基础打扎实了，遇到复杂问题才不会慌。

← 上一章 📖 返回目录 下一章 →