企业官网建设流程全解析

用C++手搓一个表达式计算器：从字符串解析到二叉树求值（附完整代码）

在编程的世界里，表达式计算器是一个既经典又实用的项目。它不仅能帮助我们理解编译原理的基础知识，还能锻炼数据结构与算法的应用能力。本文将带你用C++实现一个完整的表达式计算器，从字符串解析到构建表达式树，再到递归求值，一步步揭开编译器处理数学表达式的神秘面纱。

1. 表达式计算器的核心原理

表达式计算的核心在于理解运算符优先级和结合性。比如2+3*4应该先计算乘法再计算加法。这种优先级关系可以通过运算符栈和操作数栈来管理，这就是著名的Shunting-yard算法。

表达式树的构建则是将中缀表达式转换为二叉树结构，其中：

• 叶子节点是操作数
• 内部节点是运算符
• 子树表示子表达式

这种表示法的优势在于：

1. 直观反映运算优先级
2. 便于后续遍历求值
3. 容易扩展新运算符

2. 项目架构设计

我们的计算器将分为三个主要模块：

2.1 词法分析模块

enum TokenType { NUMBER, OPERATOR, PAREN }; struct Token { TokenType type; std::string value; }; std::vector<Token> tokenize(const std::string& expr) { // 实现字符串到token序列的转换 }

2.2 语法分析模块

struct Node { std::string value; Node* left; Node* right; }; Node* buildExpressionTree(const std::vector<Token>& tokens) { // 实现从token序列构建表达式树 }

2.3 求值模块

double evaluate(Node* root) { // 递归遍历表达式树计算结果 }

3. 关键实现细节

3.1 运算符优先级处理

我们使用一个优先级表来决定运算符的处理顺序：

对应的优先级比较函数：

int getPrecedence(const std::string& op) { if (op == "+" || op == "-") return 1; if (op == "*" || op == "/") return 2; if (op == "^") return 3; return 0; }

3.2 双栈算法的实现

核心算法流程：

1. 初始化运算符栈和操作数栈
2. 遍历token序列：
   • 遇到数字直接压入操作数栈
   • 遇到运算符：
     • 弹出栈顶优先级更高或相等的运算符
     • 构建子树并压回操作数栈
     • 当前运算符入栈
3. 处理栈中剩余运算符

Node* shuntingYard(const std::vector<Token>& tokens) { std::stack<Node*> output; std::stack<std::string> operators; for (const auto& token : tokens) { if (token.type == NUMBER) { output.push(new Node{token.value, nullptr, nullptr}); } else if (token.type == OPERATOR) { while (!operators.empty() && getPrecedence(operators.top()) >= getPrecedence(token.value)) { processOperator(output, operators); } operators.push(token.value); } // 处理括号逻辑... } // 处理剩余运算符... return output.top(); }

4. 完整实现与优化

4.1 内存管理

使用智能指针避免内存泄漏：

struct Node { std::string value; std::unique_ptr<Node> left; std::unique_ptr<Node> right; };

4.2 错误处理

添加输入验证和错误提示：

try { auto tokens = tokenize(expr); auto tree = buildExpressionTree(tokens); return evaluate(tree.get()); } catch (const std::exception& e) { std::cerr << "计算错误: " << e.what() << std::endl; return NAN; }

4.3 扩展功能

支持更多运算符和函数：

double evaluate(Node* node) { if (!node->left && !node->right) { return std::stod(node->value); } double left = evaluate(node->left.get()); double right = evaluate(node->right.get()); if (node->value == "+") return left + right; if (node->value == "-") return left - right; if (node->value == "*") return left * right; if (node->value == "/") { if (right == 0) throw std::runtime_error("除零错误"); return left / right; } // 添加更多运算符... }

5. 测试与调试技巧

5.1 单元测试示例

void testEvaluator() { assert(compute("2+3*4") == 14); assert(compute("(2+3)*4") == 20); assert(compute("2^3^2") == 512); // 右结合 assert(std::isnan(compute("1/0"))); }

5.2 可视化调试

打印表达式树辅助调试：

void printTree(const Node* node, int indent = 0) { if (!node) return; printTree(node->right.get(), indent + 4); std::cout << std::string(indent, ' ') << node->value << std::endl; printTree(node->left.get(), indent + 4); }

输出示例：

* + 5 2 2

这个表达式树对应的是2*(2+5)，计算结果应该是14。