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

用C手搓一个表达式计算器从字符串解析到二叉树求值附完整代码在编程的世界里表达式计算器是一个既经典又实用的项目。它不仅能帮助我们理解编译原理的基础知识还能锻炼数据结构与算法的应用能力。本文将带你用C实现一个完整的表达式计算器从字符串解析到构建表达式树再到递归求值一步步揭开编译器处理数学表达式的神秘面纱。1. 表达式计算器的核心原理表达式计算的核心在于理解运算符优先级和结合性。比如23*4应该先计算乘法再计算加法。这种优先级关系可以通过运算符栈和操作数栈来管理这就是著名的Shunting-yard算法。表达式树的构建则是将中缀表达式转换为二叉树结构其中叶子节点是操作数内部节点是运算符子树表示子表达式这种表示法的优势在于直观反映运算优先级便于后续遍历求值容易扩展新运算符2. 项目架构设计我们的计算器将分为三个主要模块2.1 词法分析模块enum TokenType { NUMBER, OPERATOR, PAREN }; struct Token { TokenType type; std::string value; }; std::vectorToken tokenize(const std::string expr) { // 实现字符串到token序列的转换 }2.2 语法分析模块struct Node { std::string value; Node* left; Node* right; }; Node* buildExpressionTree(const std::vectorToken tokens) { // 实现从token序列构建表达式树 }2.3 求值模块double evaluate(Node* root) { // 递归遍历表达式树计算结果 }3. 关键实现细节3.1 运算符优先级处理我们使用一个优先级表来决定运算符的处理顺序运算符优先级结合性, -1左*, /2左^3右(0-对应的优先级比较函数int getPrecedence(const std::string op) { if (op || op -) return 1; if (op * || op /) return 2; if (op ^) return 3; return 0; }3.2 双栈算法的实现核心算法流程初始化运算符栈和操作数栈遍历token序列遇到数字直接压入操作数栈遇到运算符弹出栈顶优先级更高或相等的运算符构建子树并压回操作数栈当前运算符入栈处理栈中剩余运算符Node* shuntingYard(const std::vectorToken tokens) { std::stackNode* output; std::stackstd::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_ptrNode left; std::unique_ptrNode 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(23*4) 14); assert(compute((23)*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*(25)计算结果应该是14。