C++栈式计算器实现（从零开始掌握表达式求值与栈数据结构）

实现步骤概览

1. 将中缀表达式转换为后缀表达式（使用调度场算法）
2. 使用栈对后缀表达式进行求值

第一步：中缀转后缀

我们需要一个函数，输入如 "3 + 5 * (2 - 1)" 的字符串，输出后缀形式 "3 5 2 1 - * +"。

规则简述：

• 数字直接加入输出队列
• 遇到操作符，根据优先级决定是否弹出栈中操作符到输出
• 左括号入栈，右括号则不断弹出直到遇到左括号

第二步：后缀表达式求值

遍历后缀表达式：

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

完整C++代码实现

#include <iostream>#include <stack>#include <queue>#include <cctype>#include <string>#include <sstream>#include <vector>using namespace std;// 判断字符是否为操作符bool isOperator(char c) {    return c == '+' || c == '-' || c == '*' || c == '/';}// 获取操作符优先级int getPrecedence(char op) {    if (op == '+' || op == '-') return 1;    if (op == '*' || op == '/') return 2;    return 0;}// 中缀表达式转后缀（返回 token 列表）vector<string> infixToPostfix(const string& expr) {    stack<char> ops;    vector<string> output;    string number = "";    for (char c : expr) {        if (isspace(c)) continue;        if (isdigit(c)) {            number += c;        } else {            if (!number.empty()) {                output.push_back(number);                number = "";            }            if (c == '(') {                ops.push(c);            } else if (c == ')') {                while (!ops.empty() && ops.top() != '(') {                    output.push_back(string(1, ops.top()));                    ops.pop();                }                if (!ops.empty()) ops.pop(); // 弹出 '('            } else if (isOperator(c)) {                while (!ops.empty() && ops.top() != '(' &&                       getPrecedence(ops.top()) >= getPrecedence(c)) {                    output.push_back(string(1, ops.top()));                    ops.pop();                }                ops.push(c);            }        }    }    if (!number.empty()) {        output.push_back(number);    }    while (!ops.empty()) {        output.push_back(string(1, ops.top()));        ops.pop();    }    return output;}// 计算后缀表达式double evaluatePostfix(const vector<string>& postfix) {    stack<double> nums;    for (const string& token : postfix) {        if (isdigit(token[0]) || (token.size() > 1 && isdigit(token[1]))) {            nums.push(stod(token));        } else {            double b = nums.top(); nums.pop();            double a = nums.top(); nums.pop();            char op = token[0];            switch (op) {                case '+': nums.push(a + b); break;                case '-': nums.push(a - b); break;                case '*': nums.push(a * b); break;                case '/':                     if (b == 0) {                        cerr << "Error: Division by zero!" << endl;                        return 0;                    }                    nums.push(a / b);                     break;            }        }    }    return nums.top();}int main() {    string expression = "3 + 5 * (2 - 1)";    cout << "原始表达式: " << expression << endl;    vector<string> postfix = infixToPostfix(expression);    cout << "后缀表达式: ";    for (const auto& t : postfix) {        cout << t << " ";    }    cout << endl;    double result = evaluatePostfix(postfix);    cout << "计算结果: " << result << endl;    return 0;}

运行效果

程序输出如下：

原始表达式: 3 + 5 * (2 - 1)后缀表达式: 3 5 2 1 - * + 计算结果: 8

总结

通过本教程，你已经掌握了如何用 C++ 实现一个完整的栈式计算器。这个项目融合了栈数据结构、字符串处理、运算符优先级等核心概念，是理解C++表达式求值机制的绝佳练习。进一步地，你可以尝试支持小数、负数、更多运算符（如 ^ 幂运算）或错误处理，打造更强大的后缀表达式计算引擎。

希望这篇教程对你有帮助！动手敲一遍代码，你会收获更多。