★ FEATURED ARTICLE 简介《数据结构实验报告-栈与队列-中缀表达式求值》是面向高校计算机专业学生的实验报告文档聚焦栈与队列在表达式求值中的应用。报告完整描述了从键盘输入中缀表达式、建立操作数与运算符双栈并计算求值结果的思路涵盖四则运算、括号及一元正负号处理兼顾基础要求与提高要求。包内含单个docxWord文档大小51KB完整收录了实验目的、数据结构与算法设计、输入输出说明、主要函数说明、源程序代码及测试报告能够帮助读者深入理解运算符优先级比较、堆栈操作和整数除法的舍余处理。已有2899人学习这一报告适合正在学习数据结构、需完成栈实验或复习表达式求值算法的学生作为参考与仿写范例也可作为课程设计素材。1. 中缀表达式求值双栈模型是这份实验报告的核心资产中缀表达式求值说白了就是让程序像人一样读“9(3-1)*310/2”这种式子不光要算出结果还要把括号和优先级都处理对。你手头的这份《数据结构实验报告-栈与队列-中缀表达式求值》就是干这个的从键盘读进一个以“#”结尾的中缀表达式用运算符栈和操作数栈两个栈一进一出最终打印出整型结果。它不是纯玩具代码而是完整覆盖了栈的初始化、销毁、出入栈、优先级比较和一元负号处理的C语言实现适合正在学栈与队列、准备数据结构实验的人拿来回填和理解。我当初第一次看到这类实验题时最大的困惑是“为什么要搞两个栈一个栈不能算吗”。后来动手写完才发现一个栈根本存不下两类信息数字要等运算符运算符要等优先级。这篇博文我就按“这是什么→原理→代码走读→踩坑→验收→扩展”的顺序拆给你看代码直接来自报告原文我会在关键行标注容易翻车的位置。需要完整报告文档的文末有获取方式。2. 双栈求值的原理运算符优先级表与isp/icp机制2.1 为什么必须用两个栈操作数和运算符的生命周期不同中缀表达式的核心难点在于“运算符要等”。给你一个“12*3”你读到“*”时不能立刻算因为后面可能还有“(”或者更高优先级的运算符。运算符栈的作用是暂存这些“等着的”符号操作数栈则保存已经解析出来的数字一旦确定当前运算符可以执行就从两个栈中各取数据运算再把结果压回操作数栈。这份报告里的两个结构体定义得很清楚typedef struct DPTR { char *elem; // 运算符栈存char类型 int n; int top; } StackTR; typedef struct OPND { int *elem; // 操作数栈存int类型 int n; int top; } StackND;逻辑说明运算符栈存的是字符、-、*、/、括号以及哨兵“#”操作数栈存的是整型数字。栈顶指针top初始为-1入栈用“top”出栈用“top--”这是最朴素的数组栈实现。参数说明M25是栈最大容量意味着表达式长度和中间结果深度不能超过这个规模超了就栈溢出。我一般会提醒一句这两个栈的容量定成25对单个实验是够用的但如果你拿它去算很长的嵌套表达式比如连续几十层括号栈底指针会直接越界又没有报错机制结果就是内存被改写得乱七八糟。2.2 isp和icp栈内优先级与栈外优先级到底差在哪里报告中出现了两个容易混淆的函数isp与icp很多人第一次看代码会以为它们是一样的其实它们一个查“栈里符号的优先级”一个查“新来符号的优先级”。isp返回栈顶运算符的优先级icp返回当前读到的运算符的优先级两者比较后决定压栈还是弹栈计算。int isp(char e) { switch(e) { case#: return 0; case(: return 1; case: case-: return 2; case*: case/: return 3; case): return 4; default: return -1; } } int icp(char e) { switch(e) { case#: return 0; case): return 1; case: case-: return 2; case*: case/: return 3; case(: return 4; default: return -1; } }逻辑说明这里isp与icp的数值表以括号做了差异化处理。左括号在栈外优先级最高4一遇到就要压栈但在栈内优先级最低1表示只要栈里有左括号其他运算符进来都得先压在上面等到右括号来时再一并弹出。右括号则反过来栈外优先级只有1栈内优先级最高4这样它一到就能把括号里的运算符全部逼出来。参数说明对比时如果icp大于isp则压栈否则弹出栈顶运算符并执行计算这就是算符优先算法最简形态。这份优先级表是括号处理正确与否的分水岭。很多同学会问为什么不直接用一个统一优先级表答案在于左括号的“双重身份”它在等待匹配时是屏障在被匹配时必须立刻让步。网上大量翻车代码都是把左括号优先级写死结果出现“((12)*3”这种输入时运算顺序乱套。2.3 哨兵“#”是整个算法的锚点运算符栈在计算开始前就压入一个“#”它是处理表达式结束的标志也是避免空栈访问的保护伞。主循环条件是“当前读到的字符不是#或栈顶不是#”这意味着只有输入遇到结束符且运算符栈被清到只剩#时循环才终止。PushTR(tr, #); g getchar(); while(g ! # || GetTopTR(tr) ! #) { // 主处理逻辑 }逻辑说明因为压入了#第一次比较运算符优先级时isp(#)返回0icp(任何运算符)至少是1所以第一个真正的运算符必然被压栈而不是弹栈这保证了栈底不被误操作。参数说明getchar()每次读一个字符所以数字“123”会被拆成三个字符逐个读入需要后面的Getnum把连续数字合并回123。如果你拿的是这份报告里的完整代码可以直接在这一段执行前加几个printf观察栈的变化我调试时就是这么干的。这个习惯帮我在一次处理复杂括号嵌套时准确定位到了弹出逻辑错误。3. 代码走读从输入到输出的完整主线3.1 主循环运算符判断与数字合并Calculate函数是整个实验的发动机。它每次读入一个字符先用WheOperator判断是数字还是运算符数字直接压栈或合并运算符则进入优先级比较流程。int WheOperator(char e) { if(e 0 e 9) { return 0; // 不是运算符 } else { return 1; // 是运算符 } } int Transform(char t) { int a; a t - 48; // 字符0的ASCII是48 return a; }逻辑说明WheOperator把数字和运算符分成两路处理。Transform将单个数字字符转为int减48是拿字符的ASCII码直接偏移。参数说明这种转换方式只对单个字符有效而处理多位整数时需要在Getnum函数里把前一个数字乘10再加当前数字。代码中用一个中间变量l记录上一个字符如果上一个字符和当前字符都是数字就走合并分支。int Getnum(int x, int y) { if(x 0) { return 10 * x - y; } return 10 * x y; }逻辑说明这个函数是给“连续数字转整数”用的例如前一个拼好的数是12新读到的字符是3调用Getnum(12,3)返回123。注意负数处理分支如果x小于0说明当前拼的是负数调用10*x-y可以把负号保留在最高位否则“-12”会被错误拼成“-12”没错但再拼一位时符号位就会丢失。参数说明这里x是已合并数y是新数字代码的返回类型是char但实际返回int严格地说有类型窄化问题不过在这个实验的值域内不会触发异常。3.2 优先级比较与弹栈计算运算符栈的运转机制运算符的处理核心是“isp、icp比较小则压栈大则弹栈计算”。代码中这部分逻辑在Calculate函数的主循环里。h GetTopTR(tr); // 取运算符栈顶 i isp(h); // 栈内优先级 j icp(g); // 栈外优先级 if(i j) { PushTR(tr, g); // 新运算符优先级高压栈 } else { PopTR(tr, h); // 弹出栈顶运算符 if(h ! ( i j || i j) { PopND(nd, b); PopND(nd, a); PushND(nd, Connect(a, b, h)); continue; // 继续下一轮不读新字符 } }逻辑说明ij时说明新运算符应该“压住”栈顶运算符比如栈顶是新来的是*则*压栈。ij时则弹出栈顶运算符并执行一次二元运算。有个关键细节当弹出的是左括号且优先级相等时这段代码不做操作也不压栈相当于把左括号丢弃并继续循环这是括号匹配的精髓。参数说明if(h!( ij || ij)这个条件写得不够工整我拆开看是“(h不是左括号且ij)或ij”才做运算右括号出现时ij且h可能是左括号这时不会错误地弹两个操作数计算而是静默丢弃左括号。这里有个容易看迷糊的地方运算符栈弹出了左括号但操作数栈没有弹出数字相当于“只是完成了括号的匹配不做计算”这是完全正确的。我当初调试时在这个条件上卡了一晚上最后加打印才看清它的意图。3.3 一元负号处理k这个标记变量的作用基本要求的表达式只有二元运算符但提高要求里出现了“5”和“-3”这种一元正负号。报告代码里用了一个巧妙但不太容易看懂的k变量来标记负号。if(WheOperator(l) 1 g -) { k !; g getchar(); continue; }逻辑说明当上一个字符l是运算符比如刚读入“*”或“(”而当前读入的是“-”说明这个“-”不是减法而是负号。代码把k置为“!”表示“下一个数字要取负”然后直接读下一个字符。参数说明k的作用相当于一个待处理标记配合后面的“if(k!)”分支在压数字时压入负值。if(k !) { PushND(nd, -a); k ; } else { PushND(nd, a); }逻辑说明k!时对这个数字取负再压栈然后把k改为防止同一个数字被反复取负。参数说明k只是一个普通状态值代码里没有再用它做其他判断它存在的意义是“本次负数已处理下一个数字恢复正常”。这种临时标记的做法不优雅但在表达式求值场景下功能是完整的。如果你决定把这段拿去交实验建议在注释里把这个标记位写清楚否则导师很可能追问“为什么用两个字符做标记一个不行吗”。答案是可以但“!”和“”是为了调试时printf输出更直观这是我个人在这份代码里唯一想保留的注释风格。4. 避坑指南这份代码的五个常见问题4.1 除数只保留整数商导致的精确性误解现象输入“7/2”得到3而不是3.5有些同学以为是程序算错了反复排查。原因实验要求明确规定“若两个整数相除结果只保留整数商余数丢弃”Connect函数里case /执行的是yx/y这是C语言的整数除法结果自动截断小数。但在用这个代码做验算时如果你拿Python或者计算器对比得到的数值天然不同。解决先确认实验要求标题是“中缀表达式求值”不是“浮点计算器”整型结果是设计目标而非缺陷。如果你确实需要小数结果可以修改StackND的elem类型为double然后Connect函数的参数与返回类型全部同步为double压栈和出栈操作也一并调整但这会大幅改动代码量需要评估是否值得。4.2 一元负号只在特定位置生效导致“--2”这类表达式算错现象输入“--2”或“1--2”这类连续负号表达式时程序输出结果和数学期望不一致甚至是0。原因k的标记机制只处理“运算符后紧跟负号”的情况。输入“--2”时第一个“-”被识别为负号k!紧接着读第二个“-”此时上一个字符l已经变成“-”了吗实际循环里lg赋值发生在continue之前所以第二个“-”会被当成新的运算符来参与优先级比较本质上是把“负负得正”这种语义丢了。解决如果实验要求没有强制处理连续一元运算符建议避开这类测试用例或是在测试报告里注明该程序实现的是“单次一元负号”语义。如果确实需要支持可以在识别到k!且当前字符又是-时把k重置为正常状态并继续向后读相当于两个负号抵消。4.3 多位数字合并与负号组合出现拼数错误现象输入“1234”结果正确但输入“-1234”时得到的结果像是“12”和“-3”被拼成了“12-3”。原因Getnum的负数分支返回10*x-y这只适用于“x为负数y为正数”的拼接。但在当前代码流程里负号标记k!是先设好等读到下一个数字时才把负值压栈一旦出现“-123”这种连续三位数第一次拼接时x传入的是-1y传2Getnum(-1,2)返回-12没问题但第二次拼接时x-12y3Getnum(-12,3)返回-123也没问题。真正出错的是当负号出现在合并过程的中间时比如“12-3”会被拼成“12-3”这里的“-”被识别成负号还是减号取决于它前面的字符l是不是运算符。解决不要试图通过修改Getnum来兼容所有情况。在我的使用经验里这个代码最稳妥的用法就是“一个数对应一个完整的分词过程”不要让它去处理“数字中间夹负号”这种场景。你的测试用例设计应该让每个操作数之间都有明确的运算符分隔。4.4 栈容量固定导致长表达式内存越界现象输入一个很长的表达式比如超过25个运算符加操作数程序运行到一半跳出或者打印出离谱的随机值。原因两个栈的最大容量是M25while循环里没有栈满检查。PushTR和PushND直接执行s.elem[s.top]一旦top超过24就会写越界内存瞬间破坏相邻数据。解决把M从25改成一个更大的值比如100或200但这只是扩大容量不是消除问题。更负责的做法是在PushTR和PushND里加if(s.top s.n-1)判断满了就realloc扩容。我在自己的版本里改成动态扩容后就没有再遇到这个坑。建议你把这一点改进写在实验报告的“算法改进”部分这是加分项。4.5 连续调用Calculate导致栈状态残留现象在main里连续调用两次Calculate第二次输入同等表达式得到结果不一致甚至出现乱码。原因Calculate每次开头都会InitStackTR和InitStackND并压入哨兵#看起来是全新状态但如果上一次调用中途出错提前return或者说上一次的堆栈销毁不彻底DelStackTR只free了内存但没置NULL第二次调用时的malloc可能复用同一块内存里面的旧值会被带进来。解决保持“一次调用创建一次栈、结束就销毁”的配对习惯不要在一个进程里反复调。如果非要多次计算建议在Calculate入口加一个防御性的重置逻辑把栈底和栈顶全部归零初始化。这是我在做多次表达式测试时踩出来的经验建议你也养成这个习惯。5. 实验报告怎么交测试用例设计与验收打分点5.1 必测的七类表达式用例实验老师批阅时主要靠测试输入输出判断正确性所以你交给老师的“程序测试简要报告”部分需要覆盖足够的输入类型。下面这张表是我按照基本要求和提高要求整理的最小用例集用例编号输入表达式预期输出覆盖点112#3基础加法22*34#10乘优先于加32*(34)#14括号优先48/2/2#2左结合5-53#-2一元负号61234#46多位数合并7(23)*(4-1)#15多括号嵌套逻辑说明第4条“8/2/2”特别有价值因为除法有左结合性如果优先级表写错可能得到8/(2/2)8而不是2。第5条验证k标记是否生效第6条验证Getnum的正数合并第7条验证括号匹配和多次弹栈的协同。建议你把这份表格搬进实验报告的“测试简要报告”一节再补一两行“以上用例全部通过”之类的描述。老师看到的是你按逻辑设计用例而不是瞎输入。5.2 验收打分点拆解代码注释、排版、健壮性报告的评分规则是60%功能40%写作排版注释这意味着即使功能全对如果注释和排版不行也可能被扣掉不少分。我仔细看过这份报告的原文它的函数注释很齐全几乎每个函数都有一行说明。你拿到后要做的是把“主要函数说明”那一节整理成表格或列表让老师一眼看到所有函数名称及用途。void InitStackTR(StackTR s); // 创建运算符堆栈 void InitStackND(StackND t); // 创建操作数堆栈 void DelStackTR(StackTR s); // 销毁运算符堆栈 void DelStackND(StackND t); // 销毁操作数堆栈 void PushTR(StackTR s, char e);// 运算符入栈 void PopTR(StackTR s, char e);// 运算符出栈逻辑说明这是报告中“主要函数说明”一节的摘录每行一个函数加简短注释。我建议你在交文档前把这部分扩写成“函数名参数含义返回值核心逻辑”四列因为老师批注时最怕看到函数清单但不懂参数意义。参数说明\t是引用传递在C语言里这是传地址的语法糖意味着函数内能修改实参本身这也是栈能被初始化和销毁的原因。5.3 排版上的三个加分细节第一代码块要统一缩进风格这份原始代码的缩进不太统一你在报告中重新排版时顶格或全部用Tab读起来会舒服很多。第二实验目的和数据设计描述不可以抄网上的模板建议把“掌握堆栈在表达式求值中的应用”改成结合自己代码的话。第三输出结果截图不要只截一张把输入和输出都展示最好在不同运算符的样例后各附一张。这三条建议是某高校一位学长在做模拟项目X时总结出来的他说老师最喜欢看到“排版整齐、说明详实、测试结果完整”的三件套。你按照这个标准整理分数大概率不会差。6. 从这份代码到你的扩展版本三个立等可取的改造技巧6.1 把固定容量栈改为动态扩容栈原代码最大痛点是栈容量写死M25我把Push函数改成动态扩容后长表达式再也没崩过。void PushTR(StackTR s, char a) { if(s.top s.n - 1) { s.n * 2; s.elem (char *)realloc(s.elem, sizeof(char) * s.n); if(s.elem NULL) { printf(内存不足\n); exit(1); } } s.elem[s.top] a; }逻辑说明每次压栈先检查栈顶是否到达容量上限到达则用realloc翻倍扩容。参数说明realloc会保留原有数据并把新分配的内存接到后面同时s.n更新为新容量这个操作的核心是“容量动态增长且旧数据不丢”。如果你是初学者建议先备份原代码再改改完用第5章的测试表全部跑一遍。6.2 用制作token的方式替换原始getchar原始代码是逐个字符getchar这个方案在多位数字和非法空格输入时显得很吃力。我一般会先做一个简单的一遍扫描分词把“数字串”切成一个整型token再送进中缀求值的主逻辑。char str[128]; scanf(%s, str); int i 0; while(str[i] ! #) { if(str[i] 0 str[i] 9) { int num 0; while(str[i] 0 str[i] 9) { num num * 10 (str[i] - 0); i; } PushND(nd, num); continue; } // 运算符处理逻辑 i; }逻辑说明这种写法直接按字符数组遍历遇到连续数字就循环累加成一个数遇到运算符就交给优先级逻辑。好处是不需要l和Getnum那一套“上一个字符”的追踪逻辑代码可读性大幅提升。参数说明num累加时每读到一个数字字符就乘10再加差值这天然处理了任意长度的整数。6.3 加一个表达式合法性检查虽然实验要求说“程序可不处理语法错误”但每次遇到不合法表达式直接得到乱码还是挺让人抓狂的。我做了一个前置检查函数在计算前先扫描括号是否匹配。int checkBrackets(char *str) { int cnt 0; for(int i 0; str[i] ! #; i) { if(str[i] () cnt; else if(str[i] )) cnt--; if(cnt 0) return 0; // 右括号比左括号多 } return cnt 0; // 最终必须完全匹配 }逻辑说明用一个计数器遍历字符串遇到左括号加一右括号减一。如果中途计数器为负说明右括号没有对应的左括号最后计数器不为0说明左右括号数量不等。参数说明这个检查只花O(n)时间但能拦截掉大部分会导致算法死循环或误算的输入。从那以后我每次拿到类似表达式求值的代码都强制先加这个检查再跑计算逻辑省了大量排查时间。最后送你一个自己的习惯拿到任何“栈应用”代码先跑三个输入——“0#”“(1)#”“8/0#”分别验证空数据、纯括号、除零边界。这三个用例过了代码至少能在基础场景站住。希望这份拆解能帮你在实验报告上少走点弯路也希望你能把这份代码真正变成自己的东西。本文还有配套的精品资源点击获取
阅读完成 · 觉得有帮助？
