1. 项目概述从字符串到结果一个计算器的诞生“表达式求值”这听起来像是一个教科书里枯燥的算法题对吧但如果你把它想象成一个简易计算器的核心引擎事情就变得有趣多了。我们每天都在用手机或电脑上的计算器输入一串像(3 4) * 5 - 6这样的字符然后瞬间得到结果。这个“瞬间”背后就是表达式求值算法在默默工作。今天我就来拆解这个用 C 实现简易计算器的全过程这不仅是数据结构中“栈”的经典应用更是理解编译器如何“读懂”代码的绝佳入门案例。对于初学者你可能会觉得直接按数学顺序计算不就行了但计算机是“死脑筋”它需要明确的、无二义性的指令。1 2 * 3对人类来说先乘除后加减是常识但对计算机的输入流来说它看到的只是一个字符序列。我们的任务就是设计一套规则让计算机能像我们一样理解运算优先级和括号。这个过程本质上是一个微型解释器的构建。无论你是想巩固 C 语法、深入理解栈数据结构还是为未来学习编译原理打基础这个项目都是一个完美的起点。接下来我会带你一步步实现它并分享那些只有动手写过才会知道的“坑”和技巧。2. 核心思路拆解为什么是“栈”和“后缀表达式”在动手写代码之前我们必须搞清楚核心算法。直接从中缀表达式就是我们平常写的1 2计算程序需要不断地“向前看”以确定优先级逻辑会非常复杂且容易出错。因此成熟的方案普遍采用一个“中转站”先将中缀表达式转换为后缀表达式逆波兰表达式再对后缀表达式求值。而这两个过程都高度依赖“栈”这种数据结构。2.1 中缀、前缀与后缀理解表达式的三种面貌这是理解整个算法的基石。所谓“缀”指的是运算符相对于操作数的位置。中缀表达式运算符在操作数中间如A B。符合人类习惯但计算机处理麻烦需要处理优先级和括号。前缀表达式运算符在操作数前面如 A B。也叫波兰表达式。后缀表达式运算符在操作数后面如A B 。也叫逆波兰表达式。后缀表达式的最大优点在于完全消除了优先级和括号。整个表达式从左到右扫描遇到操作数就存起来遇到运算符就从之前存的操作数中取出最近的两个进行计算再把结果存回去。这个“存起来”的容器就是栈。举个例子中缀(3 4) * 5 - 6对应的后缀表达式是3 4 5 * 6 -。 计算过程读到3,4压入栈[3, 4]读到弹出4和3计算347结果7入栈[7]读到5入栈[7, 5]读到*弹出5和7计算7*535结果入栈[35]读到6入栈[35, 6]读到-弹出6和35计算35-629结果入栈[29]扫描结束栈顶的29就是最终结果。可以看到计算过程变得极其规整只需要一个简单的栈和一套固定的规则遇到操作数入栈遇到运算符出栈两个数运算后结果入栈即可。2.2 算法总览两步走策略所以我们整个计算器的实现分为两个核心阶段对应两个核心函数中缀转后缀将用户输入的字符串如12*(3-4)转换成一个后缀表达式的序列。这个过程需要处理运算符优先级和括号。后缀表达式求值对得到的后缀表达式序列进行计算得到最终结果。而在这第一步之前我们还需要一个预备步骤词法分析。也就是把输入的字符串拆解成一个一个的“单词”称为 Token比如数字123、运算符、左括号(等。这是为了让程序能理解输入的基本单元。整个流程可以概括为原始字符串-词法分析-中缀Token序列-中缀转后缀-后缀Token序列-求值-最终结果。注意很多教学示例为了简化将“中缀转后缀”和“求值”两个步骤合并在转换过程中穿插计算。我强烈建议初学者将这两个步骤清晰地分开实现。这不仅是更模块化的设计便于调试和理解也完全符合编译原理中“语法分析”与“解释执行”分离的思想。先确保你能正确转换出后缀表达式再单独测试求值最后组合起来成功率会高很多。3. 核心数据结构与词法分析3.1 定义Token统一表示表达式中的元素首先我们需要一种数据结构来统一表示表达式中的各种元素无论是数字还是运算符。我们定义一个Token结构体。#include cctype // 用于 isdigit 函数 struct Token { bool isOperator; // true表示运算符false表示操作数 union { char op; // 当isOperator为true时存储运算符字符 - * / ( ) int num; // 当isOperator为false时存储整数值 }; // 构造函数 - 用于操作数 Token(int n) : isOperator(false), num(n) {} // 构造函数 - 用于运算符 Token(char c) : isOperator(true), op(c) {} // 默认构造函数 Token() : isOperator(false), num(0) {} };这里使用了union来节省内存因为一个 Token 要么是运算符要么是操作数。两个构造函数让后续代码更清晰。这是比单纯用三个成员变量char op; int num; bool is_op;更 C 风格的写法。3.2 词法分析器实现字符串到Token序列词法分析器parse函数的任务是遍历输入字符串识别出一个个 Token。这里最大的难点在于处理正负号与减号的歧义。规则出现在表达式开头或(之后的或-是正负号属于后面数字的一部分其他情况下的-是加减运算符。#include string #include vector #include stdexcept // 用于异常处理 std::vectorToken parse(const std::string expr) { std::vectorToken tokens; int i 0; int n expr.length(); bool expectOperand true; // 关键标志true表示期望下一个Token是操作数或正负号 while (i n) { char ch expr[i]; // 跳过空格 if (isspace(ch)) { i; continue; } // 处理数字可能带正负号 if (isdigit(ch) || (expectOperand (ch || ch -))) { int sign 1; // 处理正负号 if (ch || ch -) { sign (ch -) ? -1 : 1; i; // 确保正负号后面跟着数字 if (i n || !isdigit(expr[i])) { throw std::runtime_error(Syntax error: expected digit after sign at position std::to_string(i)); } } // 解析整数部分 int value 0; while (i n isdigit(expr[i])) { value value * 10 (expr[i] - 0); i; } tokens.push_back(Token(sign * value)); expectOperand false; // 数字后面应该跟运算符或右括号 } // 处理运算符 - * / 和括号 else if (ch || ch - || ch * || ch / || ch ( || ch )) { // 此时的 - 一定是运算符不是正负号 tokens.push_back(Token(ch)); i; // 更新期望状态左括号后期望操作数右括号/数字后期望运算符 if (ch () { expectOperand true; } else if (ch )) { expectOperand false; } else { // 是 - * / 运算符 expectOperand true; } } else { // 遇到非法字符 throw std::runtime_error(Lexical error: invalid character std::string(1, ch) at position std::to_string(i)); } } return tokens; }关键点与避坑指南expectOperand标志位这是优雅处理正负号歧义的核心。它标识了在当前位置语法上期望出现的是一个操作数或正负号还是一个运算符。初始化时表达式开头当然期望操作数true。遇到(或运算符后期望操作数遇到数字或)后期望运算符。错误处理代码中加入了简单的错误检测如正负号后无数字、非法字符等。在实际项目中更详细的错误定位如括号不匹配可以后续添加但基础的错误检测能极大提升调试效率。使用std::vector相比固定大小的数组vector能动态增长更安全、更现代。我们不再需要关心最大 Token 数量。整数溢出这段代码没有处理超大整数value value * 10 ...可能溢出。对于教学项目可以忽略或使用long long。在工业级计算器中你需要引入大数处理。4. 中缀表达式转后缀表达式这是算法的核心难点。我们使用一个运算符栈来辅助转换。核心规则是比较当前运算符与栈顶运算符的优先级以决定是入栈还是将栈顶运算符输出。4.1 优先级定义与比较// 获取运算符的优先级数值越大优先级越高 int getPriority(char op) { switch (op) { case : case -: return 1; case *: case /: return 2; case (: return 0; // 左括号在栈内时优先级最低保证其他运算符能压入其上 default: return -1; // 非法运算符 } } // 比较运算符优先级 bool hasHigherPrecedence(char op1, char op2) { return getPriority(op1) getPriority(op2); }注意这里给左括号(设置了栈内优先级为 0。这是一个常用技巧确保任何运算符除了)遇到栈顶的(时都能直接入栈。4.2 转换算法实现调度场算法经典的“调度场算法”步骤如下初始化一个空栈用于存放运算符和一个空列表用于输出后缀表达式。从左到右扫描中缀表达式的每个 Token。如果 Token 是操作数直接加入输出列表。如果 Token 是运算符op只要栈非空且栈顶不是(且op的优先级小于等于栈顶运算符的优先级就将栈顶运算符弹出并加入输出列表。将op压入栈中。如果 Token 是左括号(直接压入栈中。如果 Token 是右括号)不断将栈顶运算符弹出并加入输出列表直到遇到左括号(。弹出左括号丢弃不加入输出。扫描结束后将栈中所有剩余的运算符依次弹出并加入输出列表。std::vectorToken infixToPostfix(const std::vectorToken infixTokens) { std::vectorToken postfixTokens; // 输出列表 std::vectorToken opStack; // 运算符栈用vector模拟 for (const Token tok : infixTokens) { if (!tok.isOperator) { // 操作数直接输出 postfixTokens.push_back(tok); } else { char op tok.op; if (op () { opStack.push_back(tok); } else if (op )) { // 弹出直到遇到左括号 while (!opStack.empty() opStack.back().op ! () { postfixTokens.push_back(opStack.back()); opStack.pop_back(); } if (opStack.empty()) { throw std::runtime_error(Syntax error: mismatched parentheses); } opStack.pop_back(); // 弹出左括号 } else { // 处理 - * / 运算符 // 当栈非空栈顶不是(且当前运算符优先级栈顶优先级时弹出栈顶 while (!opStack.empty() opStack.back().op ! ( !hasHigherPrecedence(op, opStack.back().op)) { postfixTokens.push_back(opStack.back()); opStack.pop_back(); } opStack.push_back(tok); } } } // 扫描结束弹出栈中所有剩余运算符 while (!opStack.empty()) { if (opStack.back().op () { throw std::runtime_error(Syntax error: mismatched parentheses); } postfixTokens.push_back(opStack.back()); opStack.pop_back(); } return postfixTokens; }实操心得优先级比较的条件while循环的条件!hasHigherPrecedence(op, opStack.back().op)是关键。它意味着当当前运算符op的优先级不高于栈顶运算符时就要弹出栈顶。这保证了相同优先级的运算符如连续的和-是左结合的即从左往右计算。括号处理左括号(入栈时像一个“屏障”其后的运算符入栈时不会因为优先级低而弹出它。右括号)像一个“终结符”强制弹出直到左括号这正好处理了括号内子表达式的优先级。错误检查在弹出直到左括号和最后清空栈时检查栈是否为空或是否残留左括号可以有效检测括号不匹配的错误。调试技巧在开发时可以单独测试这个函数。输入一个中缀 Token 序列打印出转换后的后缀序列与手工转换的结果对比能快速定位逻辑错误。5. 后缀表达式求值这是最简单的一步只需要一个操作数栈。int evaluatePostfix(const std::vectorToken postfixTokens) { std::vectorint valStack; // 操作数栈存储int for (const Token tok : postfixTokens) { if (!tok.isOperator) { // 操作数入栈 valStack.push_back(tok.num); } else { // 运算符需要两个操作数 if (valStack.size() 2) { throw std::runtime_error(Syntax error: insufficient operands for operator); } // 注意弹出顺序先弹出的是右操作数后弹出的是左操作数 int right valStack.back(); valStack.pop_back(); int left valStack.back(); valStack.pop_back(); int result 0; switch (tok.op) { case : result left right; break; case -: result left - right; break; // left - right case *: result left * right; break; case /: if (right 0) { throw std::runtime_error(Arithmetic error: division by zero); } result left / right; // 整数除法 break; default: throw std::runtime_error(Internal error: unknown operator); } valStack.push_back(result); } } // 最终栈中应只有一个值即结果 if (valStack.size() ! 1) { throw std::runtime_error(Syntax error: invalid expression); } return valStack.back(); }关键细节与常见错误操作数弹出顺序这是最容易出错的地方对于减法和除法顺序至关重要。因为栈是“后进先出”所以先弹出的是右操作数后弹出的是左操作数。计算left op right时必须是left - right和left / right。搞反了会导致结果错误。错误处理除法运算前检查除数是否为零是必须的。同时在运算符处理时检查操作数栈大小在最后检查栈内元素数量能捕获许多表达式格式错误如运算符过多、操作数过多。整数除法这里实现的是整数除法5 / 2结果是2。如果你想支持浮点数需要将Token中的num改为double并相应调整词法分析和求值逻辑。6. 整合与功能扩展打造一个健壮的计算器现在我们将三个核心模块组合起来并添加用户交互和错误处理形成一个完整的程序。#include iostream #include string #include vector #include stdexcept #include cctype // 此处插入之前定义的 Token 结构体、parse, getPriority, hasHigherPrecedence, infixToPostfix, evaluatePostfix 函数 int main() { std::string input; std::cout 简易表达式计算器 (支持 - * / 和括号输入 exit 退出)\n; while (true) { std::cout ; std::getline(std::cin, input); if (input exit || input quit) { break; } if (input.empty()) { continue; } try { // 1. 词法分析 std::vectorToken infixTokens parse(input); // 可选打印中缀Token序列用于调试 // std::cout Infix Tokens: ; // for (auto t : infixTokens) { // if (t.isOperator) std::cout t.op ; // else std::cout t.num ; // } // std::cout std::endl; // 2. 中缀转后缀 std::vectorToken postfixTokens infixToPostfix(infixTokens); // 可选打印后缀表达式 // std::cout Postfix: ; // for (auto t : postfixTokens) { // if (t.isOperator) std::cout t.op ; // else std::cout t.num ; // } // std::cout std::endl; // 3. 后缀表达式求值 int result evaluatePostfix(postfixTokens); std::cout result std::endl; } catch (const std::exception e) { std::cerr 错误: e.what() std::endl; } } std::cout 再见 std::endl; return 0; }6.1 如何测试你的计算器编译运行后你可以尝试以下表达式验证其正确性1 2 * 3-7(1 2) * 3-9-5 3 * 2-1(测试负号)10 - 3 - 2-5(测试左结合性)3 * (4 5) / 2-13(整数除法)6.2 功能扩展思路一个基础版本完成后你可以考虑以下扩展这会让你的项目更有深度支持浮点数将Token中的num改为double类型修改parse函数以解析如3.14这样的数字。注意浮点数比较的精度问题。支持更多运算符如求余%、幂运算^。添加运算符时需要在getPriority函数中定义其优先级幂运算通常是右结合需要特殊处理。支持数学函数如sin,cos,sqrt。这需要扩展 Token 类型例如增加一个func字段并在词法分析中识别函数名在后缀求值时调用对应的数学库函数。变量支持允许用户定义变量如x 5并在表达式中使用。这需要引入一个符号表如std::mapstd::string, double来存储变量名和值。错误恢复与高亮当表达式有语法错误时不仅抛出异常还能指出错误的大概位置提供更好的用户体验。图形界面使用 Qt、ImGui 或简单的控制台图形库制作一个带有按钮的 GUI 计算器将按钮事件连接到你的表达式求值引擎。7. 常见问题排查与性能优化在实际编写和运行过程中你可能会遇到以下问题问题1对于表达式1 - 2 - 3我的程序结果是2而不是-4。排查这几乎肯定是操作数弹出顺序错了。在evaluatePostfix的减法部分你很可能写成了result right - left;。请确保是result left - right;。对于除法同理。验证后缀表达式1 2 - 3 -的计算过程1,2入栈遇到-弹出2(右)和1(左)计算1-2-1入栈栈为[-1,3]遇到-弹出3(右)和-1(左)计算-1-3-4。问题2带括号的复杂表达式结果不对。排查首先单独测试infixToPostfix函数。输入中缀 Token 序列打印出转换的后缀序列与手工计算的结果对比。常见错误在于优先级比较逻辑或括号弹出逻辑。技巧在infixToPostfix函数的关键位置如每次入栈、出栈时添加调试输出打印当前 Token 和栈的状态能非常直观地看到算法执行过程。问题3程序遇到空格或非法字符崩溃。排查检查parse函数。确保isspace()函数被正确用于跳过空格。在else分支即非数字、非运算符、非空格添加了异常抛出这能防止程序继续解析无效输入。问题4对于超大表达式程序是否有效率问题分析算法的时间复杂度是O(n)其中 n 是表达式长度。每个 Token 最多入栈、出栈一次。空间复杂度也是 O(n)用于存储 Token 序列和栈。对于任何合理的输入长度几千以内性能都不是问题。优化点避免拷贝在函数传参和返回时考虑使用const引用和移动语义C11 及以上。例如infixToPostfix的参数可以是const std::vectorToken。预留空间如果你能预估 Token 数量可以使用vector::reserve()预先分配内存减少动态扩容的开销。自定义栈对于极致性能场景可以用原生数组和索引手动模拟栈避免std::vector的边界检查开销。但对于学习项目std::vector的清晰性和安全性更重要。问题5我想支持更复杂的表达式比如函数调用sin(0.5)该怎么改思路这需要升级你的词法分析和语法模型。扩展 Token增加类型如FUNC。修改词法分析识别字母开头的单词作为函数名。修改中缀转后缀函数名如sin可以像左括号一样直接压入一个特殊的“函数栈”或者将其视为一个特殊的、高优先级的运算符。当遇到右括号时弹出直到左括号并将对应的函数名输出到后缀序列。修改求值在后缀序列中遇到FUNC类型的 Token从操作数栈弹出一个参数调用对应的数学函数将结果压回栈中。实现一个表达式求值器就像给计算机安装了一个理解数学语言的小脑。从混乱的字符串到清晰的后缀表达式再到最终的结果每一步都体现了将复杂规则分解为简单步骤的计算思维。我建议你在理解上述代码后不要复制粘贴而是自己从头敲一遍。在敲代码的过程中你会被迫思考每一个细节这才是真正内化知识的过程。当你第一次看到自己写的程序正确算出(12)*34/2等于11时那种成就感是无可替代的。这个项目虽然基础但它所蕴含的栈的应用、状态机思想词法分析、调度场算法都是软件开发的宝贵财富。