简介这份《数据结构表达式求值实验报告》面向计算机专业学生与数据结构初学者聚焦栈在算术表达式求值中的经典应用帮助读者完成课程设计并理解算符优先算法的实现思路。资源包共1个doc文档约122KB内容为完整的课程设计报告书涵盖前言、概要设计、详细设计、软件测试与总结等章节。报告详细讲解运算符栈OPTR与操作数栈OPND的双栈设计给出顺序栈的存储结构、ADT描述、功能模块划分以及Precede优先级比较、Operate运算、EvalExpr求值等核心函数的实现与算符优先关系表。读者可据此掌握从字符串输入到结果输出的完整求值流程理解括号匹配与多位数处理的细节并参考测试用例与排错思路完善自己的代码。目前已有461人学习适合需要课程设计模板或想深入理解栈应用的读者参考。1. 表达式求值实验报告到底在考什么从一份 .doc 说起很多人拿到「数据结构表达式求值实验报告.doc」这个题目第一反应是去搜一份现成的 Word 模板把学号姓名一填就交。但真正做过这道题的人都知道表达式求值这个实验是数据结构课程里少数几个「代码写不对就完全跑不起来」的硬骨头。它不像链表插入删除那样改改指针就能过也不像排序算法那样换个比较函数就行——它要求你同时把栈、优先级、括号匹配、多位数解析、负数处理这几件事一次性想清楚任何一环出问题输入32*6-2都可能给你返回13而不是16。这份实验报告的核心是让你用栈实现一个算术表达式求值器。常见做法是「双栈法」一个栈存操作数一个栈存运算符从左到右扫描表达式遇到数字压数栈遇到运算符就比较优先级决定是压栈还是弹出计算。听起来简单但真正动手写的时候中缀转后缀、括号嵌套、除零判断、多位数拼接这些细节会一个接一个冒出来。适合正在做数据结构实验的本科生、准备 408 考研想手写代码的考生以及想用 C/C/Java 把栈这个结构真正用起来的人。下面我按自己踩过的路把这份实验从原理到代码到报告写法拆开讲。2. 双栈法求值的原理与手写推演为什么优先级表是核心2.1 中缀表达式为什么不能直接从左往右算人脑算32*6-2会下意识先算2*6因为你知道乘法优先级高于加法。但计算机从左到右扫描时读到的那一刻它并不知道后面有没有更高优先级的运算符。如果直接算325后面再遇到*6就全错了。所以必须引入一个「暂存」机制把暂时不能确定的运算符先存起来等确定后面没有更高优先级时再回头计算。这个暂存结构就是栈。双栈法的本质是数栈存还没参与运算的数字符栈存还没确定执行顺序的运算符。扫描过程中每当遇到一个新运算符就拿它和符栈顶的运算符比优先级。如果栈顶优先级更高或相等说明栈顶那个运算符可以先算于是弹出栈顶运算符、弹出两个数、算出结果压回数栈然后继续拿新运算符和新的栈顶比。如果新运算符优先级更高或者栈是空的或者栈顶是左括号就直接把新运算符压入符栈。这个过程一直持续到表达式扫描完最后把符栈里剩下的运算符依次弹出算完数栈里剩下的那个数就是结果。这个逻辑用一句话概括栈顶运算符优先级 ≥ 新运算符优先级时先算栈顶否则新运算符入栈。括号的处理是遇到左括号直接入符栈遇到右括号就不断弹出运算符计算直到弹出左括号为止。左括号在栈内时优先级最低保证它不会被新运算符「比下去」而提前弹出。2.2 优先级表怎么设计才不出错优先级表是双栈法的核心配置设计错了整个求值就崩。我一般用两个数组或者一个二维表来表示。常见做法是给每个运算符一个入栈优先级栈外优先级和一个栈内优先级。为什么要分两个因为左括号在栈外时优先级最高保证它能压进去在栈内时优先级最低保证它不会被其他运算符弹出来。下面这张表是我在 C 语言实现里常用的配置运算符栈外优先级入栈前比较用栈内优先级栈顶比较用33-33*55/55(61)11#00这里的#是表达式结束标志用来处理扫描结束后的收尾。注意左括号的栈外优先级是 6比乘除的 5 还高这样它才能顺利入栈而栈内优先级是 1比加减的 3 还低这样当新运算符进来时栈顶的左括号不会把它弹出去。右括号的优先级设为 1遇到它时直接触发「弹出直到左括号」的逻辑不参与常规比较。提示很多同学把左右括号的优先级设成一样结果遇到(32)*6时右括号会把左括号也弹出来算掉导致括号丢失。左括号栈内优先级必须低于所有真实运算符。2.3 手写推演一遍32*6-2的完整过程光看表不够我带你走一遍完整流程这样写代码时心里有数。初始化数栈和符栈都为空符栈先压入#作为哨兵。扫描到3是数字压入数栈。数栈[3]符栈[#]。扫描到和符栈顶#比#栈内优先级 0栈外优先级 33 0所以入符栈。数栈[3]符栈[#, ]。扫描到2压入数栈。数栈[3, 2]符栈[#, ]。扫描到*和符栈顶比栈内优先级 3*栈外优先级 55 3所以*入符栈。数栈[3, 2]符栈[#, , *]。扫描到6压入数栈。数栈[3, 2, 6]符栈[#, , *]。扫描到-和符栈顶*比*栈内优先级 5-栈外优先级 33 5所以弹出*计算。弹出数栈顶两个数 6 和 2算2*612压回数栈。数栈变成[3, 12]符栈[#, ]。继续拿-和新的栈顶比栈内优先级 3-栈外优先级 33 ≥ 3所以弹出计算。弹出 12 和 3算31215压回数栈。数栈[15]符栈[#]。再拿-和#比0 3所以-入符栈。数栈[15]符栈[#, -]。扫描到2压入数栈。数栈[15, 2]符栈[#, -]。表达式扫描完开始收尾弹出符栈顶-弹出 2 和 15算15-213压回数栈。数栈[13]符栈[#]。#不参与计算结束。结果 13。等等32*6-2按正常优先级应该是312-213没错。但如果你把*和优先级搞反结果就会变成(32)*6-228这就是优先级表设计错误的典型翻车现场。3. 用 C 语言把双栈求值器跑通完整代码与逐段拆解3.1 栈结构定义与基础操作先定义两个栈。为了代码清晰我用结构体封装数栈存double类型兼容除法小数符栈存char。栈的大小根据表达式长度动态分配或者给一个足够大的固定值实验里一般 100 够用。#include stdio.h #include stdlib.h #include ctype.h #include string.h #define MAXSIZE 100 // 数栈存操作数 typedef struct { double data[MAXSIZE]; int top; } NumStack; // 符栈存运算符 typedef struct { char data[MAXSIZE]; int top; } OpStack; void initNumStack(NumStack *s) { s-top -1; } void initOpStack(OpStack *s) { s-top -1; } int isNumEmpty(NumStack *s) { return s-top -1; } int isOpEmpty(OpStack *s) { return s-top -1; } void pushNum(NumStack *s, double v) { if (s-top MAXSIZE - 1) { printf(数栈溢出\n); exit(1); } s-data[(s-top)] v; } double popNum(NumStack *s) { if (isNumEmpty(s)) { printf(数栈为空表达式有误\n); exit(1); } return s-data[(s-top)--]; } double peekNum(NumStack *s) { if (isNumEmpty(s)) { printf(数栈为空\n); exit(1); } return s-data[s-top]; } void pushOp(OpStack *s, char op) { if (s-top MAXSIZE - 1) { printf(符栈溢出\n); exit(1); } s-data[(s-top)] op; } char popOp(OpStack *s) { if (isOpEmpty(s)) { printf(符栈为空\n); exit(1); } return s-data[(s-top)--]; } char peekOp(OpStack *s) { if (isOpEmpty(s)) { printf(符栈为空\n); exit(1); } return s-data[s-top]; }这段代码没什么玄学就是标准的顺序栈。注意popNum和popOp里加了空栈判断因为表达式写错时比如32会触发连续弹栈没有保护程序直接崩。peekNum和peekOp在求值主逻辑里用来查看栈顶但不弹出比如判断符栈顶是不是左括号。3.2 优先级比较函数与计算函数优先级函数返回栈内和栈外两个值。我一般写一个函数getPriority(char op, int inStack)inStack为 1 时返回栈内优先级为 0 时返回栈外优先级。// 返回运算符优先级inStack1 表示栈内0 表示栈外 int getPriority(char op, int inStack) { switch (op) { case : case -: return 3; case *: case /: return 5; case (: return inStack ? 1 : 6; case ): return 1; case #: return 0; default: return -1; } } // 执行一次二元运算 double calc(double a, char op, double b) { switch (op) { case : return a b; case -: return a - b; case *: return a * b; case /: if (b 0) { printf(除零错误\n); exit(1); } return a / b; default: printf(未知运算符 %c\n, op); exit(1); } }calc里对除零做了判断这是实验报告里容易被忽略但老师一定会看的点。另外注意参数顺序a是左操作数b是右操作数弹栈时先弹出的是右操作数别搞反了否则减法和除法结果全错。3.3 主求值循环扫描、比较、计算、收尾主函数负责扫描字符串、拼接多位数、处理括号和收尾。多位数处理是新手最容易翻车的地方12345不能把1、2、3当成三个数分别压栈必须拼成一个整数。double evaluate(char *expr) { NumStack numStk; OpStack opStk; initNumStack(numStk); initOpStack(opStk); pushOp(opStk, #); // 哨兵 int i 0; while (expr[i] ! \0) { // 跳过空格 if (expr[i] ) { i; continue; } // 数字拼接多位数 if (isdigit(expr[i]) || expr[i] .) { double num 0; int hasDot 0; double factor 0.1; while (isdigit(expr[i]) || expr[i] .) { if (expr[i] .) { hasDot 1; i; continue; } if (!hasDot) { num num * 10 (expr[i] - 0); } else { num (expr[i] - 0) * factor; factor * 0.1; } i; } pushNum(numStk, num); continue; } // 运算符 char op expr[i]; if (op () { pushOp(opStk, op); i; continue; } if (op )) { // 弹出运算符直到左括号 while (peekOp(opStk) ! () { char topOp popOp(opStk); double b popNum(numStk); double a popNum(numStk); pushNum(numStk, calc(a, topOp, b)); } popOp(opStk); // 弹出左括号 i; continue; } // 常规运算符比较优先级 while (getPriority(peekOp(opStk), 1) getPriority(op, 0)) { char topOp popOp(opStk); double b popNum(numStk); double a popNum(numStk); pushNum(numStk, calc(a, topOp, b)); } pushOp(opStk, op); i; } // 收尾弹出剩余运算符 while (peekOp(opStk) ! #) { char topOp popOp(opStk); double b popNum(numStk); double a popNum(numStk); pushNum(numStk, calc(a, topOp, b)); } return popNum(numStk); } int main() { char expr[200]; printf(请输入表达式); scanf(%s, expr); double result evaluate(expr); printf(结果%g\n, result); return 0; }主循环的逻辑分四块跳空格、拼数字、处理括号、处理常规运算符。数字拼接里我加了小数点支持这样3.14*2也能算。括号处理里遇到右括号就不断弹运算符计算直到栈顶是左括号然后把左括号弹掉。常规运算符处理里while循环条件是栈顶优先级 ≥ 当前运算符优先级注意这里用的是而不是因为同级运算符要从左往右算比如10-3-2必须先算10-3再减2如果只用同级运算符会一直压栈最后变成10-(3-2)9结果就错了。收尾阶段用#作为终止标志不断弹出运算符计算直到符栈只剩#。最后数栈里剩下的就是结果。注意scanf(%s, expr)遇到空格会截断如果表达式里有空格用fgets替代。实验里一般输入不带空格但报告里可以提一句这个边界。3.4 测试用例与预期结果写完代码别急着交至少跑这几组用例输入表达式预期结果考察点32*6-213基本优先级(32)*630括号改变优先级10-3-25同级从左往右100/5/210除法同级顺序2*(34)-59混合嵌套8/0报错除零处理如果10-3-2算出 9说明优先级比较用了而不是。如果(32)*6算出 13 或者报错说明左括号栈内优先级设高了。这些用例覆盖了双栈法最常见的坑跑通基本就没大问题。4. 实验报告怎么写才不被扣分结构、截图与复杂度分析4.1 报告里必须出现的几个模块「数据结构表达式求值实验报告.doc」这个文件名本身就暗示了交付物是一份 Word 文档。老师看报告的时间通常不超过三分钟所以结构清晰比文采重要。我见过的得分比较稳的报告一般包含这几块实验目的、实验环境、算法思路、核心代码、测试结果、复杂度分析、心得体会。其中算法思路和测试结果是重点代码不用全贴贴关键函数就行。实验目的别写空话写具体「掌握栈的先进后出特性在表达式求值中的应用理解运算符优先级与括号匹配的处理逻辑」。实验环境写清楚编译器和系统比如Dev-C 5.11 / Windows 10或者gcc 9.4 / Ubuntu 20.04。算法思路用文字加流程图描述双栈法的扫描过程流程图用 Word 自带的形状画别贴代码截图。4.2 测试截图怎么截才有说服力测试结果部分每一条用例都要有输入和输出的截图。截图要包含控制台窗口的标题栏或者命令行提示符证明是你自己跑出来的不是从网上抄的。输入32*6-2输出13输入(32)*6输出30输入8/0输出除零错误提示。截图下面配一行说明「测试用例 1验证乘法优先级高于加法结果正确」。如果老师要求对比不同实现可以加一组「中缀转后缀再求值」的结果做对照但那是加分项不是必须的。核心还是把双栈法讲透。4.3 复杂度分析与心得体会的写法复杂度分析写两句话就够时间复杂度 O(n)因为每个字符最多入栈出栈各一次空间复杂度 O(n)两个栈的深度与表达式长度成正比。别展开成数学证明老师不看。心得体会是唯一可以写「人话」的地方。可以写你调试时遇到的真实问题比如「一开始忘了处理多位数输入 123 算出来 6后来加了数字拼接循环才正确」。这种具体踩坑比「通过本次实验我深刻理解了栈的应用」强一百倍。但注意别写成流水账挑一两个有代表性的问题写清楚现象、原因、解决就行。5. 避坑与排查双栈求值最容易翻车的 5 个地方5.1 多位数被拆成单个数字现象输入123结果是6而不是15。原因扫描时把1和2当成两个独立的数分别压栈了。解决在数字处理分支里加一个while循环连续读取数字字符并拼成整数遇到非数字字符才停止。如果支持小数还要处理小数点。5.2 同级运算符顺序算反现象输入10-3-2结果是9而不是5。原因优先级比较用了而不是导致同级运算符没有及时弹出计算最后变成从右往左结合。解决把比较条件改成getPriority(栈顶, 1) getPriority(当前, 0)保证同级从左往右。5.3 括号匹配失败或左括号提前弹出现象输入(32)*6结果报错或者算出13。原因左括号的栈内优先级设得和栈外一样高导致新运算符进来时把左括号弹出去计算了。解决左括号栈外优先级设为最高比如 6栈内优先级设为最低比如 1这样它入栈时畅通无阻在栈内时又不会被误弹。5.4 除零没有判断导致程序崩溃现象输入8/0程序直接闪退或者输出inf。原因calc函数里没有对除数为零做检查。解决在除法分支里加if (b 0)判断输出错误提示并退出。实验报告里加上这个判断是加分项说明你考虑了边界情况。5.5 表达式扫描完后忘记收尾现象输入32*6-2结果只算了部分输出15或者3。原因主循环结束后符栈里还有运算符没弹出计算数栈里也不止一个数。解决扫描结束后加一个while循环不断弹出符栈顶运算符并计算直到符栈只剩哨兵#。收尾逻辑和常规运算符处理里的弹栈计算完全一样可以直接复用。6. 从实验到实战把求值器扩展成支持变量和函数的计算器实验报告交完这套双栈法其实还能继续用。我带学生做课程设计时常见的进阶方向是把它扩展成一个支持变量和简单函数的计算器。核心改动不大但能让你对栈的理解再深一层。第一个扩展是变量支持。在数栈之外再加一个符号表用数组或者哈希表存变量名和值。扫描到字母时先读取完整标识符然后去符号表里查值压入数栈。如果是赋值语句x35就在等号右边算完后把结果写回符号表。这里要注意标识符的读取和数字读取类似都是连续字符拼接但变量名可能包含字母、数字、下划线判断条件用isalnum加下划线。第二个扩展是函数支持。比如sin(30)、max(3,5)。处理方式是在符栈里增加函数名标记遇到函数名时压入符栈遇到左括号正常处理遇到右括号时如果栈顶是函数名就弹出来执行对应函数。函数参数用逗号分隔需要在符栈里额外处理逗号遇到逗号就弹出运算符计算直到遇到左括号。这部分逻辑比基础求值复杂不少但本质还是栈的弹出和压入只是多了一层参数个数的判断。第三个扩展是错误恢复。基础版本遇到错误直接exit(1)实际计算器不能这样。可以把exit换成返回错误码主循环里检查错误码并提示用户重新输入。比如除零返回-1括号不匹配返回-2未知字符返回-3。这样程序不会一错就退体验好很多。我自己的习惯是每加一个功能就先写三组测试用例跑通了再往下加。变量支持测x5然后x*2函数支持测max(3,5)和sin(0)错误恢复测1/0和(12。这样一步步来不会一次改太多导致调不动。最后说个血泪经验表达式求值这个实验代码写完之后一定要用纸笔手动推演一遍32*6-2的栈变化过程把每一步的栈内容画出来。我当年就是靠这个笨办法发现优先级比较写反了否则盯着代码看半天也看不出问题。希望帮到你。本文还有配套的精品资源点击获取 数据结构表达式求值实验报告：双栈法原理、C语言实现与避坑指南
简介这份《数据结构表达式求值实验报告》面向计算机专业学生与数据结构初学者聚焦栈在算术表达式求值中的经典应用帮助读者完成课程设计并理解算符优先算法的实现思路。资源包共1个doc文档约122KB内容为完整的课程设计报告书涵盖前言、概要设计、详细设计、软件测试与总结等章节。报告详细讲解运算符栈OPTR与操作数栈OPND的双栈设计给出顺序栈的存储结构、ADT描述、功能模块划分以及Precede优先级比较、Operate运算、EvalExpr求值等核心函数的实现与算符优先关系表。读者可据此掌握从字符串输入到结果输出的完整求值流程理解括号匹配与多位数处理的细节并参考测试用例与排错思路完善自己的代码。目前已有461人学习适合需要课程设计模板或想深入理解栈应用的读者参考。1. 表达式求值实验报告到底在考什么从一份 .doc 说起很多人拿到「数据结构表达式求值实验报告.doc」这个题目第一反应是去搜一份现成的 Word 模板把学号姓名一填就交。但真正做过这道题的人都知道表达式求值这个实验是数据结构课程里少数几个「代码写不对就完全跑不起来」的硬骨头。它不像链表插入删除那样改改指针就能过也不像排序算法那样换个比较函数就行——它要求你同时把栈、优先级、括号匹配、多位数解析、负数处理这几件事一次性想清楚任何一环出问题输入32*6-2都可能给你返回13而不是16。这份实验报告的核心是让你用栈实现一个算术表达式求值器。常见做法是「双栈法」一个栈存操作数一个栈存运算符从左到右扫描表达式遇到数字压数栈遇到运算符就比较优先级决定是压栈还是弹出计算。听起来简单但真正动手写的时候中缀转后缀、括号嵌套、除零判断、多位数拼接这些细节会一个接一个冒出来。适合正在做数据结构实验的本科生、准备 408 考研想手写代码的考生以及想用 C/C/Java 把栈这个结构真正用起来的人。下面我按自己踩过的路把这份实验从原理到代码到报告写法拆开讲。2. 双栈法求值的原理与手写推演为什么优先级表是核心2.1 中缀表达式为什么不能直接从左往右算人脑算32*6-2会下意识先算2*6因为你知道乘法优先级高于加法。但计算机从左到右扫描时读到的那一刻它并不知道后面有没有更高优先级的运算符。如果直接算325后面再遇到*6就全错了。所以必须引入一个「暂存」机制把暂时不能确定的运算符先存起来等确定后面没有更高优先级时再回头计算。这个暂存结构就是栈。双栈法的本质是数栈存还没参与运算的数字符栈存还没确定执行顺序的运算符。扫描过程中每当遇到一个新运算符就拿它和符栈顶的运算符比优先级。如果栈顶优先级更高或相等说明栈顶那个运算符可以先算于是弹出栈顶运算符、弹出两个数、算出结果压回数栈然后继续拿新运算符和新的栈顶比。如果新运算符优先级更高或者栈是空的或者栈顶是左括号就直接把新运算符压入符栈。这个过程一直持续到表达式扫描完最后把符栈里剩下的运算符依次弹出算完数栈里剩下的那个数就是结果。这个逻辑用一句话概括栈顶运算符优先级 ≥ 新运算符优先级时先算栈顶否则新运算符入栈。括号的处理是遇到左括号直接入符栈遇到右括号就不断弹出运算符计算直到弹出左括号为止。左括号在栈内时优先级最低保证它不会被新运算符「比下去」而提前弹出。2.2 优先级表怎么设计才不出错优先级表是双栈法的核心配置设计错了整个求值就崩。我一般用两个数组或者一个二维表来表示。常见做法是给每个运算符一个入栈优先级栈外优先级和一个栈内优先级。为什么要分两个因为左括号在栈外时优先级最高保证它能压进去在栈内时优先级最低保证它不会被其他运算符弹出来。下面这张表是我在 C 语言实现里常用的配置运算符栈外优先级入栈前比较用栈内优先级栈顶比较用33-33*55/55(61)11#00这里的#是表达式结束标志用来处理扫描结束后的收尾。注意左括号的栈外优先级是 6比乘除的 5 还高这样它才能顺利入栈而栈内优先级是 1比加减的 3 还低这样当新运算符进来时栈顶的左括号不会把它弹出去。右括号的优先级设为 1遇到它时直接触发「弹出直到左括号」的逻辑不参与常规比较。提示很多同学把左右括号的优先级设成一样结果遇到(32)*6时右括号会把左括号也弹出来算掉导致括号丢失。左括号栈内优先级必须低于所有真实运算符。2.3 手写推演一遍32*6-2的完整过程光看表不够我带你走一遍完整流程这样写代码时心里有数。初始化数栈和符栈都为空符栈先压入#作为哨兵。扫描到3是数字压入数栈。数栈[3]符栈[#]。扫描到和符栈顶#比#栈内优先级 0栈外优先级 33 0所以入符栈。数栈[3]符栈[#, ]。扫描到2压入数栈。数栈[3, 2]符栈[#, ]。扫描到*和符栈顶比栈内优先级 3*栈外优先级 55 3所以*入符栈。数栈[3, 2]符栈[#, , *]。扫描到6压入数栈。数栈[3, 2, 6]符栈[#, , *]。扫描到-和符栈顶*比*栈内优先级 5-栈外优先级 33 5所以弹出*计算。弹出数栈顶两个数 6 和 2算2*612压回数栈。数栈变成[3, 12]符栈[#, ]。继续拿-和新的栈顶比栈内优先级 3-栈外优先级 33 ≥ 3所以弹出计算。弹出 12 和 3算31215压回数栈。数栈[15]符栈[#]。再拿-和#比0 3所以-入符栈。数栈[15]符栈[#, -]。扫描到2压入数栈。数栈[15, 2]符栈[#, -]。表达式扫描完开始收尾弹出符栈顶-弹出 2 和 15算15-213压回数栈。数栈[13]符栈[#]。#不参与计算结束。结果 13。等等32*6-2按正常优先级应该是312-213没错。但如果你把*和优先级搞反结果就会变成(32)*6-228这就是优先级表设计错误的典型翻车现场。3. 用 C 语言把双栈求值器跑通完整代码与逐段拆解3.1 栈结构定义与基础操作先定义两个栈。为了代码清晰我用结构体封装数栈存double类型兼容除法小数符栈存char。栈的大小根据表达式长度动态分配或者给一个足够大的固定值实验里一般 100 够用。#include stdio.h #include stdlib.h #include ctype.h #include string.h #define MAXSIZE 100 // 数栈存操作数 typedef struct { double data[MAXSIZE]; int top; } NumStack; // 符栈存运算符 typedef struct { char data[MAXSIZE]; int top; } OpStack; void initNumStack(NumStack *s) { s-top -1; } void initOpStack(OpStack *s) { s-top -1; } int isNumEmpty(NumStack *s) { return s-top -1; } int isOpEmpty(OpStack *s) { return s-top -1; } void pushNum(NumStack *s, double v) { if (s-top MAXSIZE - 1) { printf(数栈溢出\n); exit(1); } s-data[(s-top)] v; } double popNum(NumStack *s) { if (isNumEmpty(s)) { printf(数栈为空表达式有误\n); exit(1); } return s-data[(s-top)--]; } double peekNum(NumStack *s) { if (isNumEmpty(s)) { printf(数栈为空\n); exit(1); } return s-data[s-top]; } void pushOp(OpStack *s, char op) { if (s-top MAXSIZE - 1) { printf(符栈溢出\n); exit(1); } s-data[(s-top)] op; } char popOp(OpStack *s) { if (isOpEmpty(s)) { printf(符栈为空\n); exit(1); } return s-data[(s-top)--]; } char peekOp(OpStack *s) { if (isOpEmpty(s)) { printf(符栈为空\n); exit(1); } return s-data[s-top]; }这段代码没什么玄学就是标准的顺序栈。注意popNum和popOp里加了空栈判断因为表达式写错时比如32会触发连续弹栈没有保护程序直接崩。peekNum和peekOp在求值主逻辑里用来查看栈顶但不弹出比如判断符栈顶是不是左括号。3.2 优先级比较函数与计算函数优先级函数返回栈内和栈外两个值。我一般写一个函数getPriority(char op, int inStack)inStack为 1 时返回栈内优先级为 0 时返回栈外优先级。// 返回运算符优先级inStack1 表示栈内0 表示栈外 int getPriority(char op, int inStack) { switch (op) { case : case -: return 3; case *: case /: return 5; case (: return inStack ? 1 : 6; case ): return 1; case #: return 0; default: return -1; } } // 执行一次二元运算 double calc(double a, char op, double b) { switch (op) { case : return a b; case -: return a - b; case *: return a * b; case /: if (b 0) { printf(除零错误\n); exit(1); } return a / b; default: printf(未知运算符 %c\n, op); exit(1); } }calc里对除零做了判断这是实验报告里容易被忽略但老师一定会看的点。另外注意参数顺序a是左操作数b是右操作数弹栈时先弹出的是右操作数别搞反了否则减法和除法结果全错。3.3 主求值循环扫描、比较、计算、收尾主函数负责扫描字符串、拼接多位数、处理括号和收尾。多位数处理是新手最容易翻车的地方12345不能把1、2、3当成三个数分别压栈必须拼成一个整数。double evaluate(char *expr) { NumStack numStk; OpStack opStk; initNumStack(numStk); initOpStack(opStk); pushOp(opStk, #); // 哨兵 int i 0; while (expr[i] ! \0) { // 跳过空格 if (expr[i] ) { i; continue; } // 数字拼接多位数 if (isdigit(expr[i]) || expr[i] .) { double num 0; int hasDot 0; double factor 0.1; while (isdigit(expr[i]) || expr[i] .) { if (expr[i] .) { hasDot 1; i; continue; } if (!hasDot) { num num * 10 (expr[i] - 0); } else { num (expr[i] - 0) * factor; factor * 0.1; } i; } pushNum(numStk, num); continue; } // 运算符 char op expr[i]; if (op () { pushOp(opStk, op); i; continue; } if (op )) { // 弹出运算符直到左括号 while (peekOp(opStk) ! () { char topOp popOp(opStk); double b popNum(numStk); double a popNum(numStk); pushNum(numStk, calc(a, topOp, b)); } popOp(opStk); // 弹出左括号 i; continue; } // 常规运算符比较优先级 while (getPriority(peekOp(opStk), 1) getPriority(op, 0)) { char topOp popOp(opStk); double b popNum(numStk); double a popNum(numStk); pushNum(numStk, calc(a, topOp, b)); } pushOp(opStk, op); i; } // 收尾弹出剩余运算符 while (peekOp(opStk) ! #) { char topOp popOp(opStk); double b popNum(numStk); double a popNum(numStk); pushNum(numStk, calc(a, topOp, b)); } return popNum(numStk); } int main() { char expr[200]; printf(请输入表达式); scanf(%s, expr); double result evaluate(expr); printf(结果%g\n, result); return 0; }主循环的逻辑分四块跳空格、拼数字、处理括号、处理常规运算符。数字拼接里我加了小数点支持这样3.14*2也能算。括号处理里遇到右括号就不断弹运算符计算直到栈顶是左括号然后把左括号弹掉。常规运算符处理里while循环条件是栈顶优先级 ≥ 当前运算符优先级注意这里用的是而不是因为同级运算符要从左往右算比如10-3-2必须先算10-3再减2如果只用同级运算符会一直压栈最后变成10-(3-2)9结果就错了。收尾阶段用#作为终止标志不断弹出运算符计算直到符栈只剩#。最后数栈里剩下的就是结果。注意scanf(%s, expr)遇到空格会截断如果表达式里有空格用fgets替代。实验里一般输入不带空格但报告里可以提一句这个边界。3.4 测试用例与预期结果写完代码别急着交至少跑这几组用例输入表达式预期结果考察点32*6-213基本优先级(32)*630括号改变优先级10-3-25同级从左往右100/5/210除法同级顺序2*(34)-59混合嵌套8/0报错除零处理如果10-3-2算出 9说明优先级比较用了而不是。如果(32)*6算出 13 或者报错说明左括号栈内优先级设高了。这些用例覆盖了双栈法最常见的坑跑通基本就没大问题。4. 实验报告怎么写才不被扣分结构、截图与复杂度分析4.1 报告里必须出现的几个模块「数据结构表达式求值实验报告.doc」这个文件名本身就暗示了交付物是一份 Word 文档。老师看报告的时间通常不超过三分钟所以结构清晰比文采重要。我见过的得分比较稳的报告一般包含这几块实验目的、实验环境、算法思路、核心代码、测试结果、复杂度分析、心得体会。其中算法思路和测试结果是重点代码不用全贴贴关键函数就行。实验目的别写空话写具体「掌握栈的先进后出特性在表达式求值中的应用理解运算符优先级与括号匹配的处理逻辑」。实验环境写清楚编译器和系统比如Dev-C 5.11 / Windows 10或者gcc 9.4 / Ubuntu 20.04。算法思路用文字加流程图描述双栈法的扫描过程流程图用 Word 自带的形状画别贴代码截图。4.2 测试截图怎么截才有说服力测试结果部分每一条用例都要有输入和输出的截图。截图要包含控制台窗口的标题栏或者命令行提示符证明是你自己跑出来的不是从网上抄的。输入32*6-2输出13输入(32)*6输出30输入8/0输出除零错误提示。截图下面配一行说明「测试用例 1验证乘法优先级高于加法结果正确」。如果老师要求对比不同实现可以加一组「中缀转后缀再求值」的结果做对照但那是加分项不是必须的。核心还是把双栈法讲透。4.3 复杂度分析与心得体会的写法复杂度分析写两句话就够时间复杂度 O(n)因为每个字符最多入栈出栈各一次空间复杂度 O(n)两个栈的深度与表达式长度成正比。别展开成数学证明老师不看。心得体会是唯一可以写「人话」的地方。可以写你调试时遇到的真实问题比如「一开始忘了处理多位数输入 123 算出来 6后来加了数字拼接循环才正确」。这种具体踩坑比「通过本次实验我深刻理解了栈的应用」强一百倍。但注意别写成流水账挑一两个有代表性的问题写清楚现象、原因、解决就行。5. 避坑与排查双栈求值最容易翻车的 5 个地方5.1 多位数被拆成单个数字现象输入123结果是6而不是15。原因扫描时把1和2当成两个独立的数分别压栈了。解决在数字处理分支里加一个while循环连续读取数字字符并拼成整数遇到非数字字符才停止。如果支持小数还要处理小数点。5.2 同级运算符顺序算反现象输入10-3-2结果是9而不是5。原因优先级比较用了而不是导致同级运算符没有及时弹出计算最后变成从右往左结合。解决把比较条件改成getPriority(栈顶, 1) getPriority(当前, 0)保证同级从左往右。5.3 括号匹配失败或左括号提前弹出现象输入(32)*6结果报错或者算出13。原因左括号的栈内优先级设得和栈外一样高导致新运算符进来时把左括号弹出去计算了。解决左括号栈外优先级设为最高比如 6栈内优先级设为最低比如 1这样它入栈时畅通无阻在栈内时又不会被误弹。5.4 除零没有判断导致程序崩溃现象输入8/0程序直接闪退或者输出inf。原因calc函数里没有对除数为零做检查。解决在除法分支里加if (b 0)判断输出错误提示并退出。实验报告里加上这个判断是加分项说明你考虑了边界情况。5.5 表达式扫描完后忘记收尾现象输入32*6-2结果只算了部分输出15或者3。原因主循环结束后符栈里还有运算符没弹出计算数栈里也不止一个数。解决扫描结束后加一个while循环不断弹出符栈顶运算符并计算直到符栈只剩哨兵#。收尾逻辑和常规运算符处理里的弹栈计算完全一样可以直接复用。6. 从实验到实战把求值器扩展成支持变量和函数的计算器实验报告交完这套双栈法其实还能继续用。我带学生做课程设计时常见的进阶方向是把它扩展成一个支持变量和简单函数的计算器。核心改动不大但能让你对栈的理解再深一层。第一个扩展是变量支持。在数栈之外再加一个符号表用数组或者哈希表存变量名和值。扫描到字母时先读取完整标识符然后去符号表里查值压入数栈。如果是赋值语句x35就在等号右边算完后把结果写回符号表。这里要注意标识符的读取和数字读取类似都是连续字符拼接但变量名可能包含字母、数字、下划线判断条件用isalnum加下划线。第二个扩展是函数支持。比如sin(30)、max(3,5)。处理方式是在符栈里增加函数名标记遇到函数名时压入符栈遇到左括号正常处理遇到右括号时如果栈顶是函数名就弹出来执行对应函数。函数参数用逗号分隔需要在符栈里额外处理逗号遇到逗号就弹出运算符计算直到遇到左括号。这部分逻辑比基础求值复杂不少但本质还是栈的弹出和压入只是多了一层参数个数的判断。第三个扩展是错误恢复。基础版本遇到错误直接exit(1)实际计算器不能这样。可以把exit换成返回错误码主循环里检查错误码并提示用户重新输入。比如除零返回-1括号不匹配返回-2未知字符返回-3。这样程序不会一错就退体验好很多。我自己的习惯是每加一个功能就先写三组测试用例跑通了再往下加。变量支持测x5然后x*2函数支持测max(3,5)和sin(0)错误恢复测1/0和(12。这样一步步来不会一次改太多导致调不动。最后说个血泪经验表达式求值这个实验代码写完之后一定要用纸笔手动推演一遍32*6-2的栈变化过程把每一步的栈内容画出来。我当年就是靠这个笨办法发现优先级比较写反了否则盯着代码看半天也看不出问题。希望帮到你。本文还有配套的精品资源点击获取