极客教程

Appearance

共 1,415 字预计阅读约 5 分钟

更新时间： 2026-08-27

前两个练习都在"管数据"，这个换换口味——算表达式。写一个计算器：输入 3 + 4 * 2，输出 11。核心问题很经典：怎么让计算机理解"先乘除后加减"？答案是 40 篇埋下的 std::stack——表达式求值是栈最经典的应用之一。

本文要回答：中缀表达式怎么变成后缀表达式？两个栈各干什么？stack 在这里为什么不可替代？

一、需求与设计 ​

需求：

  • 支持 + - * / 和括号 ( )
  • 正确处理优先级（先乘除后加减、括号优先）
  • 处理空格
  • 除零报错

核心思想：转后缀（逆波兰）表达式。人类习惯中缀 3 + 4 * 2（运算符在中间）；计算机求值更爱后缀 3 4 2 * +（运算符在后）——因为后缀求值只需要一个栈，从左到右扫一遍，根本不用管优先级。

@startmindmap
* 简易计算器
** 输入：中缀表达式字符串
** 转换：中缀 → 后缀（用操作符栈）
** 求值：后缀求值（用操作数栈）
** 输出：结果 / 错误信息
@endmindmap

二、算法设计 ​

2.1 中缀 → 后缀（调度场算法） ​

规则（经典）：

  • 数字直接输出到后缀序列
  • 遇到操作符：弹出栈顶所有"优先级不低于它"的操作符到输出，再把它入栈
  • 遇到 (：直接入栈
  • 遇到 )：弹出栈中直到 ( 为止的所有操作符
  • 结束：栈里剩余的依次弹出

2.2 后缀求值 ​

  • 数字压栈
  • 遇到操作符：弹出两个数，计算，结果压回
  • 结束：栈顶就是答案
@startuml
left to right direction
skinparam nodeFontSize 13
skinparam backgroundColor #FFFFFF

rectangle "3 + 4 * 2" as infix #E8F1FF
rectangle "3 4 2 * +" as postfix #DCE9FF
rectangle "求值栈" as stack #D9FFE2 {
  node "压 3" as s1 #FFF3D6
  node "压 4" as s2 #FFF3D6
  node "压 2" as s3 #FFF3D6
  node "2 * 4 → 8" as s4 #D9FFE2
  node "8 + 3 → 11" as s5 #D9FFE2
}
infix --> postfix : "操作符栈转换"
postfix --> stack : "操作数栈求值"
@enduml

三、代码设计 ​

cpp
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <sstream>
#include <cctype>
#include <stdexcept>

// 操作符优先级
int precedence(char op) {
    switch (op) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        default: return 0;
    }
}

// 中缀 → 后缀（token 化，按空格分隔）
std::vector<std::string> to_postfix(const std::string& expr) {
    std::vector<std::string> output;
    std::stack<char> ops;
    std::istringstream iss(expr);
    std::string token;

    while (iss >> token) {   // 按空白切 token
        char c = token[0];
        if (std::isdigit(static_cast<unsigned char>(c))) {
            output.push_back(token);            // 数字直接输出
        } else if (c == '(') {
            ops.push(c);
        } else if (c == ')') {
            while (!ops.empty() && ops.top() != '(') {
                output.push_back(std::string(1, ops.top()));
                ops.pop();
            }
            if (ops.empty()) throw std::runtime_error("括号不匹配");
            ops.pop();                          // 弹出 '('
        } else {                                // 操作符
            while (!ops.empty() && precedence(ops.top()) >= precedence(c)) {
                output.push_back(std::string(1, ops.top()));
                ops.pop();
            }
            ops.push(c);
        }
    }
    while (!ops.empty()) {
        if (ops.top() == '(') throw std::runtime_error("括号不匹配");
        output.push_back(std::string(1, ops.top()));
        ops.pop();
    }
    return output;
}

// 后缀求值
double eval_postfix(const std::vector<std::string>& postfix) {
    std::stack<double> nums;
    for (const auto& tok : postfix) {
        if (std::isdigit(static_cast<unsigned char>(tok[0]))) {
            nums.push(std::stod(tok));
        } else {
            if (nums.size() < 2) throw std::runtime_error("表达式不合法");
            double b = nums.top(); nums.pop();
            double a = nums.top(); nums.pop();
            switch (tok[0]) {
                case '+': nums.push(a + b); break;
                case '-': nums.push(a - b); break;
                case '*': nums.push(a * b); break;
                case '/':
                    if (b == 0) throw std::runtime_error("除零错误");
                    nums.push(a / b); break;
            }
        }
    }
    if (nums.size() != 1) throw std::runtime_error("表达式不合法");
    return nums.top();
}

int main() {
    std::cout << "输入中缀表达式（空格分隔，如: 3 + 4 * 2）: ";
    std::string expr;
    std::getline(std::cin, expr);

    try {
        auto postfix = to_postfix(expr);
        double result = eval_postfix(postfix);
        std::cout << "结果: " << result << "\n";
    } catch (const std::exception& e) {
        std::cerr << "错误: " << e.what() << "\n";
        return 1;
    }
}

知识点盘点：

知识点用到的地方
std::stack（40）操作符栈 + 操作数栈
std::istringstream（07）按空格切 token
字符串处理（33）std::string(1, c) 单字符转字符串
异常（54-57）括号不匹配、除零、非法表达式
优先级表核心逻辑

四、实验预期 ​

  • 3 + 4 * 2 → 11（先乘后加）
  • ( 3 + 4 ) * 2 → 14（括号优先）
  • 10 / 4 → 2.5（浮点除法）
  • 1 / 0 → 报错"除零错误"
  • ( 3 + 4 → 报错"括号不匹配"

五、实验数据 ​

实际编译运行输出（g++ 13，-std=c++17）：

$ g++ -O0 -g -std=c++17 -o calc main.cpp
$ ./calc
输入中缀表达式（空格分隔，如: 3 + 4 * 2）: 3 + 4 * 2
结果: 11

$ ./calc
输入中缀表达式（空格分隔，如: 3 + 4 * 2）: ( 3 + 4 ) * 2
结果: 14

$ ./calc
输入中缀表达式（空格分隔，如: 3 + 4 * 2）: 10 / 4
结果: 2.5

$ ./calc
输入中缀表达式（空格分隔，如: 3 + 4 * 2）: 1 / 0
错误: 除零错误

$ ./calc
输入中缀表达式（空格分隔，如: 3 + 4 * 2）: ( 3 + 4
错误: 括号不匹配

各表达式行为验证：

输入结果说明
3 + 4 * 211优先级正确
( 3 + 4 ) * 214括号优先
10 / 42.5浮点运算
1 / 0错误除零检测
( 3 + 4错误括号不匹配

六、实验分析 ​

1. 为什么后缀表达式这么好用？

中缀有优先级问题，后缀没有——后缀表达式本身就是"已经排好执行顺序"的。求值只需一个栈：数字压、操作符弹两个算一个压回。这个"栈 + 线性扫描"的模式，是栈最本质的用途：处理"最近的事先处理"（LIFO）的场景。括号匹配、函数调用栈、撤销操作、浏览器后退……全是同一个模型。

2. 两个栈的分工

  • 转换阶段的操作符栈：暂时寄存"还没轮到执行的操作符"（优先级不够高就先压着）
  • 求值阶段的操作数栈：寄存"还没被消费的操作数"

这就是 40 篇说的 stack "后进先出"语义的实际价值——操作符压进去的时候，你期望它"后来者先出"（优先级高的后到先算）。

3. 异常的用法示范

这个程序是异常处理的好例子：除零、括号不匹配、表达式非法——这些错误出现在函数深处，main 统一 try/catch 处理。如果用返回码，每个函数都要设计"错误码约定"，转换函数和求值函数都要传错误标志出来，代码会难看得多。这正是 54 篇说的"错误是例外、集中处理"的场景。

4. 局限

这个版本 token 必须用空格分开、不支持小数（std::stod 其实支持但 token 切分按空格）、不支持一元负号（-3 会被当成 token - 和 3）。真要完善要加"负号识别"，属于进阶。练习的价值在理解算法，不在抠边界。

七、C 对照 ​

模块C 版本C++ 版本
栈手写数组栈std::stack
字符串切分strtok（改原串！）istringstream >>
字符串转数字strtodstd::stod（异常）
错误处理返回码异常 + 集中 catch

C 版最麻烦的是 strtok 会修改原字符串、栈要自己管理容量、字符串转数字的错误检查要查 errno——每一处都是坑。C++ 的 stack、istringstream、stod 把杂活全包了，代码聚焦在算法本身。

八、与本站主线衔接 ​

  • cpp
    // 综合练习 3：简易计算器（栈实现）
// 对应文档: languages/cpp/beginner/60-practice-calculator.md
// 编译: g++ -O0 -g -std=c++17 calculator.cpp -o calculator
// 运行: ./calculator  然后输入如 "3 + 4 * 2"（空格分隔）
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <sstream>
#include <cctype>
#include <stdexcept>

int precedence(char op) {
    switch (op) {
        case '+': case '-': return 1;
        case '*': case '/': return 2;
        default: return 0;
    }
}

std::vector<std::string> to_postfix(const std::string& expr) {
    std::vector<std::string> output;
    std::stack<char> ops;
    std::istringstream iss(expr);
    std::string token;

    while (iss >> token) {
        char c = token[0];
        if (std::isdigit(static_cast<unsigned char>(c))) {
            output.push_back(token);
        } else if (c == '(') {
            ops.push(c);
        } else if (c == ')') {
            while (!ops.empty() && ops.top() != '(') {
                output.push_back(std::string(1, ops.top()));
                ops.pop();
            }
            if (ops.empty()) throw std::runtime_error("括号不匹配");
            ops.pop();
        } else {
            while (!ops.empty() && precedence(ops.top()) >= precedence(c)) {
                output.push_back(std::string(1, ops.top()));
                ops.pop();
            }
            ops.push(c);
        }
    }
    while (!ops.empty()) {
        if (ops.top() == '(') throw std::runtime_error("括号不匹配");
        output.push_back(std::string(1, ops.top()));
        ops.pop();
    }
    return output;
}

double eval_postfix(const std::vector<std::string>& postfix) {
    std::stack<double> nums;
    for (const auto& tok : postfix) {
        if (std::isdigit(static_cast<unsigned char>(tok[0]))) {
            nums.push(std::stod(tok));
        } else {
            if (nums.size() < 2) throw std::runtime_error("表达式不合法");
            double b = nums.top(); nums.pop();
            double a = nums.top(); nums.pop();
            switch (tok[0]) {
                case '+': nums.push(a + b); break;
                case '-': nums.push(a - b); break;
                case '*': nums.push(a * b); break;
                case '/':
                    if (b == 0) throw std::runtime_error("除零错误");
                    nums.push(a / b); break;
            }
        }
    }
    if (nums.size() != 1) throw std::runtime_error("表达式不合法");
    return nums.top();
}

int main() {
    std::cout << "输入中缀表达式（空格分隔，如: 3 + 4 * 2）: ";
    std::string expr;
    std::getline(std::cin, expr);

    try {
        auto postfix = to_postfix(expr);
        double result = eval_postfix(postfix);
        std::cout << "结果: " << result << "\n";
    } catch (const std::exception& e) {
        std::cerr << "错误: " << e.what() << "\n";
        return 1;
    }
}
  • 栈在系统层面无处不在：函数调用栈（21 篇）、表达式求值（本练习）、括号匹配
  • 后缀表达式和编译器的中间表示有渊源（本站 fe/ 前端编译方向），可以兴趣延伸
  • 下一篇综合练习是文本单词统计，用上 map 的词频统计

九、一句话总结 ​

简易计算器是 std::stack 的经典应用：操作符栈把中缀转后缀（调度场算法），操作数栈一次扫描求出结果——"后来者先出"的 LIFO 语义恰好匹配优先级处理；配合 istringstream 切 token、异常做错误处理，30 行核心代码完成一个带括号和优先级的计算器。

上一篇：59-综合练习：学生成绩系统 ｜ 下一篇：61-综合练习：文本单词统计