简介面向高校数据结构课程学习者尤其是西南交通大学相关课程学生这份docx实验报告完整呈现了中缀表达式求值实验的内容与实现方案。实验要求从键盘输入中缀表达式利用操作数和运算符双栈完成计算覆盖加减乘除、括号并支持提高要求中的正负号与任意整型操作数重点在于掌握栈在表达式求值中的应用。文中给出数据结构与算法设计包括栈的动态创建、出入栈操作、isp与icp优先级比较、数字字符转换、Connect运算连接等关键函数源程序采用C语言定义了运算符栈StackTR和操作数栈StackND通过#作为基准处理表达式边界。资源包共1个docx文件大小约51KB目前已近2900人学习浏览适合正在完成同类实验或撰写实验报告的学生借鉴也可用于复习栈和运算符优先级的核心机制。1. 中缀表达式求值实验卡住你的不是栈而是优先级这个黑匣子“中缀表达式求值”是数据结构实验报告里被写烂了却依然容易翻车的题目。说它基础是因为 32*3 这种式子小学生都算得明白说它坑是因为要让计算机“看懂”优先级得自己维护运算符栈、操作数栈还得处理括号、多位数、负号和一串看起来正常一跑就崩的边界输入。这篇笔记把栈与队列在这个题目里到底扮演什么角色讲清楚再给一条能直接复现的实现路径最后把 5 个高频报错和验证方法摆出来。适合正在写实验报告的大二学生、准备考研数据结构 408 的复习者以及想拿栈真正做个小计算器的开发者。2. 栈与队列的分工中缀求值为什么靠两栈模型立住先别急着写代码想清楚一个问题为什么这个实验不叫“数组表达式求值”而叫“栈与队列”因为求值过程里最核心的动作就是“读进来的东西先存着按规则再取出来”。存取的顺序一旦变了结果就错。而这个顺序规则正是栈和队列各自最擅长的部分。2.1 让运算“挂起”的机制运算符栈与操作数栈怎么配合中缀表达式从左往右读但计算机边读边算会遇到麻烦读到“12”时不能立刻算 3因为后面还可能有“*3”这种优先级更高的运算。要让这个“等一等”变成代码最自然的容器就是栈。后进先出刚好把最晚读到、优先级最高的运算符顶在最上面先处理。以“12*3”为例跟踪一遍两栈的状态变化扫描位置动作运算符栈操作数栈1数字压操作数栈[][1]运算符栈空压栈[ , ][1]2数字压操作数栈[ , ][1, 2]*栈顶 优先级 1 小于 * 的 2压栈[, *][1, 2]3数字压操作数栈[, *][1, 2, 3]结束弹 * 得 6弹 得 7[][7]操作数栈存放“暂时没轮到计算的操作数”运算符栈存放“暂时挂起的运算符”。每次遇到新运算符先把运算符栈里优先级不低于自己的运算符结算掉这保证乘除先于加减。括号的做法是左括号没有优先级直接入栈右括号出现时把左括号之上的运算符全部结算并丢弃左括号。如果括号混在优先级比较里会破坏“不低于”的判断所以栈顶是左括号时必须停止弹出。这里顺便回答一个常见疑问为什么不能用队列存挂起的运算符如果用一个 FIFO 队列先读到的“”会被先取出来那 12*3 会先算 12结果必然错。“后挂起的先执行”是栈的任务队列适合的是“先到的先消费”它在该出场的地方出场就看第 2.2 节怎么用。2.2 队列不是陪跑循环队列在表达式序列里的两个正经用途说“两种结构都要考”并不是让队列参与求值主流程而是说队列在表达式的生产和消费阶段有用。常见做法有两个方向第一个方向中缀转后缀的调度场算法输出序列按扫描顺序生成后续求值也按这个顺序消费。这个中间缓冲用队列语义最顺前面的栈负责“挂起”队列负责“按顺序排队”职责不重叠。第二个方向如果实验要求明确考察循环队列可以把输入串先解析成 token 存入一个循环队列再由求值器从队头取 token。这种环形缓冲的判空判满正好是考研数据结构 408 里常考的实现细节标题里“栈与队列”两个词要靠它落下来。#define MAXQ 256 typedef struct { double data[MAXQ]; /* 这里只演示 rearlength 判空判满实际存 token 时换成自定义结构体 */ int rear; /* 下一次写入的位置 */ int length; /* 当前元素个数 */ } LoopQueue; int loopq_empty(LoopQueue *q) { return q-length 0; } int loopq_full(LoopQueue *q) { return q-length MAXQ; } int loopq_push(LoopQueue *q, double v) { if (loopq_full(q)) return 0; /* 满队列直接拒绝 */ q-data[q-rear] v; q-rear (q-rear 1) % MAXQ; /* 环形回绕 */ q-length; return 1; }这段代码的关键参数是rear和length。rear指向下一次写入位置length记录当前元素个数。这种方案不需要牺牲一个存储单元来区分队空和队满如果用front和rear两个指针判满则要求(rear1) % MAXQ front这会平白少用一个格子。报告里写清自己用的是哪一种判空判满答辩时很加分。流水线关系也清楚了词法扫描器把表达式变成队列里一个个 token求值器再从队列按先进先出取走进入两栈结算。整体是一个“读入 → 排队 → 结算”的过程栈和队列各管一段不是硬凑。这也解释了为什么实验题目要叫“栈与队列”而不是单独叫“栈的应用”。3. 中缀转后缀与双栈直接求值我的选型和最小可运行代码确立了栈与队列的角色后下一步选主算法。常见做法是把实验拆成“中缀转后缀”和“后缀求值”两段也有报告直接用“运算符栈 操作数栈”边读边算。建议两条路线都在报告里做方案对比但代码只实现一条主路线否则工作量翻倍还容易接不上。3.1 调度场算法中缀转后缀把优先级变成顺序下面的 Python 实现假定tokenize已经准备好在第 4 章补全。核心是shunting_yard和eval_postfix两个函数加在一起就是完整求值链路。def priority(op): if op in (, -): return 1 if op in (*, /): return 2 if op ^: return 3 return 0 def is_right_assoc(op): return op ^ # 幂运算是右结合2^3^2 2^(3^2) def shunting_yard(tokens): output [] # 后缀表达式按顺序输出用队列语义消费 op_stack [] # 运算符栈挂起未结算的运算符 for kind, val in tokens: if kind num: output.append(val) elif val (: op_stack.append(val) elif val ): while op_stack and op_stack[-1] ! (: output.append(op_stack.pop()) if not op_stack: raise ValueError(括号不匹配多余的右括号) op_stack.pop() # 丢弃左括号 else: # 栈顶优先级高于当前或同为左结合运算符时先弹出结算 while op_stack and op_stack[-1] ! (: top_pri priority(op_stack[-1]) cur_pri priority(val) if top_pri cur_pri or (top_pri cur_pri and not is_right_assoc(val)): output.append(op_stack.pop()) else: break op_stack.append(val) while op_stack: if op_stack[-1] (: raise ValueError(括号不匹配缺少右括号) output.append(op_stack.pop()) return output def eval_postfix(rpn): stack [] for tok in rpn: if tok.replace(., , 1).isdigit(): stack.append(float(tok)) else: if len(stack) 2: raise ValueError(操作数不足表达式可能有误) r stack.pop() # 先弹出的是右操作数 l stack.pop() # 后弹出的是左操作数 if tok : stack.append(l r) elif tok -: stack.append(l - r) elif tok *: stack.append(l * r) elif tok /: if abs(r) 1e-12: raise ZeroDivisionError(除零错误) stack.append(l / r) elif tok ^: stack.append(l ** r) if len(stack) ! 1: raise ValueError(操作数过多表达式可能有误) return stack[0]这段代码最值得盯住的是那个while弹出条件top_pri cur_pri加上top_pri cur_pri且当前运算符不是右结合时也弹出。左结合运算符加减乘除遇到优先级相同的栈顶运算符必须弹出因为 3-2-1 要从左往右算成 (3-2)-10而不是 3-(2-1)2。is_right_assoc只给^开了口子让右结合运算保持正确的出栈顺序。priority表是整条算法的“黑匣子”扩展实验时改这一张表就行。如果要支持取负、取模这类运算就在表里加行并同步修改eval_postfix的分支。最小可运行版本里运算符白名单是 - * / ^和左右括号。3.2 双栈直接求值少一次转换多一层状态维护第二种路线是边扫描边算数字压操作数栈运算符压栈前先结算栈顶优先级不低于当前的运算符遇到右括号则结算到左括号扫完再结算剩余栈。这个方案少生成一段后缀序列代码量更小但所有状态混在一次扫描里出问题时难定位。两条路线的对比可以放在实验报告的“方案分析”一节对比项中缀转后缀 后缀求值双栈直接求值代码结构函数职责单一分段调试单循环状态多调试难度可分别打印后缀序列和求值过程出错位置不明显队列出场后缀序列天然可用队列衔接队列几乎没戏份报告讲深适合画流程图逐步讲适合讲运算挂起机制时间复杂度O(n)O(n)我一般建议实验没指定路线时选“中缀转后缀 后缀求值”理由是流程能分阶段讲清楚答辩时不容易被一问就卡住。如果实验要求点名“利用运算符栈和操作数栈直接求值”那就走双栈并把“低于栈顶才入栈”的比较条件写成注释摆在第一行。注意两条路线不要各写一半再强行拼接比如先转后缀一半又改走双栈结算。这种混合实现调试起来会变得非常像玄学不如一条路走到底。3.3 把“实验内容及要求”写进报告五个必写项标题里的“实验内容及要求”意味着报告不能只贴一段代码。老师判断实验做没做透看的不是你栈定义写得有多标准而是你有没有把输入输出边界说清楚。我一般按五个必写项组织输入约定、输出约定、数据结构定义、核心算法步骤、错误处理。每一项给一句能直接抄进报告的具体描述。输入约定写“支持数字、小数点、空格、四则运算符、^ 和括号负数必须加括号如 2*(-3)非法字符一律报错”输出约定写“结果按浮点数输出保留 6 位小数出错时输出 Error 和原因”。数据结构定义写清楚栈和队列各存什么类型核心算法步骤按“读入 → 词法扫描 → 转后缀 → 求值 → 输出”分条列。错误处理单独列一张表对应第 5 章的翻车点。这样写“实验内容及要求”这六个字才真正落了地。4. 字符流到 token词法扫描和负号预处理的三个关键步骤很多实现从“逐字符处理”开始结果死在多位数和负号上。表达式是一串字符必须先拆成有意义的 token再进入栈运算。这一步漏了后面所有逻辑都建立在错误输入上。4.1 tokenize 怎么写多位数、小数点和非法字符都在这一步挡掉def tokenize(expr): tokens [] i 0 while i len(expr): ch expr[i] if ch.isspace(): i 1 continue if ch.isdigit() or ch .: j i dots 0 while j len(expr) and (expr[j].isdigit() or expr[j] .): if expr[j] .: dots 1 if dots 1: raise ValueError(数字格式非法多个小数点) j 1 tokens.append((num, expr[i:j])) i j continue if ch in -*/^(): tokens.append((op, ch)) i 1 continue raise ValueError(f非法字符: {ch}) return tokens数字扫描的while循环是关键它把连续的“12”“3.14”合并成一个numtoken。dots变量统计小数点个数最多允许一个。如果不做这个合并后面会把 12 当成 1 和 2 两个操作数。空格在这里统一跳过所以输入“1 2”和“12”等价。非法字符在默认分支直接抛异常这比等到求值阶段才发现问题好得多。4.2 单目负号怎么处理补0预处理与输入约定负号有两个身份二元减法a-b以及一元取负-a。判断规则是看它前面的有效字符如果前面是空、运算符或左括号说明它是单目负号。最常见的省事做法是把它改成“0 减”把-3变成0-3。def normalize(expr): out [] prev None # 记录上一个有效字符用于判断单目负号 for ch in expr: if ch.isspace(): continue if ch -: # 表达式开头或前一个字符是运算符/左括号判定为单目负号 if prev is None or prev in -*/^(: out.append(0) out.append(ch) prev ch return .join(out)比如-32被标准化成0-32求值结果是 -1正确。2*(-3)变成2*(0-3)结果 -6也正确。要特别注意输入约定这种补 0 方案不支持2*-3这种省括号写法因为它会变成2*0-3结果就错了。所以实验报告的输入约定里应写明“负数必须写成括号形式如 2*(-3)”。如果要求支持无括号负号就需要在tokenize里引入一元运算符分支优先级和弹栈规则都不一样复杂度明显上升可以列为扩展内容而不是必做项。4.3 错误出口要统一不让求值器在栈空和除零时裸奔程序崩在奇怪的位置多半是错误处理没有统一出口。C 语言没有异常常见做法是定义一个错误码枚举每个函数返回状态码主流程统一判断打印Python 里则用自定义异常把词法错误、括号错误、算术错误、操作数错误分成几类。class ExpressionError(Exception): pass class LexError(ExpressionError): pass class ArithError(ExpressionError): pass主流程统一写成try: result eval_postfix(shunting_yard(tokenize(normalize(expr))) except ExpressionError as e: print(Error:, e)。这样所有错误都在一个出口变成可读信息不会出现除零后程序直接崩溃、或括号不匹配时返回一个没人看得懂的状态码。错误出口的统一也是实验报告里“程序健壮性”这一节最值得写的内容。5. 中缀求值实验的5个高频翻车点现象、原因与排查以下每条都是一线跑实验时真实遇到过的血泪经验按“现象 → 原因 → 解决”整理写报告时可以直接参考。5.1 优先级比较写成“”导致12*39现象代码逻辑看起来正确但12*3输出 9 而不是 7。原因新运算符入栈前只弹出栈顶优先级严格大于当前的运算符结果在遇到*时没被正确处理反而是先算加法。解决左结合运算符的比较条件必须是“栈顶优先级大于等于当前”右结合运算符如^才用“大于”。调试时用12*3、3-2-1两个用例一起卡后一个专门验证同优先级是否从左往右结算。5.2 减法和除法的操作数顺序颠倒现象5-3算出 -28/2算出 0.25。原因弹出两个操作数时先弹出的其实是右操作数后弹出的是左操作数代码却按“先弹出放左边”写了。解决先r stack.pop()再l stack.pop()计算l - r和l / r。这个小陷阱在栈求值里几乎人人都会踩一次写代码时把这两行注释写上比事后 debug 省时间。5.3 负号被当成减号-32 直接报错或算出5现象输入-32有的实现报“操作数不足”有的算出 5。原因开头的-被当成了二元减法但操作数栈里此时只有一个数字。解决用第 4.2 节的normalize预处理在表达式开头和左括号后补 0。同时明确输入约定要求负数写成(-3)或2*(-3)这类规范形式。碰到2*-3报错别怀疑是算法问题先看输入约定。5.4 多位数被逐字符拆散1234 算成 10现象输入1234结果输出 10。原因实现里直接遍历字符串的每个字符把1和2当成两个独立操作数压栈。解决必须走词法扫描连续数字和小数点合并成一个 token。排查技巧是把tokenize的返回值打印出来看一眼[(num,12),(op,),(num,34)]就是对的如果看到[(num,1),(num,2)...]问题定位在扫描循环而不是求值逻辑。5.5 括号不匹配、除零和非法字符裸奔三处缺口一个也不能少现象输入(12能算出 3输入1/0程序崩溃输入12报错信息莫名其妙。原因只在正确路径上写了算法错误路径全没兜。解决右括号弹栈前先查运算符栈是否为空为空就是多余的右括号扫描结束后检查运算符栈是否残留左括号有就是缺少右括号除法前判断分母绝对值是否接近 0tokenize默认分支直接抛非法字符异常。这四件事在“错误出口统一”里已经埋过伏笔这里算是正式验收清单。6. 用对拍和边界用例保住实验报告验证栈求值结果的三个动作写完代码只是第一步实验报告里的“测试结果”部分才是拉开差距的地方。手算三五个用例就交答辩时很容易被一个边界输入问倒。我的做法是两张牌一张边界用例表一个随机对拍脚本。6.1 一张用例表顶过十次口算把下面这张表放进实验报告的测试节老师一眼能看到你覆盖了正常、结合性、负号、错误路径几类场景。输入期望输出说明12*37基础优先级(12)*3-45括号改变优先级3-2-10左结合性2^3^2512右结合性-32-1单目负号12.53.5小数(12Error缺少右括号1/0Error除零这张表配合第 5 章基本覆盖了 90% 的实现漏洞。写报告时把实际输出也贴上去形成“输入-期望-实际-结论”四列比单独写一段“测试通过”有说服力得多。6.2 随机对拍生成一批表达式与解释器结果逐条比对手写用例测完后再跑一轮随机对拍。下面这段代码会生成一批简单的四则表达式用 Python 的eval结果作为参考值和自己写的求值器对比。import random def gen_expr(): ops [, -, *, /] n random.randint(2, 4) expr str(random.randint(1, 9)) for _ in range(n): expr random.choice(ops) str(random.randint(1, 9)) if random.random() 0.5: expr ( expr ) return expr def check(count200): for _ in range(count): s gen_expr() mine eval_postfix(shunting_yard(tokenize(normalize(s)))) ref eval(s) # 仅用于本地实验对拍别让线上环境调用 eval if abs(mine - ref) 1e-9: print(不匹配:, s, mine, ref) return print(all ok)这段脚本里gen_expr刻意不生成负号和幂运算因为那些是边界用例应该靠 6.1 的用例表去覆盖随机对拍负责查“常规输入下有没有低级错误”。1e-9的误差容忍度用于浮点比较避免0.10.2这类精度问题造成误报。最后说个自己的教训大二写这个实验时我只测了 12*3 和 (12)*3 就跑结果答辩老师让我手算 3-2-1我口算出 2代码却输出 0。从那天起只要是栈相关的实验我必先写左结合、右结合、负号和括号错误各一条用例再开始调主流程。这个习惯后来做单调栈相关题目和给表达式引擎补边界时帮我省了大量返工时间。希望帮到你。本文还有配套的精品资源点击获取