简介这份数据结构实验报告面向大一下学期正在学习数据结构与算法课程的学生围绕「算数表达式求值」这一经典课程设计题目展开帮助读者理解如何用栈与算符优先法解析并计算含加减乘除及括号的算术表达式。资源包内共1个docx文件约2.29MB内容涵盖设计题目、运行环境、算法设计思想、核心算法流程图、性能分析、运行结果截图及收获体会等完整实验报告结构。报告详细讲解运算符栈与数字栈的协同工作方式包括数字缓冲、优先级比较、括号匹配、栈的扩容与除零、非法符号、括号不匹配等异常处理并给出各功能函数说明与调用关系。目前已有3620人学习下载适合需要完成同类课程设计、撰写实验报告或巩固栈应用的读者参考可从中获取完整方案、算法思路与排错经验。1. 算数表达式求值为什么你的栈写对了结果还是错很多人第一次做算数表达式求值代码看起来完全正确跑出来却是错的。我见过最典型的场景某同学用两个栈分别存操作数和运算符逻辑照着课本抄的34*2能算出 11但一遇到(34)*2就翻车输出 10 或者直接崩掉。问题不在栈本身而在于优先级比较的边界条件没处理干净。算数表达式求值这个实验表面上是练栈实际上考的是三件事中缀表达式怎么转后缀、运算符优先级怎么定义、括号和多位数字怎么处理。这三件事任意一件没想清楚代码就会在某个测试用例上翻车。它适合刚学完栈和队列、需要一次完整练手的数据结构学习者也适合想重新梳理编译原理前端词法/语法处理思路的开发者。这篇文章不讲空泛概念直接按可复现的路径走先讲清中缀转后缀的调度场算法为什么能工作再给出完整可运行的实现然后重点拆解那些让程序“看起来对但结果错”的坑最后给一套验证方法和进阶技巧。你照着做至少能少花两小时在调试玄学上。2. 调度场算法中缀转后缀的每一步到底在做什么2.1 为什么不能直接从左到右算人脑算34*2会先算乘法但程序从左到右扫描时读到并不知道后面有没有更高优先级的运算符。如果直接算就会先算347再算7*214结果错了。解决思路有两种一是先把中缀表达式转成后缀表达式也叫逆波兰表达式后缀里运算符的顺序就是实际计算顺序二是用递归下降直接求值。实验报告里最常见、也最容易讲清楚的是第一种。后缀表达式的特点是没有括号运算符出现在两个操作数之后。比如34*2的后缀是3 4 2 * (34)*2的后缀是3 4 2 *。转成后缀后求值只需要一个操作数栈从左到右扫描遇到数字压栈遇到运算符弹出两个操作数计算再压回去最后栈顶就是结果。整个过程不需要考虑优先级因为优先级已经在转换阶段解决了。调度场算法Shunting-yard algorithm就是做这个转换的经典方法。它用一个运算符栈来暂存还没轮到输出的运算符核心规则是遇到数字直接输出遇到运算符时如果栈顶运算符优先级不低于当前运算符就先把栈顶弹出来输出直到栈顶优先级更低或者遇到左括号再把当前运算符压栈遇到左括号直接压栈遇到右括号就不断弹栈输出直到遇到左括号并把左括号弹出丢弃。扫描结束后把栈里剩余的运算符全部弹出输出。2.2 优先级表和结合性怎么定优先级表是整个算法的核心配置。常见做法是给每个运算符一个整数优先级和-为 1*和/为 2(在栈内特殊处理。但这里有一个容易被忽略的点结合性。和-是左结合的a-b-c应该算成(a-b)-c所以遇到栈顶是或-、当前也是或-时栈顶优先级不低于当前要先弹出。*和/同理。如果优先级表只写数值不处理结合性8/4/2可能算成8/(4/2)4而正确结果是(8/4)/21。下面是一个可以直接用的优先级配置用 Python 字典表示# 栈内运算符优先级数值越大优先级越高 # 左括号在栈内优先级设为 0保证任何运算符都能压到它上面 PRECEDENCE { : 1, -: 1, *: 2, /: 2, (: 0 } def precedence(op): 返回运算符优先级未知运算符返回 -1 便于排查 return PRECEDENCE.get(op, -1)这段代码里(的优先级设为 0 是关键。当栈顶是(时任何运算符的优先级都大于 0所以不会把(弹出来左括号就被“保护”住了。如果这里设成其他值比如和一样是 1那么遇到(34)时读到会把(弹出来直接崩掉。参数说明PRECEDENCE字典可以根据需要扩展%、^等运算符^是右结合的优先级比较逻辑要单独处理实验报告里一般用不到。2.3 中缀转后缀的完整实现把上面的规则写成代码输入是一个去掉空格的表达式字符串输出是后缀表达式列表def infix_to_postfix(expr): 中缀表达式转后缀表达式支持 - * / 和括号支持多位数 output [] # 存放后缀结果 op_stack [] # 运算符栈 i 0 n len(expr) while i n: ch expr[i] if ch.isdigit(): # 处理多位数字连续读入所有数字字符 num [] while i n and expr[i].isdigit(): num.append(expr[i]) i 1 output.append(.join(num)) continue # 注意这里不增加 i因为内层已经移动了 elif ch (: op_stack.append(ch) elif ch ): # 弹出直到遇到左括号 while op_stack and op_stack[-1] ! (: output.append(op_stack.pop()) if not op_stack: raise ValueError(括号不匹配缺少左括号) op_stack.pop() # 丢弃左括号 elif ch in -*/: # 栈顶优先级 当前优先级时弹出左结合 while (op_stack and op_stack[-1] ! ( and precedence(op_stack[-1]) precedence(ch)): output.append(op_stack.pop()) op_stack.append(ch) else: raise ValueError(f非法字符: {ch}) i 1 # 扫描结束后弹出剩余运算符 while op_stack: if op_stack[-1] (: raise ValueError(括号不匹配缺少右括号) output.append(op_stack.pop()) return output逻辑说明主循环用i手动控制索引因为处理多位数时需要连续读取。遇到数字时内层while把连续数字全部读完后i已经指向下一个非数字字符所以外层用continue跳过i 1避免跳过一个字符。这是多位数字处理最容易写错的地方很多人在这里少读一位或者多跳一位。运算符处理部分while条件里先判断op_stack[-1] ! (再比较优先级顺序不能反否则precedence(()返回 0虽然不会出错但逻辑上不清晰。括号不匹配的检查放在两个地方遇到)时栈空说明缺左括号扫描结束后栈里还有(说明缺右括号。2.4 后缀求值一个栈就够拿到后缀列表后求值逻辑非常直接def eval_postfix(postfix): 计算后缀表达式的值支持整数四则运算 stack [] for token in postfix: if token.lstrip(-).isdigit(): # 支持负数去掉负号后是数字就按数字处理 stack.append(int(token)) else: if len(stack) 2: raise ValueError(f表达式非法运算符 {token} 缺少操作数) b stack.pop() # 注意先弹出的是右操作数 a stack.pop() if token : stack.append(a b) elif token -: stack.append(a - b) elif token *: stack.append(a * b) elif token /: if b 0: raise ValueError(除数为零) stack.append(a // b) # 整数除法实验报告一般要求整除 if len(stack) ! 1: raise ValueError(表达式非法操作数多余) return stack[0]参数说明token.lstrip(-).isdigit()用来判断 token 是不是数字同时兼容负数。但要注意如果表达式里用-作为二元运算符它不会被误判为数字因为单独的-去掉负号后是空字符串isdigit()返回 False。除法用//是整数除法如果实验要求支持小数把int换成float、//换成/即可。弹出顺序b先、a后是关键减法和除法对顺序敏感写反了3-2会算成2-3。3. 把两个栈合成一个类工程化实现与参数调优3.1 用类封装状态避免全局变量污染实验报告里经常看到一堆全局变量和函数互相调用调试时改一个地方影响三个地方。更稳妥的做法是把转换和求值封装成一个类状态放在实例属性里。下面是一个可以直接复用的实现class ExpressionEvaluator: 算数表达式求值器支持 - * / 和括号 PRECEDENCE {: 1, -: 1, *: 2, /: 2, (: 0} def __init__(self, expr): self.expr expr.replace( , ) # 去掉所有空格 self.postfix [] def _precedence(self, op): return self.PRECEDENCE.get(op, -1) def to_postfix(self): 中缀转后缀结果存入 self.postfix output [] op_stack [] i 0 n len(self.expr) while i n: ch self.expr[i] if ch.isdigit(): num [] while i n and self.expr[i].isdigit(): num.append(self.expr[i]) i 1 output.append(.join(num)) continue elif ch (: op_stack.append(ch) elif ch ): while op_stack and op_stack[-1] ! (: output.append(op_stack.pop()) if not op_stack: raise ValueError(括号不匹配) op_stack.pop() elif ch in -*/: while (op_stack and op_stack[-1] ! ( and self._precedence(op_stack[-1]) self._precedence(ch)): output.append(op_stack.pop()) op_stack.append(ch) else: raise ValueError(f非法字符: {ch}) i 1 while op_stack: if op_stack[-1] (: raise ValueError(括号不匹配) output.append(op_stack.pop()) self.postfix output return output def evaluate(self): 先转后缀再求值返回整数结果 if not self.postfix: self.to_postfix() stack [] for token in self.postfix: if token.lstrip(-).isdigit(): stack.append(int(token)) else: if len(stack) 2: raise ValueError(f缺少操作数: {token}) b stack.pop() a stack.pop() if token : stack.append(a b) elif token -: stack.append(a - b) elif token *: stack.append(a * b) elif token /: if b 0: raise ValueError(除数为零) stack.append(a // b) if len(stack) ! 1: raise ValueError(表达式非法) return stack[0]逻辑说明__init__里直接去掉所有空格这样调用方不用关心空格问题。to_postfix和evaluate分开方便单独测试转换结果。evaluate里先检查self.postfix是否为空避免重复转换。这个类可以直接拿去做实验报告的代码部分也可以作为后续扩展的基础。3.2 参数调优优先级表怎么改、除法怎么选优先级表是唯一需要根据需求调整的参数。如果实验要求支持%取模在PRECEDENCE里加%: 2并在求值部分加一个分支。如果要求支持^幂运算注意^是右结合的2^3^2应该算成2^(3^2)512而不是(2^3)^264。右结合的处理方式是遇到^时栈顶优先级严格大于当前才弹出等于时不弹出。把while条件里的改成即可但只对^生效其他运算符还是。这个细节在实验报告里如果写了是加分项。除法有两种选择整数除法//和浮点除法/。实验报告一般要求整数运算用//。但要注意 Python 的//是向下取整-7 // 2 -4而 C 语言里-7 / 2 -3。如果实验要求跟 C 一致需要用int(a / b)。这个差异在测试负数除法时会暴露出来建议在报告里注明。3.3 测试用例设计覆盖边界比覆盖功能更重要写完代码后至少跑下面这组测试用例。它们覆盖了优先级、括号、多位数、结合性、除零和非法输入用例表达式期望结果考察点134*211乘法优先级2(34)*214括号改变优先级38/4/21左结合4100200*3700多位数5((23)*4)-515嵌套括号610/0抛异常除零73抛异常缺少操作数8(34抛异常括号不匹配跑完这组用例基本能确认实现是稳的。如果某个用例挂了对照第 4 章的排查清单定位。4. 避坑与排查那些让结果悄悄出错的细节4.1 多位数字被拆成单个字符现象输入100200结果是123或者直接报错。原因扫描时每读一个字符就当成一个数字压栈没有连续读取。解决在数字分支里用内层while连续读取所有数字字符拼成完整数字后再输出。注意内层循环结束后i已经指向下一个非数字字符外层要用continue跳过i 1否则会跳过一个字符。这个坑几乎每个人都会踩一次血泪经验是写完先测1234不要只测12。4.2 括号匹配检查漏掉一边现象输入(34程序不报错但结果不对或者输入34)直接崩。原因只检查了遇到)时栈里有没有(没检查扫描结束后栈里还有没有残留的(。解决在两个地方都加检查——遇到)弹栈时如果栈空了就抛异常扫描结束后如果栈里还有(也抛异常。另外左括号弹出后要丢弃不要输出到后缀里否则求值时会把它当成运算符处理。4.3 减法和除法的操作数顺序写反现象3-2算出-18/4算出0。原因后缀求值时先弹出的b是右操作数后弹出的a是左操作数计算应该是a - b和a / b不是b - a。解决记住“先弹右、后弹左”或者用变量名right和left代替b和a减少混淆。这个坑在加法乘法里不会暴露因为交换律成立所以测试用例一定要包含减法和除法。4.4 优先级比较时把左括号弹出来了现象(34)*2算出34*211或者直接崩。原因优先级表里(的值设得不对或者while条件里没有排除(。解决(的优先级设为 0并且在弹出条件里加op_stack[-1] ! (。这样任何运算符都不会把(弹出来左括号只有在遇到)时才被丢弃。4.5 除零和非法表达式没有提前拦截现象程序在某个用例上直接崩溃报ZeroDivisionError或者IndexError而不是给出友好提示。原因求值前没有检查操作数数量除法前没有检查除数是否为零。解决在弹出两个操作数之前检查栈大小是否至少为 2除法前检查b 0并抛出带说明的异常。实验报告里异常处理是加分项不要省。5. 进阶技巧从能跑到能讲清楚5.1 用递归下降替代调度场代码更短但更难调调度场算法是迭代的逻辑清晰但代码量大。另一种思路是递归下降把表达式按优先级分层解析parse_expression处理加减parse_term处理乘除parse_factor处理数字和括号。核心代码大概三十行但递归调用的边界条件更容易写错。如果实验报告要求体现“分治”思想递归下降是更好的选择如果要求体现“栈的应用”调度场更贴题。两种方法我都写过递归下降在支持一元负号时更自然调度场在支持自定义运算符时更灵活。5.2 加一个简单的词法分析器把数字和运算符分开现在的实现是边扫描边判断字符类型逻辑耦合在一起。更工程化的做法是先做词法分析把输入拆成 token 列表每个 token 带类型数字、运算符、左括号、右括号。这样转换和求值都只处理 token不用再关心字符级别的问题。词法分析器大概二十行def tokenize(expr): 把表达式拆成 token 列表每个 token 是 (类型, 值) tokens [] i 0 n len(expr) while i n: ch expr[i] if ch.isspace(): i 1 continue if ch.isdigit(): num [] while i n and expr[i].isdigit(): num.append(expr[i]) i 1 tokens.append((NUM, int(.join(num)))) continue if ch in -*/(): tokens.append((OP, ch)) i 1 continue raise ValueError(f非法字符: {ch}) return tokens有了 token 列表后中缀转后缀的代码可以简化成对 token 列表的遍历不用再处理多位数和空格。这个重构在实验报告里可以作为“改进方向”写一段体现你对代码结构的思考。5.3 验证方法用随机表达式对拍手工测试用例覆盖有限更可靠的验证方式是随机生成表达式同时用两种方法求值对比结果。一种方法是你自己写的求值器另一种是 Python 内置的eval。生成表达式时控制运算符和括号确保不出现除零。下面是一个简单的对拍脚本import random def random_expr(depth0): 随机生成表达式depth 控制嵌套深度 if depth 2 or random.random() 0.3: return str(random.randint(1, 20)) op random.choice([, -, *, /]) left random_expr(depth 1) right random_expr(depth 1) if op /: # 避免除零把右边包成非零表达式 right f({right}1) if random.random() 0.3: return f({left}{op}{right}) return f{left}{op}{right} for _ in range(1000): expr random_expr() try: expected eval(expr) except ZeroDivisionError: continue # 注意 eval 返回浮点数整数除法需要转换 expected int(expected) actual ExpressionEvaluator(expr).evaluate() if expected ! actual: print(f不一致: {expr}, 期望 {expected}, 实际 {actual}) break else: print(1000 组随机测试全部通过)这个脚本跑通基本可以确认实现没有逻辑漏洞。注意eval的除法是浮点除法所以要用int转换并且生成的表达式要避免除零。如果对拍发现不一致把出错的表达式单独拿出来用第 4 章的排查清单逐条检查。5.4 一个我常犯的错误早期写这个实验时我总喜欢在转换阶段就把能算的算掉觉得这样求值更快。结果代码越写越复杂遇到括号就乱套。后来才想明白转换和求值必须严格分开转换阶段只负责调整顺序不碰数值求值阶段只负责按顺序计算不碰优先级。这个边界一旦模糊调试成本会翻倍。现在我的习惯是先把后缀表达式打印出来确认顺序对了再去看求值结果。如果后缀是对的但结果错了问题一定在求值阶段的操作数顺序或除零处理上。这个习惯帮我省了很多后悔药。希望帮到你。本文还有配套的精品资源点击获取