简介面向西南交通大学数据结构课程‘栈与队列’实验这份资源是与中缀表达式求值主题配套的完整实验报告。报告逐项给出实验内容要求基础版覆盖加减乘除四则运算与括号、操作数零至九提高版增加一元正负号、任意整型操作数及整数相除取整并完整包含数据结构设计、算法设计、输入输出设计、主要函数说明、测试报告和源程序代码。实现上围绕运算符栈与操作数栈展开通过栈内外优先级比较决定压栈或运算使用动态内存分配与栈顶指针管理代码分函数组织、注释清楚同时附有各类运算的测试结果。文档保留学号、姓名等占位信息可作为实验报告模板直接修改。压缩包内为单个docx文件约51KB已有2899人学习下载适合正在学习数据结构、需要完成同类实验报告或深入理解栈与队列应用的读者。1. 一份能直接交实验的栈应用代码中缀表达式求值的地基与它的隐藏坑中缀表达式求值是数据结构课程里栈的经典应用也是实验报告里出镜率最高的选题之一。手头这份C语言代码用一个运算符栈加一个操作数栈完成一次扫描求值核心是isp/icp两套优先级编号栈外优先级高就压栈栈外优先级低就弹出计算。它覆盖了实验基本要求的 - * / 与括号也实现了提高要求里的一元正负号和任意int操作数整数除法按C规则截断。适合三类人要交数据结构实验报告的学生、准备408或考研机试的备考生、想从一份能跑的代码里拆出可复用栈思路的从业者。注意标题里的“队列”在代码里几乎没出场这份资源真正的主角是栈。后文按“为什么这么设计→主流程怎么走→易错点在哪儿→怎么排查→如何改造成自己的工具”逐层拆开。2. 双栈结构与isp/icp优先级表为什么这套设计能支撑任意括号嵌套2.1 为什么要两个栈一次扫描背后的“延迟决定”人算中缀表达式时会在脑子里滞后处理优先级。看到23*4会先记下等3*4算完再回头算212。程序没有这种临时记忆只能拿栈当“记账本”。读到一个运算符时程序不立刻决定计算而是先和运算符栈顶比优先级栈外新来的运算符比栈顶高说明右边的运算要先做于是压栈比栈顶低或相等说明栈顶运算符该先算于是弹出栈顶同时让操作数栈弹出两个数参与计算。这就是一遍扫描求值的本质把中缀表达式拆成一段“遇到高优先级就攒着、遇到低优先级就先结算”的序列。它和单调栈处理“左边第一个更大元素”是同一类思想——栈内维持一个有序性区别在于这里维持的是优先级次序而且每次比较都发生在栈顶不需要遍历。2.2 栈的C实现动态分配、top-1与容量M25原代码为运算符和操作数分别定义了两个结构体写法上只有元素类型不同运算符栈存char操作数栈存int。typedef struct DPTR{//运算符堆栈 char *elem; //栈内元素数组 int n; //容量 int top; //栈顶指针 }StackTR; typedef struct OPND{//操作数堆栈 int *elem; //栈内元素数组 int n; //容量 int top; //栈顶指针 }StackND; void InitStackTR(StackTR s){ s.nM; s.top-1; s.elem(char *)malloc(sizeof(char)*M); } void PushTR(StackTR s,char a){ s.elem[s.top]a; } void PopTR(StackTR s,char e){ es.elem[s.top--]; }top初始化为-1入栈用top出栈用top--这是顺序栈的标准写法。malloc在堆上分配M个槽位M定义为25意味着表达式里同时需要的运算符层数不能超过25。括号嵌套很深、或者连续出现多个一元负号时要留意这个上限原代码没有做越界检查这是实验代码的量级能跑但别拿极端用例压它。销毁栈用free释放elem销毁后结构体变量本身还在只是elem变成悬空指针。如果销毁后仍调用GetTopTR这类函数属于未定义行为调试时容易在莫名其妙的地方崩掉。2.3 isp与icp两张优先级表是怎么把括号“安排”明白的整个算法最核心的一张表长这样符号#) -* /(isp栈内优先级04231icp栈外优先级01234左括号在栈外优先级最高4所以任何左边的运算符都压不过它括号里的内容必然先入栈一旦入栈isp降到1低于所有四则运算符括号内的计算就能照常进行直到等来右括号。右括号在栈外优先级最低1意思是它不参与压栈只用来强制触发弹出它在栈内优先级是4一旦它在栈顶谁都得让位。这两张表的不对称是刻意设计。验证一下括号配对的核心场景当栈顶是左括号、新读到右括号时ispicp1此时ij成立但左括号不应触发任何计算只能被弹出。这个判断在原代码里写成if(h!( ij || ij)C语言里优先级高于||实际含义是((h!() (ij)) || (ij)。拆清楚这句话括号逻辑就通了一半后面第4章还会详细展开。提示优先级表是这份代码的“规则说明书”写错一个数字整个括号嵌套全乱。动手改代码前先把这张表默写一遍。3. 一次扫描的求值主流程从#哨兵、负号标记到两个栈的协作3.1 主循环的停机条件输入结束#和栈底#都不消失才算完Calculate函数是整个程序的大脑初始化时先往运算符栈压一个#作为栈底哨兵然后循环读取字符。int Calculate(){ char g,h,l,k; int a,b; l-; // l记录上一个读入的字符初始化为-代表表达式开头 k; // k标记一元负号是否待消费 StackTR tr; StackND nd; InitStackTR(tr); InitStackND(nd); PushTR(tr,#); // 栈底哨兵优先级0低于所有运算符 ggetchar(); // 读第一个字符 while(g!#||GetTopTR(tr)!#){ // 主逻辑数字进操作数栈运算符比优先级 } PopND(nd,c); // 最终结果 DelStackTR(tr); DelStackND(nd); return c; }栈底压入#有两个作用。一是作为比较基准它的isp0低于所有真实运算符保证第一个真正读到的运算符能顺利入栈。二是停机判断只有输入读到#且运算符栈只剩栈底#才说明所有运算符都已结算完毕循环退出。while条件里用的是逻辑或||意思是“输入没结束或者栈没清空”两个条件同时为假才退出。如果误写成会出现输入已经结束但栈里还剩运算符未计算、程序提前退出的情况这是自己重写时最容易踩的第一个坑。3.2 连续数字与一元负号两个隐藏状态l和k基本要求里操作数只有0到9一个数字字符就能用一个int存。提高要求放开到任意整型就必须把连续读到的数字字符拼成真正的多位数比如输入12时先读到1再读到2要拼成12。int Getnum(int x,int y){ if(x0){ return 10*x-y; } // x已经是负数时继续接低位 return 10*xy; // 正常情况高位乘10加低位 } // 数字分支内 if(!WheOperator(l)){ // 上一个字符也是数字说明这是多位数 PopND(nd,a); bTransform(g); // 当前字符转数字 aGetnum(a,b); // 合并成多位数 PushND(nd,a); }Transform函数把字符3变成整数3写法是t-48利用ASCII码差值。教学场景里这么写直观工程上更推荐写成t-0含义一样但不需要记48这个魔法数字。Getnum的负数分支值得单独说。当输入是-12时负号先触发一元负号逻辑把1压成了-1下一个2进来时栈里是负数Getnum走10*x-y得到-12。这个分支不是防御代码而是专门为“负数后继续接数字”准备的。如果不写-12会被算成-8。一元负号的触发逻辑在运算符分支最前面if(WheOperator(l)1 g-){ k!; // 标记下一个数字要取负 ggetchar(); continue; }l变量记住上一个读入的字符k变量记住“刚读到一个负号下一个数字需要取负”。触发条件要求上一个字符也是运算符这样3-2里的减号不会被误当成负号因为此时l是数字3。如果l初值不设成-表达式开头的负号就无法识别这也是一个典型翻车点。3.3 优先级比较落地ij压栈ij弹出计算运算符分支的主体是比优先级然后决定压栈还是计算。hGetTopTR(tr); // 运算符栈顶 iisp(h); // 栈内优先级 jicp(g); // 栈外优先级g是当前运算符 if(ij){ PushTR(tr,g); // 新运算符优先级更高先压栈等右边算完 }else{ PopTR(tr,h); if(h!( ij || ij){ PopND(nd,b); // 注意顺序先弹出的是右操作数 PopND(nd,a); PushND(nd,Connect(a,b,h)); // 结果压回操作数栈 continue; } }ij表示栈外优先级更高新运算符入栈等待后续计算。ij表示栈顶优先级不低栈顶运算符可以先结算。比如23*4读到*时栈内是isp(2) icp()(3)*压栈读到4后读到#时栈内是*isp(3) icp(#)(0)先弹*算34再弹算212。Connect函数里执行四则运算减法除法必须注意操作数顺序先弹出来的是b右操作数后弹出来的是a左操作数a-b和b-a结果完全不同。Connect的返回类型是char把int结果塞进char在实验范围内一般不炸但接近int极限时会出现截断后面排查章再细说。4. 括号黑匣子与整数除法边界把if条件彻底拆开4.1 右括号的真实流程为什么同一个右括号会被处理两轮很多读者卡在这一行if(h!( ij || ij)。C语言运算符优先级里高于||所以它等价于((h!() (ij)) || (ij)全程用右括号触发。以(23)*4为例读到第一个右括号时运算符栈顶是isp()2icp())1ij成立于是弹出计算23continue回到循环顶部。注意此时g仍然是右括号没有被重新读入。第二轮再进入运算符分支栈顶变成左括号isp(()1icp())1ij成立但h是左括号第一个条件h!(为假所以不弹操作数。程序进入else分支把左括号弹出栈右括号自然就被“消费”掉了随后读取下一个字符。右括号从头到尾没有压入过运算符栈。它靠“同一个g被continue保留连续两轮处理”来完成配对第一轮把括号内剩余运算符结算完第二轮把左括号弹出。如果自己重写时漏了else分支里的continue右括号会被当成普通字符进入下一次判断行为立刻变成死循环或越界。提示这段代码读起来像天书拆开就是两步——右括号先清空括号内的运算符再弹掉左括号。理解了这个流程其余分支全是体力活。4.2 整型操作数与整数除法C语言截断规则带来的边界基本要求的操作数只有0到9提高要求放开到任意int值。操作数栈用int存储运算直接用yx/y除法结果按C语言规则向零截断。这意味着-7/2得到-3不是数学上的-4。如果实验报告或测试用例预期的是“向下取整”需要特别说明如果按C语言惯例这反而是正确行为。很多同学只测正整数看不到这个差异但提高要求里“整数相除只保留整数商”这句话其实已经隐含了按C截断规则的意思。另一个容易忽略的边界是int溢出。两个接近INT_MAX的值相加是未定义行为INT_MIN取负后仍然是INT_MIN因为补码表示下负数的绝对值比正数范围大1。代码没有对这些边界做保护符合实验要求“程序可不处理语法错误”但想拿高分的话这两处补上检查是显著加分项。4.3 五个小函数的分工表每个函数到底负责什么函数职责输入→返回注意点WheOperator判断字符是否是运算符char→0/1数字字符返回0其它返回1Transform数字字符转intchar→intt-48只对数字有效Getnum合并连续数字int,int→intx为负数时走10*x-yisp / icp查优先级表char→int表写错全盘皆输Connect执行四则运算左操作数,右操作数,运算符→char参数顺序左操作数在前WheOperator把数字字符和运算符做了二元区分0到9返回0其余返回1所以空格、换行这类字符都会被认为是运算符这也意味着原代码不能容忍表达式里有空格。实验要求是“从键盘输入”如果测试时在1 2里加了空格程序会直接进入运算符分支去比较优先级结果不可预期。这不是代码bug而是输入约定的一部分测试要按无空格格式输入。Getnum和Connect是真正动手算的两个函数其余函数都在为它们准备数据。Getnum负责把字符流变成真正的整数Connect负责把栈里的两个整数按运算符合并成一个新整数。5. 常见问题排查五条踩坑记录和一条定位手段5.1 提示语顺序颠倒像“卡住”printf参数求值顺序没有保证现象程序跑起来后不打印“输入一个以#结尾的运算表达式”光标一直闪等输入完内容提示才在结果前出现看起来像程序卡死。原因main函数里写成一行printf(表达式结果为: %d\n,Calculate())Calculate是printf的参数。C标准只规定函数参数求值顺序未指定在多数实现里会先求值Calculate而Calculate内部阻塞在getchar上等待输入要等玩家输完表达式、计算结束printf才拿到返回值开始输出格式串。解决把提示和计算拆成两条语句。先单独printf提示语再调用Calculate最后printf结果。这样无论编译器按什么顺序求值提示语都会先出现行为与编译器无关。5.2 多位数合并出怪数Getnum两个操作数顺序写反现象输入123#预期15实际得到24或者得到更离谱的负值。原因连续数字分支里先PopND弹出栈里已有的高位a再用Getnum(a,b)合并。Getnum约定高位在前、低位在后返回10*ab。如果把参数顺序写成Getnum(b,a)12会被拼成21表达式变成213输出24。解决改回高位在前同时在合并前打印a和b确认谁先出栈。出栈顺序本身也值得检查——先弹的是最近压入的数字也就是表达式中靠后的数字这在多位数字合并时尤其容易搞混。5.3 括号嵌套算错或程序不结束优先级表或continue位置错了现象输入((23))*4#结果不是20而是中间某一步的值或者程序迟迟不输出像死循环。原因两种可能。一是isp表里左括号的栈内优先级设错比如设成和 -一样的2那么右括号到来时栈顶左括号的isp2、右括号icp1ij成立左括号会被当成普通运算符参与计算括号语义直接崩坏。二是else分支里漏了continue右括号弹出后没有保持g不变而是照常执行lg; ggetchar();右括号被当作已处理字符丢弃配对的左括号永远卡在栈里栈清不了循环退不出。解决对照第2章的isp/icp表逐项核对确认右括号弹出左括号后是否继续用同一个g走下一轮。调试时在循环开头打印栈内容能立刻看到左括号是否残留。5.4 一元负号把二元减号吞了负号触发条件写得太宽现象自己改写代码后输入3-2#得到-1或1而不是正确结果1。原因负号触发条件没有检查“上一个字符是不是运算符”。比如写成if(g-)就直接标记负号那么表达式中间的二元减号也会被当成一元负号处理操作数栈会压入一个-2而不是把减号压入运算符栈最终运算顺序全乱。解决严格按原代码写法触发条件必须包含WheOperator(l)1 g-并且l初始化为-。l记录的是“当前字符之前读入的那个字符”它在每轮循环末尾更新但continue分支会跳过更新这一点在改写时要保留。5.5 接近int边界的整数溢出与除零提高要求里的两枚暗雷现象输入1/0#程序直接崩溃或输出垃圾值输入超出int范围的数字得到意外的负数。原因Connect的case /里没有检查除数是否为0整数除零在C里是未定义行为。多位整数拼接时Getnum的中间结果超过INT_MAX也会溢出2147483648会被拼成一个负数后续计算全错。解决在case /前面加if(y0)的判断输出错误信息并结束拼接多位整数时用long long做中间运算最后检查是否落在int范围内再压栈。实验要求允许不处理语法错误但数据边界处理属于工程习惯补上之后代码档次明显不一样。5.6 排查手段循环顶部打印状态十分钟定位问题栈类逻辑最难的不是算法而是“看不见状态”。推荐在while循环体开头插一段调试输出把每轮的输入字符和两个栈的内容打出来// 调试用每轮循环开头打印当前状态定位完删除 printf(g%c l%c k%c | 运算符栈:, g, l, k); for(int idx0; idxtr.top; idx){ printf(%c , tr.elem[idx]); } printf( | 操作数栈:); for(int idx0; idxnd.top; idx){ printf(%d , nd.elem[idx]); } printf(\n);对照表达式手动模拟一遍就能清楚看到是压栈方向错、优先级比较错还是continue位置不对。比如第5.3节的括号残留问题打印后左括号会一直出现在运算符栈里现象一目了然。另外程序正常路径会在Calculate末尾调用DelStackTR和DelStackND释放内存。如果中途有提前return或异常分支两个栈的malloc内存就会泄漏。用valgrind跑一遍看leak summary就能确认释放路径是否完整。6. 把作业代码改造成趁手工具测试矩阵、整行读入和一张表验证法6.1 测试矩阵从“能跑”到“证明它正确”验收栈程序光跑几个正整数用例远远不够。建议准备一组覆盖各种边界的测试矩阵用例期望结果覆盖点12#3基本加法7-3*2#1乘除优先于加减(23)*4#20括号改变优先级((12)*(34))#21嵌套括号-32#-1一元负号打头1234#46多位整数拼接8/4*2#4同优先级左结合3-2#1二元减号不被吞1/0#程序报错除零保护其中8/4*2#特别容易被人手算错。按数学直觉可能先算乘法得到1但C语言里乘除同优先级从左到右结合实际是先 8/42 再 2*24。这个用例能验证代码没有在ij时提前计算而是严格按栈内栈外优先级规则结算。6.2 改造成自己的工具整行读入、空格过滤和栈容量原代码用getchar逐字符读输入约定是无空格、以#结尾。实际用的时候这种输入方式不太友好。最常见的改造是先用fgets整行读入过滤空格和换行再喂给原来的状态机char line[128]; fgets(line, sizeof(line), stdin); for(int i0; line[i]; i){ if(line[i] || line[i]\n) continue; // 把line[i]按原逻辑交给Calculate的状态机处理 }这样测试时1 2 * ( 3 - 4 )这种带空格的表达式也能正常跑不需要刻意控制输入格式。栈容量M25也可以顺手加大比如改成128避免深层括号嵌套时越界。更工程化的做法是给Push函数加一个扩容检查栈满时realloc但实验场景里改常量就够了。记住这份代码的主逻辑很紧凑所有修改都围绕“输入方式”和“容量上限”做不要动isp/icp表和负号标记的状态机那部分动了就要重新过一遍整个测试矩阵。从那以后我每次写栈相关的作业或机试题都先把isp/icp两张表默写在草稿纸上再开始动代码。优先级表就是表达式的“规则说明书”定了它后面的入栈出栈全是体力活不定它调试全是玄学。这份实验报告完整代码可以直接下载建议你照着测试矩阵敲一遍把每个函数为什么存在、为什么是这个返回类型讲清楚比直接抄代码收获大得多。希望帮到你。本文还有配套的精品资源点击获取