简介这份资源是大一下学期数据结构课程设计的算数表达式求值实验报告面向正在学习栈、算符优先法与表达式解析的初学者及需要完成同类课设的学生。报告围绕含加减乘除与括号的正整数表达式求值展开采用运算符栈与数字栈双栈协作并借助临时栈拼接多位操作数完整呈现了从问题描述、算法设计思想、核心流程图到函数调用关系与性能分析的实现脉络。压缩包内仅含1个docx文档约2.29MB内容涵盖运行环境说明、关键功能函数清单、合法与非法输入的运行截图以及除数为零、括号不匹配、非法符号等异常提示的处理思路。目前已有3620人学习下载。读者可从中获得可直接参考的课设报告框架、算符优先法的具体落地细节、栈扩容与错误检测的排错经验以及时间复杂度O(n)、空间复杂度O(n)的分析写法适合作为课程设计撰写与算法复现的对照材料。1. 算数表达式求值为什么你的栈写对了结果还是错的如果你正在做数据结构实验题目要求实现算数表达式求值你大概率已经翻过教材、看过伪代码知道要用两个栈——一个存操作数一个存运算符。然后你打开编辑器照着思路写了一遍编译通过运行输入34*2输出11没问题。再输入(34)*2输出14也对。你觉得搞定了交报告。但老师随手输入一个34*2/(1-5)你的程序输出1或者直接崩了。你盯着屏幕开始怀疑人生。这不是你一个人踩过的坑。算数表达式求值这个实验看起来是栈的入门练习实际上它是一道分水岭能跑通简单用例的人很多能正确处理所有边界的人很少。它考察的不只是「栈怎么用」而是你对运算符优先级、括号匹配、负数与减号的歧义、除零处理、多位数解析、浮点精度这一整套问题的理解。我带过几轮数据结构实验课见过太多同学在「中缀转后缀」这一步翻车也见过有人用递归下降写得漂漂亮亮但报告里说不清原理。这篇文章面向正在做这个实验、或者想把这个实验做扎实的人。我会从选型开始讲清楚为什么主流做法是「中缀转后缀再求值」然后给出可复现的代码和参数说明再把我见过的坑一条条拆开。你照着走至少能少熬两个晚上。2. 中缀转后缀为什么它是这个实验的最优解2.1 直接求值 vs 转后缀求值两条路的选择理由做算数表达式求值常见做法有两类。第一类是「双栈直接求值」边扫描边算遇到运算符就根据优先级决定是否弹出栈顶运算符进行计算。第二类是「先转后缀表达式再对后缀求值」分两步走。教材上两种都会提但实验报告里我更推荐第二种原因有三个。第一逻辑解耦。转后缀只关心运算符优先级和括号求值只关心「遇到运算符就弹两个操作数算一下」。两个函数各自职责单一调试的时候你能明确知道是转换错了还是求值错了。双栈直接求值把优先级判断和计算揉在一个循环里一旦出错你很难定位。第二后缀表达式天然没有括号求值时不需要再判断优先级。这意味着求值部分可以用一个极简的循环搞定代码量少出错概率低。第三可扩展性。如果你后面想支持更多运算符比如幂运算^或者取模%只需要改优先级表和转换逻辑求值部分几乎不用动。当然双栈直接求值也有它的价值——它更接近「一遍扫描」的直觉在某些在线判题场景下代码更短。但作为实验报告老师看的是你对原理的理解分两步走更容易讲清楚。2.2 运算符优先级表一张表决定转换正确性中缀转后缀的核心是优先级比较。我一般会定义一个函数priority(op)返回运算符的优先级数值。常见设定如下运算符优先级结合性1左结合-1左结合*2左结合/2左结合(0不参与这里有一个容易忽略的点左结合运算符在遇到同优先级时应该先弹出栈顶再入栈。比如3-42扫描到时栈顶是-两者优先级相同因为-是左结合所以先弹出-参与运算再压入。如果你写成「优先级大于才弹出」就会变成右结合3-42会算成3-(42)结果从1变成-3。这个坑我在批改实验报告时见过不下十次。括号的处理也要注意遇到(直接入栈遇到)则不断弹出栈顶运算符直到遇到(然后把(弹出丢弃。括号不参与优先级比较所以它的优先级可以设为 0保证任何运算符遇到它都不会误弹。2.3 中缀转后缀的完整实现与逐行说明下面是我常用的 Python 实现逻辑清晰适合直接放进实验报告。如果你用 C 或 Java思路完全一样只是栈需要自己实现。def infix_to_postfix(expr): # 运算符优先级表数字越大优先级越高 priority {: 1, -: 1, *: 2, /: 2} output [] # 存放后缀表达式 op_stack [] # 运算符栈 i 0 n len(expr) while i n: ch expr[i] # 情况1数字支持多位数和小数点 if ch.isdigit() or ch .: num [] while i n and (expr[i].isdigit() or expr[i] .): num.append(expr[i]) i 1 output.append(.join(num)) continue # 情况2左括号直接入栈 elif ch (: op_stack.append(ch) # 情况3右括号弹出直到左括号 elif ch ): while op_stack and op_stack[-1] ! (: output.append(op_stack.pop()) if not op_stack: raise ValueError(括号不匹配缺少左括号) op_stack.pop() # 丢弃左括号 # 情况4运算符 elif ch in priority: # 左结合优先级小于等于栈顶时弹出 while (op_stack and op_stack[-1] ! ( and priority[op_stack[-1]] priority[ch]): output.append(op_stack.pop()) op_stack.append(ch) # 情况5空格跳过 elif ch : pass else: raise ValueError(f非法字符{ch}) i 1 # 扫描结束后弹出剩余运算符 while op_stack: if op_stack[-1] (: raise ValueError(括号不匹配多余左括号) output.append(op_stack.pop()) return output这段代码有几个关键点需要说明。第一数字解析部分用了内层while循环支持12.5这样的多位数和小数。如果你只处理单个数字遇到102就会解析成1、0、、2结果完全错。第二右括号处理时检查了栈是否为空防止)多于(的情况。第三运算符弹出条件用的是而不是这是左结合的正确写法。第四扫描结束后还要检查栈里是否有未匹配的(有就报错。参数方面输入expr是一个字符串允许包含空格函数会自动跳过。输出是一个列表每个元素是数字字符串或运算符。如果你希望输出字符串用 .join(output)即可。2.4 后缀表达式求值一个循环搞定拿到后缀表达式后求值逻辑非常直接遇到数字压栈遇到运算符弹两个数计算结果压回栈。最后栈里剩下的唯一元素就是答案。def eval_postfix(postfix): stack [] for token in postfix: if token in (, -, *, /): # 注意先弹出的是右操作数 right stack.pop() left stack.pop() if token : stack.append(left right) elif token -: stack.append(left - right) elif token *: stack.append(left * right) elif token /: if right 0: raise ZeroDivisionError(除数为零) stack.append(left / right) else: stack.append(float(token)) if len(stack) ! 1: raise ValueError(表达式非法操作数多余) return stack[0]这里最容易翻车的地方是操作数顺序。栈是后进先出所以第一次pop出来的是右操作数第二次才是左操作数。如果你写成left stack.pop()再right stack.pop()减法和除法就会算反。3-4会变成4-3结果从-1变成1。这个错误极其隐蔽因为加法和乘法交换律成立你测试34和3*4都发现不了只有减法和除法才会暴露。另外除零判断必须做。实验报告里如果没写除零处理老师大概率会扣分。浮点数用float解析如果你需要整数结果可以在最后判断result.is_integer()再转int。3. 负数、减号与括号三个最容易翻车的边界3.1 负号与减号的歧义为什么-34会解析失败在中缀表达式里-有两种含义二元减号如5-3和一元负号如-3。如果你不区分-34会被当成「减号前面没有操作数」转换逻辑直接崩掉。常见做法是在扫描时判断-前面是否是数字或右括号如果不是就认为它是一元负号。处理一元负号有两种策略。第一种是在转后缀之前预处理把-3替换成(0-3)这样后续逻辑不用改。第二种是在转换函数里特殊处理遇到一元负号时直接输出一个特殊标记求值时再处理。我一般用第一种简单粗暴不容易出错。def preprocess(expr): # 去掉空格 expr expr.replace( , ) result [] for i, ch in enumerate(expr): if ch - and (i 0 or expr[i-1] in (-*/): result.append((0-1)*) # 把 -x 变成 (0-1)*x else: result.append(ch) return .join(result)这个预处理会把-34变成(0-1)*34后续转换和求值都不需要特殊处理。注意(0-1)*后面跟的是原来的数字所以-3变成(0-1)*3结果是-3正确。如果是一元负号出现在括号里比如(-34)预处理后变成((0-1)*34)也能正确处理。3.2 括号不匹配的三种情况与检测方法括号不匹配有三种左括号多余、右括号多余、左右括号交叉。交叉的情况在中缀表达式里不会出现因为括号必须成对嵌套。所以只需要检测前两种。左括号多余扫描结束后运算符栈里还有(。右括号多余遇到)时栈为空或者弹出过程中没遇到(就空了。这两种情况都要抛出明确的异常信息而不是让程序崩溃或者返回错误结果。我在实验报告里会专门写一个测试用例表覆盖这三种情况输入预期行为(34)*2正常求值结果 1434)*2报错右括号多余(34*2报错左括号多余()34报错空括号空括号()也是非法表达式但很多实现会忽略它。如果你在转换时遇到(后面直接跟)可以在右括号处理时检查栈顶是否是(如果是说明括号内没有表达式抛出异常。3.3 多位数与小数点的解析细节前面代码里已经处理了多位数和小数点但有一个细节需要注意小数点不能重复。3.2.1是非法输入但如果你只用isdigit() or ch .判断会把3.2.1当成一个数字解析然后float(3.2.1)会抛异常。更稳妥的做法是在解析数字时记录小数点是否已经出现。def parse_number(expr, i): num [] has_dot False n len(expr) while i n and (expr[i].isdigit() or expr[i] .): if expr[i] .: if has_dot: raise ValueError(非法数字多个小数点) has_dot True num.append(expr[i]) i 1 return .join(num), i这个函数返回解析后的数字字符串和新的索引位置。调用方用num, i parse_number(expr, i)即可。如果你不需要支持小数可以把小数点判断去掉只保留isdigit()。4. 避坑与排查五条血泪经验4.1 现象3-42结果是-3而不是1原因运算符弹出条件写成了priority[栈顶] priority[当前]导致同优先级的没有弹出栈顶的-表达式被当成3-(42)计算。解决把条件改成确保左结合运算符在同优先级时先弹出栈顶。改完后3-42正确输出1。4.2 现象102结果是4而不是12原因数字解析只处理了单个字符10被拆成1和0然后1023或者类似错误结果。解决用内层循环解析连续的数字字符支持多位数。如果支持小数还要处理小数点。解析完后把整个数字字符串作为一个 token 输出。4.3 现象34*2/(1-5)程序崩溃或输出inf原因除数为零没有判断。1-5结果是-44*2/(-4)是-2但如果表达式是34*2/(5-5)除数就是0直接除会抛异常或得到无穷大。解决在求值函数里对除法做除零判断抛出明确的ZeroDivisionError并在主程序里捕获异常输出友好提示。实验报告里要写明除零处理策略。4.4 现象-34报错「非法字符」或结果错误原因一元负号没有预处理转换函数把-当成二元减号发现前面没有操作数逻辑混乱。解决在转换前做预处理把一元负号替换成(0-1)*的形式。判断依据是-前面是开头、左括号或另一个运算符。预处理后所有-都是二元减号逻辑统一。4.5 现象(34)*2结果是11而不是14原因括号处理时遇到)弹出运算符直到(但弹出后忘记把(也弹出丢弃导致(留在栈里后续优先级判断出错。解决在右括号处理循环结束后显式执行op_stack.pop()丢弃左括号。同时检查栈是否为空防止右括号多余的情况。5. 从能跑到能讲实验报告的验证方法与进阶技巧5.1 用测试用例表证明你的实现是可靠的实验报告不是代码堆砌老师要看的是你验证过程。我一般会设计一张测试用例表覆盖正常表达式、边界情况、异常输入三类。每一条用例写清楚输入、预期输出、实际输出、是否通过。下面是我常用的模板编号输入预期输出测试点134*211优先级2(34)*214括号33-421左结合4102.512.5多位数与小数5-341一元负号634*2/(1-5)1综合734*2/(5-5)报错除零异常处理8(34*2报错括号不匹配异常处理934)报错括号不匹配异常处理103*4报错表达式非法异常处理这张表放在报告里比写一百行代码都有说服力。老师一眼就能看出你考虑了哪些情况哪些没考虑。5.2 递归下降另一种值得了解的求值思路如果你想让实验报告更有深度可以在最后加一节介绍递归下降求值。它的思路是把表达式拆成expr - term - factor三层每层处理不同优先级的运算符。expr处理加减term处理乘除factor处理数字和括号。递归下降不需要显式的栈代码更优雅但理解成本稍高。class Parser: def __init__(self, expr): self.tokens expr.replace( , ) self.pos 0 def parse(self): result self.expr() if self.pos len(self.tokens): raise ValueError(表达式非法多余字符) return result def expr(self): result self.term() while self.pos len(self.tokens) and self.tokens[self.pos] in -: op self.tokens[self.pos] self.pos 1 right self.term() if op : result right else: result - right return result def term(self): result self.factor() while self.pos len(self.tokens) and self.tokens[self.pos] in */: op self.tokens[self.pos] self.pos 1 right self.factor() if op *: result * right else: if right 0: raise ZeroDivisionError(除数为零) result / right return result def factor(self): if self.pos len(self.tokens): raise ValueError(表达式非法意外结束) ch self.tokens[self.pos] if ch (: self.pos 1 result self.expr() if self.pos len(self.tokens) or self.tokens[self.pos] ! ): raise ValueError(括号不匹配) self.pos 1 return result elif ch -: self.pos 1 return -self.factor() else: num, self.pos parse_number(self.tokens, self.pos) return float(num)递归下降的优点是代码结构清晰每一层职责明确。缺点是递归深度受表达式长度限制超长表达式可能栈溢出。对于实验报告来说两种方法都写出来对比能体现你对问题理解的深度。5.3 浮点精度为什么0.10.2不等于0.3如果你用float做运算0.10.2的结果是0.30000000000000004。这不是 bug是 IEEE 754 浮点数的固有特性。实验报告里如果涉及小数运算最好说明这一点。解决方案有两种一是用decimal.Decimal做精确计算二是输出时格式化保留合理位数。from decimal import Decimal def eval_postfix_decimal(postfix): stack [] for token in postfix: if token in (, -, *, /): right stack.pop() left stack.pop() if token : stack.append(left right) elif token -: stack.append(left - right) elif token *: stack.append(left * right) elif token /: if right 0: raise ZeroDivisionError(除数为零) stack.append(left / right) else: stack.append(Decimal(token)) return stack[0]用Decimal后0.10.2精确等于0.3。但Decimal的运算速度比float慢如果表达式很长性能会有影响。实验报告里可以两种都测一下对比结果和耗时。5.4 一个我至今保留的习惯每次写完求值函数我不会直接跑复杂表达式。我会先跑11再跑2*3再跑(12)*3再跑1-2再跑4/2最后才跑综合表达式。这个顺序能让我在每一步都确认基本逻辑是对的而不是一上来就被复杂表达式搞晕。如果1-2输出1我立刻知道是操作数顺序反了不用去翻转换代码。这个习惯帮我省了很多时间。希望帮到你。本文还有配套的精品资源点击获取