企业官网建设流程全解析

简介：《数据结构实验报告-栈与队列-中缀表达式求值》是面向高校计算机专业学生的实验报告文档，聚焦栈与队列在表达式求值中的应用。报告完整描述了从键盘输入中缀表达式、建立操作数与运算符双栈并计算求值结果的思路，涵盖四则运算、括号及一元正负号处理，兼顾基础要求与提高要求。包内含单个docx（Word）文档，大小51KB，完整收录了实验目的、数据结构与算法设计、输入输出说明、主要函数说明、源程序代码及测试报告，能够帮助读者深入理解运算符优先级比较、堆栈操作和整数除法的舍余处理。已有2899人学习这一报告，适合正在学习数据结构、需完成栈实验或复习表达式求值算法的学生作为参考与仿写范例，也可作为课程设计素材。

1. 中缀表达式求值：双栈模型是这份实验报告的核心资产

中缀表达式求值，说白了就是让程序像人一样读“9+(3-1)*3+10/2”这种式子，不光要算出结果，还要把括号和优先级都处理对。你手头的这份《数据结构实验报告-栈与队列-中缀表达式求值》就是干这个的：从键盘读进一个以“#”结尾的中缀表达式，用运算符栈和操作数栈两个栈一进一出，最终打印出整型结果。它不是纯玩具代码，而是完整覆盖了栈的初始化、销毁、出入栈、优先级比较和一元负号处理的C语言实现，适合正在学栈与队列、准备数据结构实验的人拿来回填和理解。

我当初第一次看到这类实验题时最大的困惑是“为什么要搞两个栈，一个栈不能算吗”。后来动手写完才发现，一个栈根本存不下两类信息：数字要等运算符，运算符要等优先级。这篇博文我就按“这是什么→原理→代码走读→踩坑→验收→扩展”的顺序拆给你看，代码直接来自报告原文，我会在关键行标注容易翻车的位置。需要完整报告文档的，文末有获取方式。

2. 双栈求值的原理：运算符优先级表与isp/icp机制

2.1 为什么必须用两个栈：操作数和运算符的生命周期不同

中缀表达式的核心难点在于“运算符要等”。给你一个“1+2*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--”，这是最朴素的数组栈实现。参数说明：M=25是栈最大容量，意味着表达式长度和中间结果深度不能超过这个规模，超了就栈溢出。

我一般会提醒一句：这两个栈的容量定成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则压栈，否则弹出栈顶运算符并执行计算，这就是算符优先算法最简形态。

这份优先级表是括号处理正确与否的分水岭。很多同学会问为什么不直接用一个统一优先级表，答案在于左括号的“双重身份”：它在等待匹配时是屏障，在被匹配时必须立刻让步。网上大量翻车代码都是把左括号优先级写死，结果出现“((1+2)*3”这种输入时运算顺序乱套。

2.3 哨兵“#”是整个算法的锚点

运算符栈在计算开始前就压入一个“#”，它是处理表达式结束的标志，也是避免空栈访问的保护伞。主循环条件是“当前读到的字符不是#或栈顶不是#”，这意味着只有输入遇到结束符且运算符栈被清到只剩#时，循环才终止。

PushTR(tr, '#'); g = getchar(); while(g != '#' || GetTopTR(tr) != '#') { // 主处理逻辑 }

逻辑说明：因为压入了#，第一次比较运算符优先级时isp('#')返回0，icp(任何运算符)至少是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; // 继续下一轮，不读新字符 } }

逻辑说明：i<j时说明新运算符应该“压住”栈顶运算符，比如栈顶是+，新来的是*，则*压栈。i>=j时则弹出栈顶运算符并执行一次二元运算。有个关键细节：当弹出的是左括号且优先级相等时，这段代码不做操作也不压栈，相当于把左括号丢弃并继续循环，这是括号匹配的精髓。参数说明：if(h!='(' && i==j || i>j)这个条件写得不够工整，我拆开看是“(h不是左括号且i==j)或i>j”才做运算，右括号出现时i==j且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 '/'执行的是y=x/y，这是C语言的整数除法，结果自动截断小数。但在用这个代码做验算时，如果你拿Python或者计算器对比，得到的数值天然不同。

解决：先确认实验要求，标题是“中缀表达式求值”，不是“浮点计算器”，整型结果是设计目标而非缺陷。如果你确实需要小数结果，可以修改StackND的elem类型为double，然后Connect函数的参数与返回类型全部同步为double，压栈和出栈操作也一并调整，但这会大幅改动代码量，需要评估是否值得。

4.2 一元负号只在特定位置生效导致“--2”这类表达式算错

现象：输入“--2”或“1--2”这类连续负号表达式时，程序输出结果和数学期望不一致，甚至是0。

原因：k的标记机制只处理“运算符后紧跟负号”的情况。输入“--2”时，第一个“-”被识别为负号，k='!'，紧接着读第二个“-”，此时上一个字符l已经变成“-”了吗？实际循环里l=g赋值发生在continue之前，所以第二个“-”会被当成新的运算符来参与优先级比较，本质上是把“负负得正”这种语义丢了。

解决：如果实验要求没有强制处理连续一元运算符，建议避开这类测试用例，或是在测试报告里注明该程序实现的是“单次一元负号”语义。如果确实需要支持，可以在识别到k='!'且当前字符又是'-'时，把k重置为正常状态，并继续向后读，相当于两个负号抵消。

4.3 多位数字合并与负号组合出现拼数错误

现象：输入“123+4”结果正确，但输入“-123+4”时得到的结果像是“12”和“-3”被拼成了“12-3”。

原因：Getnum的负数分支返回10*x-y，这只适用于“x为负数，y为正数”的拼接。但在当前代码流程里，负号标记k='!'是先设好，等读到下一个数字时才把负值压栈，一旦出现“-123”这种连续三位数，第一次拼接时x传入的是-1，y传2，Getnum(-1,2)返回-12，没问题；但第二次拼接时x=-12，y=3，Getnum(-12,3)返回-123，也没问题。真正出错的是当负号出现在合并过程的中间时，比如“12-3”会被拼成“12-3”，这里的“-”被识别成负号还是减号，取决于它前面的字符l是不是运算符。

解决：不要试图通过修改Getnum来兼容所有情况。在我的使用经验里，这个代码最稳妥的用法就是“一个数对应一个完整的分词过程”，不要让它去处理“数字中间夹负号”这种场景。你的测试用例设计应该让每个操作数之间都有明确的运算符分隔。

4.4 栈容量固定导致长表达式内存越界

现象：输入一个很长的表达式（比如超过25个运算符加操作数），程序运行到一半跳出或者打印出离谱的随机值。

原因：两个栈的最大容量是M=25，while循环里没有栈满检查。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 必测的七类表达式用例

实验老师批阅时主要靠测试输入输出判断正确性，所以你交给老师的“程序测试简要报告”部分需要覆盖足够的输入类型。下面这张表是我按照基本要求和提高要求整理的最小用例集：

逻辑说明：第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 把固定容量栈改为动态扩容栈

原代码最大痛点是栈容量写死M=25，我把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#”，分别验证空数据、纯括号、除零边界。这三个用例过了，代码至少能在基础场景站住。希望这份拆解能帮你在实验报告上少走点弯路，也希望你能把这份代码真正变成自己的东西。

本文还有配套的精品资源，点击获取