简介资源为“数据结构实验报告·栈与队列·中缀表达式求值”配套文档适合高校计算机专业学生完成数据结构课程实验或复习栈的应用。内容涵盖实验内容与要求、数据结构与算法设计、函数模块说明、程序测试及C语言源代码重点讲解运算符栈与操作数栈的协作、isp/icp优先级比较、括号与正负号处理、整数除法截断等实现细节。包内共1个docx文档约51KB便于直接查看和编辑。文档从基础要求到提高要求逐层展开既能帮助入门者掌握中缀表达式求值流程也为需要完成实验报告或代码设计的读者提供了完整参考。当前已有2899人浏览学习适合作为课程实验的参考资料也可用于复习栈与队列在表达式求值中的典型应用。1. 中缀表达式求值实验题目在考栈队列为什么也要出现在报告里中缀表达式求值几乎是每次数据结构实验必考的应用题这份以“栈与队列”为题的实验报告核心就一件事把23*(4-1)这样的中缀表达式用栈转换成后缀表达式再用栈求出结果。考的不是代码能不能跑而是你懂不懂栈的“先进后出”为什么恰好匹配运算符优先级以及队列在这个过程里到底能承担什么角色。适合正在写实验报告想拿高分的学生也适合想用一个晚上把这份实验彻底弄明白的自学者。下面按实验报告的完整结构把原理、代码、测试和踩坑一次讲透保证你能直接照着复现。2. 为什么中缀转后缀和求值都必须用栈从两个栈的设计说起2.1 手推 23*(4-1)看栈到底在压什么我一般不在报告开头直接贴代码先手推三组用例。中缀转后缀的经典算法叫调度场算法核心是两张优先级表isp栈内优先级和 icp栈外优先级。规则只有四条数字直接输出运算符 x 与栈顶 y 比较若 icp(x) 大于 isp(y)x 入栈否则弹出 y 并输出左括号直接入栈右括号把栈内运算符一直弹出直到遇到左括号。手推23*(4-1)数字 2 输出压栈3 输出*的 icp 是 4大于栈顶的 isp 3压栈左括号压栈4 输出-的 icp 是 2大于栈顶(的 isp 1压栈1 输出遇到右括号弹出-和(表达式读完依次弹出*和。最终后缀串是2 3 4 1 - * 。这里最关键的一点栈的先进后出正好承担了“运算符先压住等右操作数算完再出来”这件事。*比后进栈却比先出栈所以乘法先于加法执行括号内减法更先执行。这就是中缀转后缀必须用栈的根本理由——运算符的优先级结构本质上是一个嵌套括号结构天然匹配栈的后进先出。对照《大话数据结构》和考研资料里关于栈的章节中缀转后缀都被列为必背算法不是因为它难而是因为它把栈的“延迟输出”特性用到极致。2.2 优先级表的设计两个细节容易被扣分isp 和 icp 为什么要两套数值因为同一个运算符在栈内和栈外的优先级不同。以加减乘除为例栈外 icp 依次是 2、2、4、4栈内 isp 依次是 3、3、5、5。左括号栈外 icp 是 6栈内 isp 是 1右括号栈外 icp 是 1栈内 isp 是 6。这套设计保证了两个效果一是新来的运算符能压住栈里优先级更高或相等的运算符二是左括号进栈后括号内部的运算符依然能正常压栈右括号到达时又能把括号内所有运算符一次性弹出。如果只设一套优先级(12)*3就会出问题左括号进栈后的优先级如果小于等于栈顶永远压不进去括号内部的表达式直接算错。报告里这一张优先级表可以直接照抄但要在表下加一句说明#是栈底哨兵作用是让清栈操作有一个明确的终止条件。部分实验要求支持取模%它的优先级和乘除相同乘方^涉及右结合isp 和 icp 规则更复杂普通实验课不建议加加了反而要处理2^3^2到底是算(2^3)^2还是2^(3^2)的争议。运算符isp栈内icp栈外#00(16 -32* / %54)612.3 队列在表达式处理中的三个合理位置不硬凑才不会被老师盯上标题写的是“栈与队列”但经典中缀转后缀算法只显式使用栈。怎么让队列合理出现而不是硬凑功能我在实验报告里用过三个位置都站得住脚。第一输入缓冲。表达式从控制台读入后先按字符拆成一个环形队列转后缀程序每次从队头取一个字符。这样扫描器的结构是“FIFO 顺序消费”队列的先进先出和表达式从左到右的语义天然一致而且能顺手把空格过滤掉。第二后缀表达式缓冲。中缀转后缀的输出先入链队列求值器再依次出队消费。后缀串本来就是从左到右求值的用队列承载这个“待处理任务流”逻辑上没有违和感。第三只在概要设计里画出来。如果代码实在不想动可以在报告的概要设计模块单独列一个“输入队列”的数据结构图说明“若表达式长度固定环形队列比链队列更省空间”不写具体实现老师也不会深究。原则就一条报告里明确写队列承担的是“缓冲”或“顺序消费”不要写“用队列完成中缀表达式求值”否则答辩时被追问一句“队列先进先出怎么体现运算优先级”当场就会卡壳。常见做法是选输入缓冲或输出缓冲其中一个真正实现另一个在设计中画出即可代码和报告两头都稳。3. 按实验报告要求逐段拆解“实验内容”六个段落的完整写法3.1 需求分析与概要设计先写清楚输入输出再动手写代码实验报告第一部分是需求分析不要写空话。直接写输入是一个中缀表达式支持加减乘除和取模、括号、多位数、空格和小数点输出是转换后的后缀表达式以及最终计算结果程序对非法表达式要有错误返回不能直接崩溃。再补一句“操作数使用 double 类型避免整数除法截断”。概要设计里列两个数据结构算符栈char 类型数组栈和操作数栈double 类型数组栈。如果采纳了 2.3 的输入队列方案再加一个环形队列。这一节的流程图用 Word 自带的文本框画主流程四个框读入表达式、预处理、中缀转后缀、后缀求值最后输出结果。不要省略流程图很多报告的评分点就在这里。3.2 核心代码中缀转后缀模块可直接编译的版本下面这段代码对应报告“详细设计”部分可以直接放进 C 语言工程编译运行。栈结构用定长数组MAX 取 100实验课够用。优先级函数返回 int数字判断同时支持小数点。#include stdio.h #include stdlib.h #include string.h #define MAX 100 /* 字符栈用于存运算符 */ typedef struct { char data[MAX]; int top; } CharStack; void InitStack(CharStack *s) { s-top -1; } int Push(CharStack *s, char c) { if (s-top MAX - 1) return 0; s-data[s-top] c; return 1; } int Pop(CharStack *s, char *c) { if (s-top -1) return 0; *c s-data[s-top--]; return 1; } int GetTop(CharStack *s, char *c) { if (s-top -1) return 0; *c s-data[s-top]; return 1; } /* isp栈内优先级icp栈外优先级 */ int isp(char op) { switch (op) { case #: return 0; case (: return 1; case : case -: return 3; case *: case /: case %: return 5; case ): return 6; default: return 0; } } int icp(char op) { switch (op) { case #: return 0; case (: return 6; case : case -: return 2; case *: case /: case %: return 4; case ): return 1; default: return 0; } } /* 数字判断支持小数点便于处理 12.5 这类操作数 */ int IsDigit(char c) { return (c 0 c 9) || c .; } /* 中缀转后缀结果写入 postfix操作数和运算符之间用空格分隔 */ void InfixToPostfix(const char *infix, char *postfix) { CharStack op; InitStack(op); Push(op, #); /* 栈底哨兵 */ int i 0, j 0; char c, top; while ((c infix[i]) ! \0) { if (c ) { /* 过滤输入中的空格 */ i; continue; } if (IsDigit(c)) { /* 连续读取一个完整数字 */ while (IsDigit(infix[i])) postfix[j] infix[i]; postfix[j] ; /* 数字之间必须有分隔符 */ } else { GetTop(op, top); if (icp(c) isp(top)) { /* 新运算符优先级高入栈 */ Push(op, c); i; } else if (icp(c) isp(top)) { /* 左右括号相遇弹出左括号 */ Pop(op, top); i; } else { /* 栈顶运算符优先级更高弹出 */ Pop(op, top); postfix[j] top; postfix[j] ; } } } while (Pop(op, top) top ! #) { /* 清空剩余运算符 */ postfix[j] top; postfix[j] ; } postfix[j] \0; }这段代码的逻辑可以拆成三点说明。第一postfix[j] 这句不能省后缀表达式里数字和运算符全靠空格分隔否则123转出来会变成123求值阶段完全无法还原操作数边界。第二icp(c) isp(top)是入栈条件icp(c) isp(top)只用于左右括号相遇普通运算符不会出现相等的情况这是优先级表设计决定的。第三函数结束后必须有一个单独的 while 循环清空算符栈很多人把清栈逻辑写在主循环里最后一位运算符就会神秘失踪后面避坑章会专门讲。3.3 核心代码后缀求值模块与主流程后缀求值用另一个独立栈存 double 类型。注意弹出顺序先弹出的是右操作数 b再弹出的是左操作数 a除法必须写成a / b很多初学者写成b / a结果整个表达式反了。除零用 ok 标记拦截不让程序直接崩溃。/* 数字栈用于后缀表达式求值 */ typedef struct { double data[MAX]; int top; } NumStack; void InitNumStack(NumStack *s) { s-top -1; } int PushNum(NumStack *s, double v) { if (s-top MAX - 1) return 0; s-data[s-top] v; return 1; } int PopNum(NumStack *s, double *v) { if (s-top -1) return 0; *v s-data[s-top--]; return 1; } /* 二元运算封装除零场景通过 ok 返回 0 表达错误 */ double Calc(double a, double b, char op, int *ok) { *ok 1; switch (op) { case : return a b; case -: return a - b; case *: return a * b; case /: if (b 0) { *ok 0; return 0; } return a / b; case %: if ((int)b 0) { *ok 0; return 0; } return (int)a % (int)b; default: *ok 0; return 0; } } /* 后缀表达式求值返回 1 表示成功0 表示表达式非法 */ int EvalPostfix(const char *postfix, double *result) { NumStack st; InitNumStack(st); int i 0; char c; while ((c postfix[i]) ! \0) { if (c ) { i; continue; } if (IsDigit(c)) { char token[32]; int k 0; while (IsDigit(postfix[i]) postfix[i] ! \0) token[k] postfix[i]; token[k] \0; PushNum(st, atof(token)); /* atof 解析整数和小数 */ } else { double a, b; if (!PopNum(st, b)) return 0; /* 操作数不足 */ if (!PopNum(st, a)) return 0; int ok; double v Calc(a, b, c, ok); if (!ok) return 0; PushNum(st, v); } } if (PopNum(st, result) st.top -1) return 1; /* 栈里只剩一个值才算合法 */ return 0; } int main() { char infix[128], postfix[256]; double result; printf(输入中缀表达式: ); fgets(infix, sizeof(infix), stdin); infix[strcspn(infix, \n)] \0; /* 去掉 fgets 留下的换行符 */ InfixToPostfix(infix, postfix); printf(后缀表达式: %s\n, postfix); if (EvalPostfix(postfix, result)) printf(计算结果: %.4f\n, result); else printf(表达式非法\n); return 0; }EvalPostfix 最后有个容易被忽略的校验PopNum(st, result) st.top -1。这行要求表达式结束后操作数栈里只能剩一个结果。如果输入(12这种左括号不匹配的表达式转后缀阶段会留下未处理的左括号或者操作数栈里残留多余数字这里能直接拦下来。main 函数里用 fgets 代替 gets再用strcspn去掉换行符很多教材还停留在 gets 的写法那是 C11 已经移除的不安全函数实验报告里用了会被扣印象分。3.4 调试分析与复杂度报告里必须写的那两段话调试分析这一节老师会重点看“遇到的问题”不要只写“没有遇到问题”。把第 5 章里的任意一条踩坑记录搬过来就是现成的素材比如 fgets 读入表达式会在末尾留换行符如果不截断转后缀阶段会把\n当成一个优先级为 0 的运算符导致栈底#被错误弹出表现为“合法表达式也报非法”。写清楚现象、原因、解决办法这一节就充实了。复杂度分析写给两行中缀转后缀对表达式做一次线性扫描时间复杂度 O(n)n 为表达式字符数后缀求值同样对后缀串做一次线性扫描时间复杂度 O(n)两个栈的总空间不超过表达式长度空间复杂度 O(n)。报告里最好再加上一句“空格过滤和合法性校验都在一次扫描内完成不额外增加复杂度”。这句话虽然短但能明显拉高分。4. 测试用例设计让中缀表达式求值在边界上不翻车4.1 测试用例表覆盖多位数、空格、嵌套括号和负数实验报告的测试结果部分最忌只截图一个“运行成功”。测试用例必须覆盖优先级、括号、多位数、空格、除零、非法输入这几类场景每一条都要写出“输入、期望输出、实际输出、覆盖点”。下面这张表可以直接抄进报告最后一列写清楚这个用例在测什么答辩时老师问到任何一行都能答上。输入表达式期望输出实际输出覆盖点23*41414乘法优先级高于加法(23)*42020括号提升优先级10/42.52.5浮点除法不是整数整除12*3-4/255同级运算符从左到右结合((12))33连续嵌套括号7 81515空格过滤12.5 0.51313多位数与小数3/0除零错误表达式非法除零拦截(12非法表达式非法括号不匹配表格里第 8 行要注意基础版本的代码里除零和语法错误统一返回 0main 里都打印“表达式非法”。如果想让测试报告更严谨可以给 EvalPostfix 增加一个错误码参数用 0 表示语法错误、-1 表示除零错误main 里按错误码分别打印。这一点在答辩时属于加分项后面 5.2 会展开说。负数怎么测基础版本里把-35写成(0-3)5就能绕开单目运算符。如果实验要求比较高要支持直接输入-35需要按 5.3 的方法做单目负号扩展扩展完再补一组测试用例。报告里如果写了扩展测试表里一定要有对应行否则老师一眼看出测试和代码对不上。4.2 表达式合法性校验五个崩溃前的拦截规则合法性校验不需要单独再扫描一遍表达式在转后缀和求值的过程中顺带完成省一次 O(n)。五个规则按顺序写进代码里空串直接报非法左括号不匹配由转后缀结束后栈里残留(暴露连续运算符如12会因为第二次扫描到时栈内没有足够的操作数而求值失败右括号多余会被icp(c) isp(top)分支触发等于号为#时 Pop 失败除零在 Calc 里拦截。我一般会把第一个字符是*或/这种场景也归为连续运算符同一类因为它们本质都是“运算符出现在不该出现的位置”。这五个规则不需要每种都写独立 if很多是算法天然的行为。比如12转后缀能成功但求值阶段第二个弹不出两个操作数返回 0。报告里写测试用例时把这五类输入都跑一遍一一对应“表达式非法”的输出就足够说明程序的健壮性了。5. 中缀表达式求值避坑五个最容易让实验报告重写的踩坑记录5.1 现象表达式末尾的运算符神秘失踪输入12*3期望后缀1 2 3 * 实际输出却是1 2 3 *加号丢了。第一次遇到这个问题的人很容易怀疑是优先级表写错其实是转后缀主循环结束后没有把算符栈里剩余的运算符全部弹出来。很多人把清栈逻辑写在循环体的某个分支里遇到数字分支直接 continue清栈语句被跳过或者把清栈写在 while 外面但写成了只弹一次。解决方法是单独写一个循环while (Pop(op, top) top ! #)把所有非#运算符依次输出。这句话必须在主循环结束后无条件执行一次不能放在任何分支里。排查时最快的方法是在清栈循环前加一行 printf 打印栈顶看栈里到底还剩什么。5.2 现象除零错误让整份报告现场翻车输入3/0程序要么直接崩溃退出要么输出一个巨大的负数。C 语言里整数除零会触发 SIGFPE 信号浮点除零会得到 inf都不是正常结果。很多初学者只在主函数里检查表达式是否合法压根没想到要在 Calc 层面对除法单独拦截。解决Calc 函数的case /分支里判断if (b 0)置 ok 为 0 并返回。如果要区分错误类型把 EvalPostfix 的返回类型从 int 改成带错误码的结构体或者传一个int *err进去0 表示语法错误-1 表示除零错误。报告测试部分的截图里如果能分别看到“表达式非法”和“除数不能为零”两种输出这份报告的测试严谨度就直接拉开差距了。5.3 现象单目负号被当成双目减号输入-35程序把开头的-当成减号遇到右操作数时弹出栈里不存在的数字直接报表达式非法。这是中缀转后缀算法最经典的坑几乎所有初学者都会踩一次。解决思路扫描时判断当前-的前一个字符如果表达式开头或者前一个字符是运算符或左括号则当前-是单目负号而不是双目减号。常见做法是把它压入一个特殊标记比如后缀求值时遇到只弹出一个操作数取负。如果时间紧张基础版本完全可以在需求分析里写明“负数请以 (0-负值) 形式输入”这在实验课上是允许的。但你要是选择了扩展记得把测试用例表补上-35这一行代码和报告保持一致。5.4 现象符号栈和数栈共用一个结构体有的同学为了省事用一个typedef struct { int data[MAX]; } Stack同时存运算符和操作数结果转后缀阶段正常一到求值阶段拿到乱码。原因是 double 类型被 int 数组截断了12.5 存进去变成 12小数位全部丢失而且字符和数字共用同一个栈会让栈顶判断彻底混乱。解决定义两个结构体CharStack 存 charNumStack 存 double代码量多不了几行但可读性和正确性都远好于一个通用栈。实验报告级别不需要引入 union 或者 void* 这类技巧那是给代码库设计用的不是给实验作业用的。两个结构体最大的好处是答辩时一句话就能说清设计意图运算符栈和操作数栈类型不同生命周期也不同必须分开。5.5 现象报告只贴代码不贴测试过程报告里放一大段源码测试结果只写“运行成功”没有任何输入输出截图和用例表格。这是实验报告评分最可惜的一种翻车代码明明写对了但因为测试部分太空老师无法判断你是真跑通了还是从网上抄的。答辩时老师现场换一组输入比如(23)*4你在那里盯着控制台敲了半天场面会非常尴尬。解决测试部分必须给表格每一行写明“输入、期望输出、实际输出、覆盖点”把错误用例也放进去说明你的程序对非法输入有明确响应。截图可以是三张一张正常表达式、一张多位数小数、一张除零错误。这三张就能覆盖大部分评分点也足够证明代码不是黑匣子。6. 从实验报告到答辩中缀表达式求值还能往哪里问6.1 双栈直接求值不生成后缀串的另一种实现如果老师追问“能不能不转后缀直接求值”答案是双栈法操作数栈存数字运算符栈存运算符数字直接压数栈运算符压栈前先把栈里优先级更高或相等的运算符全部取出计算遇到右括号计算到左括号。核心依然是栈只是少了对后缀串的中间输出。这个方案和中缀转后缀本质是同一个算法只是把输出后缀的动作换成了立即求值答辩时能说出这层关系说明你理解了原理。6.2 表达式树与层次遍历队列的第二个天然角色把后缀表达式建成表达式树操作数建叶子节点入栈运算符弹出两棵子树作为左右孩子新树再入栈。最后对表达式树做层次遍历这时候队列就不再是“缓冲”角色而是真正的算法本体——从根节点开始逐层从左到右输出。如果实验报告还有“思考与展望”一栏这一段写进去非常加分因为它同时用到了栈和队列和标题完美对应。6.3 答辩被追问时的三句话准备被问“为什么不用递归求值”回答递归本质也是栈表达式树和后缀表达式用递归会有一层函数调用开销显式栈在中缀转后缀场景更直观可控。被问“栈空间不够怎么办”回答定长数组栈可以改成链栈用动态内存分配代价是每次入栈要 malloc慢一些但不会溢出。被问“怎么证明计算结果是对”的回答转后缀后先把后缀串打印出来手工按后缀规则演算一遍再对照结果这是最笨也最可靠的方法。我当年第一次交这份实验报告时只贴了一段完整代码就交上去了结果答辩老师让我现场跑(23)*4我盯着控制台愣了几秒才意识到自己压根没准备测试数据。后来我养成了一个习惯任何栈和队列的实验动手写代码之前先在草稿纸上把三组用例手推完再对照程序输出最后才落笔写报告。这个习惯帮我躲过了很多次翻车现场也会让你这份中缀表达式求值实验报告不用再交第二遍。希望帮到你。本文还有配套的精品资源点击获取