C++双栈法实现算术表达式求值：从 tokenizer 到工业级鲁棒实现

简介本资源是一份面向大一下学期数据结构课程学习者的实验报告聚焦栈在算术表达式求值中的核心应用解决含括号与四则运算的合法表达式解析与计算问题。报告完整呈现“算符优先法”算法设计思想、双栈运算符栈数字栈协同工作机制、运算符优先级判定逻辑并附有详细流程图、函数调用关系、时间/空间复杂度分析均为O(n)及运行截图特别展示了输入序列与栈状态的动态变化过程便于理解栈的实时操作语义。压缩包为1个2.29MB的docx文档涵盖课程设计封面、题目描述、算法思想、核心代码实现含栈创建/出入栈/优先级比较/异常处理等10函数、运行结果分析及个人收获体会结构规范、内容详实。目前已有3619人学习下载适合数据结构初学者深入掌握栈的应用场景、算法调试技巧与工程化报告撰写方法。1. 为什么一个“、-、*、/、(、)”组成的字符串会让大一学生在数据结构实验里反复崩溃这不是一道数学题而是一次对栈本质的现场拷问。当你把3 4 * 2 / (1 - 5)这样的字符串喂给程序它得在没有编译器帮忙、不调用eval()、不依赖任何表达式解析库的前提下仅靠两个栈操作数栈 运算符栈和一套手工定义的优先级规则一步步推演、归约、弹出、压入最终吐出-1.0——这个过程不是“算出来”而是“模拟人脑手算的每一步动作”。它逼你直面运算符优先级怎么编码括号怎么打断当前流程负号和减号如何区分浮点数怎么保精度输入含空格或非法字符时是直接报错还是跳过这些细节全藏在严蔚敏《数据结构C语言版》第3章“栈和队列”的课后习题里也是王道408真题中反复出现的“栈应用”高频考点。如果你正被“数据结构实验报告”卡在这一关说明你不是不会写代码而是还没真正理解栈不是容器是控制流的暂存凭证表达式求值不是计算是语法驱动的状态机推演。本文不讲伪代码只带你用 C 写出可调试、可断点、可验证、能过所有边界测试用例的工业级实现——从最简23到带负数、小数、嵌套括号的(-2.5 3.7) * (-4) / (1 2 * 3)全部跑通。2. 用双栈法在 C 中实现算术表达式求值从 tokenizer 到状态机推演2.1 为什么必须用双栈单栈为什么必然失败很多初学者尝试只用一个栈存数字遇到就加遇到*就乘——这在12*3上当场翻车。原因很简单*的优先级高于但先出现若不暂存1这个未完成的加法2*3算完后就无法回溯到16。栈的本质是“延迟执行”运算符栈存的是“待决指令”操作数栈存的是“待决数据”。只有当新运算符优先级 ≤ 栈顶运算符时才触发“归约”——即弹出栈顶运算符和对应数量的操作数执行运算结果压回操作数栈。这个机制天然支持左结合性a-b-c → (a-b)-c和优先级中断ab*c → a(b*c)。单栈无法同时维护“待执行动作”和“待参与动作的数据”两个维度就像试图用一个记事本既记菜谱又记炒菜步骤——必然混乱。2.2 Tokenizer把字符串切分成原子单元比想象中更脏别信网上那些“用stringstreamgetline按空格切”的方案——真实表达式根本没空格。-2.5*(13)里-是负号不是减号2.5是浮点数*和(之间无空格。正确 tokenizer 必须识别四类 token数字整数/浮点数支持负号前缀运算符,-,*,/,(,)错误字符如#,无效格式如..,1.2.3,*我们不用正则C11 regex 在嵌入式或老编译器上常不可用而用状态机扫描#include vector #include string #include cctype #include stdexcept enum class TokenType { NUMBER, OPERATOR, ERROR }; struct Token { TokenType type; std::string value; // 对于 NUMBER 存数值字符串OPERATOR 存符号 }; std::vectorToken tokenize(const std::string expr) { std::vectorToken tokens; size_t i 0; while (i expr.length()) { char c expr[i]; if (std::isspace(c)) { i; continue; } // 处理负号前面是 ( 或开头 或运算符且后面是数字或 .才是负号 if (c - (i 0 || expr[i-1] ( || std::strchr(-*/, expr[i-1]) ! nullptr)) { // 向后看是否跟数字或 . size_t j i 1; bool has_digit false; while (j expr.length() (std::isdigit(expr[j]) || expr[j] .)) { if (std::isdigit(expr[j])) has_digit true; j; } if (has_digit) { // 找到负数起点 size_t start i; i j; // i 已跳到数字末尾 tokens.push_back({TokenType::NUMBER, expr.substr(start, i - start)}); continue; } } if (std::isdigit(c) || c .) { size_t j i; while (j expr.length() (std::isdigit(expr[j]) || expr[j] .)) { j; } tokens.push_back({TokenType::NUMBER, expr.substr(i, j - i)}); i j; continue; } if (std::strchr(-*/(), c)) { tokens.push_back({TokenType::OPERATOR, std::string(1, c)}); i; continue; } throw std::runtime_error(Invalid character: std::string(1, c)); } return tokens; }注意这段 tokenizer 的关键逻辑在负号判断——它不是简单看c -而是检查前驱上下文i0表示开头expr[i-1](表示左括号后strchr(...)判断前一个是运算符再确认后继是数字或小数点。这是处理-2(-3)*4这类表达式的唯一可靠方式。很多同学在这里栽跟头以为负号和减号是同一个 token结果2--3直接崩。2.3 运算符优先级表用二维数组比 map 更快、更可控C 标准库map查找是 O(log n)而运算符只有 6 种用静态数组查 O(1) 且无内存分配开销。我们定义precedence[6][6]行是栈顶运算符列是当前读入运算符值为-1(栈顶优先级高可归约)、0(相等如)遇)或(遇()、1(当前优先级高压栈)// 运算符索引映射→0, -→1, *→2, /→3, (→4, )→5 int precedence[6][6] { /* */ {-1, -1, 1, 1, -1, 1}, // 栈顶是 当前是 → 归约当前是 * → 压栈 /* - */ {-1, -1, 1, 1, -1, 1}, /* * */ {-1, -1, -1, -1, -1, 1}, /* / */ {-1, -1, -1, -1, -1, 1}, /* ( */ { 1, 1, 1, 1, 1, 0}, // ( 只能压栈除非遇到 ) /* ) */ {-1, -1, -1, -1, 0, -1} // ) 触发归约直到 ( }; int getPrecedenceIndex(char op) { switch(op) { case : return 0; case -: return 1; case *: return 2; case /: return 3; case (: return 4; case ): return 5; default: throw std::runtime_error(Unknown operator: std::string(1, op)); } }这个表的设计直接决定了算法行为(的行全为1表示无论当前是什么运算符除了)都压栈)的列全为-1除(是0表示遇到)就疯狂归约直到弹出(行对*列是1栈顶*当前 → 压栈不归约*行对列是-1*栈顶当前 → 归约因为*优先级高。这就是整个算法的“心脏节律”——所有控制流都由这个表驱动。3. 双栈核心循环状态机推演的七步铁律3.1 主循环骨架token 流驱动非字符流驱动很多实现错误地按字符遍历导致括号匹配、负号识别混乱。正确做法是先tokenize()得到 token 序列再对每个 token 做状态决策#include stack #include cctype #include cmath double evaluate(const std::string expr) { auto tokens tokenize(expr); std::stackdouble nums; // 操作数栈 std::stackchar ops; // 运算符栈 for (const auto token : tokens) { if (token.type TokenType::NUMBER) { nums.push(std::stod(token.value)); // 支持浮点 } else if (token.type TokenType::OPERATOR) { char op token.value[0]; if (op () { ops.push(op); } else if (op )) { // 归约直到 ( while (!ops.empty() ops.top() ! () { applyTopOperator(nums, ops); } if (ops.empty()) throw std::runtime_error(Mismatched parentheses); ops.pop(); // 弹出 ( } else { // 普通运算符比较优先级归约直到可压栈 while (!ops.empty() ops.top() ! ( precedence[getPrecedenceIndex(ops.top())][getPrecedenceIndex(op)] 0) { applyTopOperator(nums, ops); } ops.push(op); } } } // 扫描结束归约剩余运算符 while (!ops.empty()) { applyTopOperator(nums, ops); } if (nums.size() ! 1) throw std::runtime_error(Invalid expression format); return nums.top(); }这个循环的健壮性来自三点tokenize()已解决负号/小数/空格问题主循环只处理干净 token)的处理是独立分支强制归约到(避免((12))类嵌套漏处理结尾while(!ops.empty())确保123这种无括号表达式也能完全归约。3.2 applyTopOperator执行一次二元运算必须处理除零和栈空这是唯一真正做计算的地方也是最容易崩溃的函数void applyTopOperator(std::stackdouble nums, std::stackchar ops) { if (nums.size() 2) throw std::runtime_error(Insufficient operands for operator); if (ops.empty()) throw std::runtime_error(No operator to apply); double b nums.top(); nums.pop(); // 注意顺序a op bb 是后入栈的 double a nums.top(); nums.pop(); char op ops.top(); ops.pop(); double result; switch(op) { case : result a b; break; case -: result a - b; break; case *: result a * b; break; case /: if (std::abs(b) 1e-10) throw std::runtime_error(Division by zero); result a / b; break; default: throw std::runtime_error(Unknown operator in stack: std::string(1, op)); } nums.push(result); }提示a和b的顺序至关重要。栈是 LIFO12tokenized 后1先压栈2后压栈所以nums.top()是2nums.pop()后再top()是1。因此a是左操作数b是右操作数a - b正确b - a就错了。这是血泪经验——无数人在3-5上得到2而不是-2就是因为顺序反了。3.3 完整可运行示例附带 12 个边界测试用例把上面所有片段组合成完整.cpp文件加上main()测试#include iostream #include vector #include string #include stack #include cctype #include stdexcept #include cmath #include iomanip // [此处插入 tokenize(), getPrecedenceIndex(), precedence 表, applyTopOperator(), evaluate()] int main() { std::vectorstd::pairstd::string, double test_cases { {23, 5.0}, {12*3, 7.0}, {(12)*3, 9.0}, {-23, 1.0}, {2*(-3), -6.0}, {(-2.53.7)*(-4), -4.8}, // 浮点负数 {1234, 10.0}, {10/2/2, 2.5}, // 左结合 {2*(34)*5, 70.0}, {((12)*(34)), 21.0}, {3.141592.71828, 5.85987}, {1/(23)*4, 0.8} // 混合优先级 }; std::cout std::fixed std::setprecision(5); for (size_t i 0; i test_cases.size(); i) { try { double res evaluate(test_cases[i].first); bool pass std::abs(res - test_cases[i].second) 1e-5; std::cout [ (pass ? PASS : FAIL) ] test_cases[i].first res (expected test_cases[i].second )\n; } catch (const std::exception e) { std::cout [ERROR] test_cases[i].first - e.what() \n; } } return 0; }编译命令确保 C11g -stdc11 -o expr_eval expr_eval.cpp ./expr_eval输出应全为[PASS]。如果某个失败立刻用gdb断点打在applyTopOperator或tokenize里——这才是调试的正确姿势而不是盲目改优先级表。4. 避坑数据结构实验里最常踩的 5 个深坑与解法4.1 坑负号和减号混淆2--3解析成2 - -3还是2 - (-3)现象输入2--3报错或算成2-3即-1而非5。原因tokenizer 把第二个-当作减号但实际它是负号前缀属于--3这个整体 token 的一部分。错误实现只认单个-不向前/向后看上下文。解决严格按 2.2 节 tokenizer 实现用i0 || expr[i-1]( || strchr(-*/, expr[i-1])判断负号起始条件并将整个负数如--3中的-3作为一个 NUMBER token。2--3→ tokens:[2, -, -3]→ 计算2 - (-3) 5。4.2 坑浮点数精度丢失0.10.2算出0.30000000000000004现象测试用例0.10.2返回0.30000000000000004与期望0.3不符。原因IEEE 754 双精度浮点数无法精确表示0.1和0.2这是硬件限制非算法 bug。解决在main()测试中用abs(res - expected) 1e-10比较而非。实验报告里需注明“采用相对误差容限1e-10判定浮点结果正确性”这是标准工程实践不是取巧。4.3 坑括号不匹配时程序崩溃而非报有意义错误现象输入(12或12)时segmentation fault或stack::top() on empty stack。原因applyTopOperator未检查nums.size()2)分支未检查ops.empty()归约循环未设保护。解决所有栈操作前加if (stack.empty()) throw ...applyTopOperator开头强制检查操作数数量)分支归约后加if (ops.empty()) throw ...。错误信息必须明确如Missing closing parenthesis。4.4 坑12*3/4-5类长表达式结果错误但短表达式全对现象12、2*3单独正确但12*3/4-5算成-3.5应为-3.5等等手动算2*366/41.511.52.52.5-5-2.5——发现预期值本身要重算原因优先级表填错。常见错误是把对/设为1压栈实际/优先级更高应设为-1归约。查表行/列必须是-1。解决打印precedence表调试或写单元测试验证12*3→ 归约2*3再161*23→ 归约1*2再23。4.5 坑VS2019 或 Dev-C 下stod()报错或不识别现象编译通过但运行时std::stod抛std::invalid_argument。原因老版本 MSVC 或 MinGW 对 C11 字符串转换支持不全或输入字符串含不可见字符如\r、\0。解决1用strtod()替代char* end; double val strtod(token.value.c_str(), end); if (*end ! \0) throw std::runtime_error(Invalid number format: token.value);2在tokenize后 trim 字符串token.value.erase(0, token.value.find_first_not_of( \t\r\n));3VS2019 确保项目属性 → C/C → 语言 → “C 语言标准” 设为ISO C14 Standard (/std:c14)或更高。5. 进阶验证用 AST 构建反向验证双栈结果以及实验报告得分关键点5.1 为什么需要 AST 验证双栈是黑匣子AST 是白盒显影双栈法正确性难直观验证——你看到nums和ops栈在变但不知道中间步骤是否符合数学语义。构建抽象语法树AST能可视化整个求值逻辑struct ASTNode { enum Type { NUM, OP } type; double value; // for NUM char op; // for OP std::shared_ptrASTNode left, right; // for OP }; std::shared_ptrASTNode buildAST(const std::vectorToken tokens, size_t pos) { // 递归下降解析先处理因子数字/括号再处理项/-最后表达式*// // 此处省略具体实现重点在用途 // ... } void printAST(const std::shared_ptrASTNode node, int indent 0) { if (!node) return; std::string prefix(indent, ); if (node-type ASTNode::NUM) { std::cout prefix NUM: node-value \n; } else { std::cout prefix OP: node-op \n; printAST(node-left, indent 2); printAST(node-right, indent 2); } }生成12*3的 ASTOP: NUM: 1 OP: * NUM: 2 NUM: 3这清晰表明*在的右子树即先算2*3。而双栈执行日志应与此结构一致2、3入 nums*入 ops然后触发归约2*366入 nums入 ops最后1入 nums结束归约167。AST 是你的“后悔药”——当双栈结果可疑时画出 AST再手推双栈每一步错在哪一环一目了然。5.2 实验报告高分必备的 3 个技术细节表格老师最看重的不是代码长度而是你是否理解设计权衡。在报告“算法设计”章节务必包含以下对比表格对比维度双栈法本实现递归下降法调用std::eval()禁用时间复杂度O(n)单次扫描O(n)但函数调用开销略大O(n)但有安全风险空间复杂度O(n)栈深度最大为表达式长度O(n)递归深度同括号嵌套层数O(1)但底层解析器占用未知错误定位能力可精确报错位置token index可报错但需额外行号追踪只报“expression error”无位置扩展性易加新运算符改 precedence 表需改语法分析器侵入性强无法扩展受 Python 解析器限制教学价值完美体现栈的“延迟执行”本质体现递归与语法树思想无教学价值掩盖原理另一张表展示你的鲁棒性设计边界场景你的处理方式常见错误实现1.2.3tokenizer 报Invalid number formatstod(1.2.3)停在1.2丢弃.32*3tokenizer 在*前报错运算符栈压入后*导致优先级乱序())分支检测到空 ops →Missing (归约时nums.size()2崩溃-(-2)tokenizer 产出[-,-2]→0误判为2或2-21e52tokenizer 不支持科学计数法 → 报错stod自动解析但实验要求不支持5.3 我的血泪习惯每次提交前必做的三件事用valgrind扫内存泄漏Linux/macOSvalgrind --leak-checkfull ./expr_eval确保std::stack和std::vector无泄漏——虽然 STL 通常安全但实验报告里写“经 valgrind 验证无内存泄漏”是加分项。手写 3 个“反直觉”测试用例12*3-4/2→ 手算2*36,4/22,16-25-(23)*4→-5*4-20负号作用于整个括号2.5e01.5→ 如果 tokenizer 不支持e应报错而非stod默默接受。在报告“调试过程”章节贴一段真实 gdb 日志$ gdb ./expr_eval (gdb) b evaluate (gdb) r # 输入测试用例 (gdb) step (gdb) print nums.size() (gdb) print ops.top()展示你如何用工具定位问题比写“我仔细检查了代码”有力十倍。最后说一句这个实验的价值不在算出123而在你亲手让两个栈像钟表齿轮一样咬合转动每一步都受优先级表驱动每一次pop()都有明确语义。当(-2.53.7)*(-4)在你屏幕上打出-4.80000那不是数字是你对栈理解的具象化。希望帮到你。本文还有配套的精品资源点击获取