企业官网建设流程全解析

简介：一份面向西南交通大学计算机专业学生的数据结构实验报告，围绕栈与队列在中缀表达式求值中的应用展开。实验需从键盘输入中缀表达式，通过操作数栈与运算符栈实现加、减、乘、除以及括号运算；基础要求支持0～9操作数，提高要求扩展至任意整数及一元正负号。报告完整呈现了数据结构设计、算法流程、运算符优先级比较、动态内存分配栈的构建思路，并附有可直接运行的C语言源代码和程序测试报告，既能帮助读者掌握堆栈的典型应用，也可作为实验报告写作与代码注释的参考范本。文档以docx格式压缩于单个文件内，大小仅51KB，内容精炼但覆盖实验要求、设计、代码与测试全流程，目前已有2899人学习查看，适合数据结构课程学习者及需要完成同类实验的学生借鉴。

1. 为什么放着“直接算”的念头，中缀表达式求值非要绕栈和队列这一圈

“数据结构实验报告-栈与队列-中缀表达式求值”这类题目，几乎每个开数据结构课的专业都会布置一次。你很可能已经知道核心思路是“用栈”，但很多人把实验做成了“扫描字符串硬算”，遇到括号和优先级就堆一大坨 if-else，最后连自己都说不清程序凭什么是对的。这个实验的正确打开方式，是把中缀表达式先转成后缀表达式（逆波兰式），再用队列把后缀表达式缓存起来，最后用一个栈完成求值。栈负责“暂时算不了的东西”，队列负责“等会儿依次要算的东西”，两边分工明确。这篇笔记按“规则推演 → C 代码 → 报告写法 → 踩坑 → 验证”的顺序讲，适合正在写实验报告、期末复习数据结构，或者准备王道 408 统考的读者照着做一遍。

2. 中缀转后缀表达式：拿一个例子把栈的推演规则走通

2.1 为什么后缀表达式天生就是“栈的舒适区”

中缀表达式3 + 4 * 2的问题在于：读完整串才知道4 * 2要先算，也就是说“运算符的生效时机”和“它出现的时机”不同步。人脑靠肉眼和经验处理，程序没有这种直觉，所以必须借助一个后进先出的结构，把暂时不能生效的运算符压住，等条件满足再弹出来。这就是栈出现在这个实验里的根本原因。

后缀表达式则完全不同。它没有括号、没有优先级，求值顺序完全由位置决定：从左到右扫描，遇到数字压栈，遇到运算符弹出两个数字算完再压回去。整个过程不需要回看，不需要比较优先级，每一步都是机械操作。于是“中缀转后缀 + 后缀求值”这个两阶段方案，把一个需要全局判断的问题，拆成了两个只需要局部判断的问题。

可能有人会问：既然求值这么简单，那队列是干什么的？答案在“两阶段”这三个字里。中缀转后缀的结果是一串有顺序的 Token，这串 Token 要先完整地存下来，再交给求值阶段逐个消费。这个“先到先处理”的存储角色，正是队列的典型场景。如果边转后缀边求值、只用一个栈，程序也能跑，但那就把队列从实验里抹掉了，也和“实验内容及要求”里明确点名栈与队列的意图不符。

顺带说一个对比：王道数据结构教材里讲到表达式求值时，给的是“运算符栈 + 操作数栈”双栈边转边求的方案，那个方案少一次遍历、省内存，但讲课时很难把“运算符栈的弹出时机”讲干净。日常实验我更推荐两阶段方案，因为每一步都能打印出“当前运算符栈”和“后缀队列”，答辩时老师问起来，你能很直观地解释程序在做什么。

2.2 手推一遍3 + 4 * 2 - ( 1 + 2 ) / 3：规则不是背的，是走出来的

我建议你拿笔在纸上跟一遍这个过程，比直接看代码有用得多。下面这个表达式的完整推演，覆盖了四种关键情况：普通运算符、括号、同优先级相遇、扫描结束后的清栈。

最终后缀表达式：3 4 2 * + 1 2 + 3 / -

求值时从左到右扫：压入 3、4、2；遇到*弹出 2 和 4 得 8，压回；此时栈里 3、8；遇到+弹出 8 和 3 得 11；再压 1、2，遇到+得 3；压 3，遇到/得 1；最后遇到-，弹出 1 和 11，得到 10。整个过程一遍跑完不回头，这就是后缀表达式和栈的默契。

2.3 优先级表怎么设计：栈内栈外两套优先级别偷懒

优先级规则是转后缀时“弹栈与否”的唯一依据，但括号打破了普通运算符的对称性。同一个(，在栈外要表现得“极高”，遇到它必须无条件入栈；一旦进了栈，又要表现得“极低”，排在它上面的普通运算符已经全被弹走了。所以不能只给(定一个固定优先级，正确做法是区分“栈内”和“栈外”两个状态。

// 返回运算符优先级；inStack 为 1 表示该运算符已在运算符栈中 int priority(char op, int inStack) { if (op == '+' || op == '-') return 1; if (op == '*' || op == '/') return 2; if (op == '(') return inStack ? 0 : 3; return -1; // 非法运算符 }

这段代码把(的栈外优先级设为 3，高于*/；栈内优先级设为 0，低于所有普通运算符。配合弹栈条件peek >= current使用：当栈顶是(且 inStack 为 1 时，priority 返回 0，任何普通运算符的优先级都 >= 0，按条件应该弹出(，那就错了。

我一般把弹栈条件分两层去理解：普通运算符之间，用栈内优先级 >= 当前优先级决定弹出；(则只在遇到)时才被弹出。这么写虽然 priority 函数里(的栈内优先级没被弹栈条件使用，但保留它能让代码语义更完整，也能让读报告的评分老师一眼看出你考虑过栈内栈外区别的问题。还有一点：>=这个细节决定了相同优先级运算符的结算顺序。3 - 2 + 1里-入栈后，遇到+，如果不弹-直接压+，后缀会变成3 2 1 + -，算出来是 0，正确答案是 2。用>=保证优先级相同时先结算旧的，符合左结合规则。如果你的实验要求里额外支持^（幂运算），它是有结合性的，弹栈条件要单独改成>。这一步是加分项，也是很多人在报告里被追问的地方，建议提前准备一句解释。

3. 用 C 语言实现：两栈一队列的完整代码与参数说明

3.1 数据结构选型：Token 结构、运算符栈、操作数栈、队列

写代码前先把数据结构的“形状”定下来。本实验一共需要三种容器：一个存运算符的字符栈、一个存数字的双精度栈、一个存 Token 的队列。Token 是一个小结构体，分别标记“这是数字”还是“这是运算符”，避免用同一个数组装不同类型的数据时还要反复判断。

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #include <math.h> #define MAX 128 typedef struct { int type; // 0：数字，1：运算符 double num; // type == 0 时有效 char op; // type == 1 时有效 } Token; typedef struct { char data[MAX]; int top; } CharStack; typedef struct { double data[MAX]; int top; } NumStack; typedef struct { Token data[MAX]; int head, tail; } TokenQueue;

队列这里用循环顺序队列，MAX 取 128。中缀转后缀后括号消失，Token 总数只会比原字符串的可见字符数少，不会更多，所以顺序队列完全够用。后面的代码不写动态扩容，一方面是为了让实验报告更聚焦在栈和队列本身，另一方面也避免链表实现的指针操作把优先级逻辑的篇幅挤掉。

3.2 核心一：中缀转后缀，连负号一起处理

下面这个函数是本实验最关键的部分。请留意我处理“负号”的方式：-可能是减号，也可能是一元负号，比如-3 + 2和1 - -3。很多代码把-一律当二元运算符，遇到(-3)这种输入就崩。

// 判断表达式当前位置的前一个有效字符是不是数字或右括号 // 如果是，则当前 '-' 是减号；否则是一元负号 int isPrevNumber(const char* p, const char* start) { const char* q = p - 1; while (q >= start && *q == ' ') q--; if (q < start) return 0; if (isdigit((unsigned char)*q) || *q == ')') return 1; return 0; } void convertToRPN(const char* expr, TokenQueue* rpn) { CharStack opStack; opStack.top = -1; const char* p = expr; while (*p != '\0') { if (*p == ' ') { p++; continue; } // 负号不是减号：直接 C 库函数解析后面的数字，连同符号一起入队 if (*p == '-' && !isPrevNumber(p, expr)) { char* end; double v = strtod(p, &end); if (end == p) { fprintf(stderr, "非法输入\n"); exit(1); } enqueue(rpn, (Token){0, v, 0}); p = end; continue; } // 数字或多位数、小数：用 strtod 一次取完 if (isdigit((unsigned char)*p)) { char* end; double v = strtod(p, &end); enqueue(rpn, (Token){0, v, 0}); p = end; continue; } char op = *p; if (op == '(') { pushChar(&opStack, op); // 栈外优先级最高，无条件入栈 } else if (op == ')') { while (!isCharEmpty(&opStack) && peekChar(&opStack) != '(') { enqueue(rpn, (Token){1, 0, popChar(&opStack)}); } if (isCharEmpty(&opStack)) { fprintf(stderr, "括号不匹配\n"); exit(1); } popChar(&opStack); // 丢弃左括号本身 } else { while (!isCharEmpty(&opStack) && priority(peekChar(&opStack), 1) >= priority(op, 0)) { enqueue(rpn, (Token){1, 0, popChar(&opStack)}); } pushChar(&opStack, op); } p++; } while (!isCharEmpty(&opStack)) { enqueue(rpn, (Token){1, 0, popChar(&opStack)}); } }

逐段解释：

• strtod(p, &end)是 C 标准库自带的字符串转浮点函数，能自动处理前导空格、正负号、小数点。end指向第一个无法解析的字符，用它跳过整段数字，比手动拼字符省心得多。
• 负号分支的判断依据是“前一个有效字符”。1--3中，第一个-前是1，判定为减号；第二个-前是运算符-，判定为一元负号，strtod 会把-3整体解析成数字并入队。如果偷懒用“前一个入队 Token 是不是数字”来判断，在1 - -3这种场景会因为栈状态不同而误判，建议直接看原字符。
• (入栈前不比较优先级，这是规则，不是优化。while弹栈条件里priority(peekChar, 1)和priority(op, 0)一个查栈内优先级，一个查栈外优先级，两个参数都要写对，网上不少代码把 inStack 参数固定成 1，导致(的处理出错。
• 扫描结束后，栈里剩余运算符必须全部弹出入队。漏掉这一步，结果会差一个运算符，而且极难排查。

3.3 核心二：后缀表达式求值，弹出的顺序决定了减法和除法的符号

后缀求值的代码比转换简单得多，但有一个细节最容易翻车：弹出两个操作数时，先弹出的是右操作数，后弹出的是左操作数。减法要用左 - 右，除法要用左 / 右。很多人写成a - b，但 a 和 b 的赋值顺序一旦反过来，3 4 -会算成 1 而不是 -1。

double evaluateRPN(TokenQueue* rpn, int verbose) { NumStack vs; vs.top = -1; while (!isQueueEmpty(rpn)) { Token t = dequeue(rpn); if (verbose) { if (t.type == 0) printf("%g ", t.num); else printf("%c ", t.op); } if (t.type == 0) { vs.data[++vs.top] = t.num; } else { if (vs.top < 1) { fprintf(stderr, "表达式不合法\n"); exit(1); } double b = vs.data[vs.top--]; // 先弹出的是右操作数 double a = vs.data[vs.top--]; // 后弹出的是左操作数 switch (t.op) { case '+': vs.data[++vs.top] = a + b; break; case '-': vs.data[++vs.top] = a - b; break; // 一定是 a - b case '*': vs.data[++vs.top] = a * b; break; case '/': if (fabs(b) < 1e-9) { fprintf(stderr, "除零错误\n"); exit(1); } vs.data[++vs.top] = a / b; break; } } } if (vs.top != 0) { fprintf(stderr, "表达式不合法\n"); exit(1); } return vs.data[vs.top]; }

这里把printf("%g ", ...)放在遍历队列的同时进行，等于把“后缀表达式的输出”和“求值”合并成一次遍历。报告里既能展示队列里存的完整后缀序列，又不用再复制一份队列。verbose参数建议保留，调试时传 1，正式测试时传 0，比注释掉打印语句干净。

除零检查用的是fabs(b) < 1e-9，而不是b == 0。因为操作数本身就是 double，0.0可以精确表示，但经过运算得到的中间结果，比如(1.0 / 3.0) * 3.0 - 1.0，在二进制里可能留下极小误差。用精确等于判断会漏掉一些本应报错的场景，用绝对值阈值更符合浮点语义。

3.4 辅助打印函数：把运算符栈和后缀队列实时打出来

调试这个实验，最大的痛苦是“程序跑完了，但你不知道栈里发生了什么”。我习惯写一个队列快照函数，参数用值传递而不是指针——C 语言里结构体按值传参会在函数内产生副本，出队操作只影响副本，不会破坏原队列。这个技巧能让调试代码非常短。

void dumpQueue(TokenQueue q) { // 注意：值传递，函数内出队不影响原始队列 printf("后缀队列: "); while (!isQueueEmpty(&q)) { Token t = dequeue(&q); if (t.type == 0) printf("[%g] ", t.num); else printf("[%c] ", t.op); } printf("\n"); }

在convertToRPN的 while 循环里适当位置插入dumpQueue(*rpn)，就能看到每一步入队后队列的变化；同理可以写一个打印运算符栈的函数。这比 debugger 单步更快，也更适合写进实验报告作为“调试过程”展示。

4. 实验报告怎么写：从“实验内容及要求”拆出五段式可答辩的结构

4.1 先把“实验内容及要求”拆成功能点清单

大多数实验指导书给出的要求是：输入一个中缀表达式，输出计算结果，要求利用栈实现，表达式可包含加、减、乘、除和括号。这行字看起来简单，但拆成可测试的功能点，至少包含：支持多位数；支持十进制小数；支持负数；支持嵌套括号；支持在除零和括号不匹配时报错并退出。

把这些功能点列进报告的“实验内容分析”段落，会让评分老师觉得你读懂了题目，而不是上来就贴代码。我一般会建议在报告里画一张不超过五行的小表：

表格的价值在于把“栈和队列分别承担什么角色”一句话讲完。这是整个实验报告的灵魂：栈管临时不可算的运算符和操作数，队列管转译后的待处理序列。

4.2 五段式报告，每一段的“字数配额”

普遍接受的实验报告结构是五段：实验目的、实验内容与要求、实验原理与算法设计、运行结果与测试、实验总结与体会。实验原理与算法设计这段要占全篇的 40% 左右，运行结果占 30%，其余三段共 30%。

• 实验目的，写三条就够：掌握栈的后进先出特性在表达式处理中的应用；理解队列对中间结果有序缓存的作用；熟悉中缀、后缀表达式转换规则。不要抄书上的“通过本次实验，使学生深刻理解……”这类套话，直接写能力目标。
• 实验内容与要求，重点写“你对题目的拆解”，也就是 4.1 里那张功能点清单。
• 实验原理与算法设计，这是重头戏。先写一句“本实验采用两阶段方案：中缀转后缀，再对后缀求值”，然后放一段伪代码。伪代码没有语法负担，反而能把栈和队列的分工画清楚：

扫描中缀表达式的每个字符 t： 若 t 是数字 → 入 suffix 队列 若 t 是 '(' → 入 op 栈 若 t 是 ')' → op 栈弹到 '('，弹出的运算符依次入 suffix 队列 若 t 是普通运算符 → 当 op 栈顶优先级 >= t 优先级时，栈顶出栈入 suffix； 然后 t 入 op 栈 扫描结束 → op 栈剩余全部出栈入 suffix 遍历 suffix 队列： 数字 → 压入 num 栈 运算符 → 弹出右操作数 b、左操作数 a，计算 a op b，结果压回

这段伪代码直接复制到报告里也不会显得敷衍，它比贴完整 C 代码更容易让读者看懂，因为剔除了 strtod 和边界判断的干扰。之后再把第 3 章的核心代码按“栈和队列的基本操作实现”“转换函数”“求值函数”三段贴出，并逐段配一两句话说明。

4.3 运行结果与测试：三件套截图与测试用例设计

运行结果部分最常见的错误是只截一张“输入表达式、输出结果”的图。在栈与队列这个实验里，老师更想看到的是过程证据。我建议至少准备三张截图：第一张是普通四则运算表达式的完整过程；第二张是嵌套括号和小数的表达式；第三张是异常输入（除零或括号不匹配）时的报错信息。

测试用例不能只挑“看起来顺眼”的表达式。下面这组用例是我每次交给学生的检查清单，覆盖面足够证明程序不是只写了 happy path：

如果你想拿高分，在“实验总结”里写一句“本实验的结果均通过批量对拍验证，正确性不是仅凭几组手工用例断言的”，然后放第 6 章的对拍脚本和运行结果。这一句能让报告的说服力上一个台阶，因为大多数同学只做了手工测试。

5. 常见问题与避坑：5 个让程序或报告翻车的细节

5.1 负号被当成减号，程序直接崩

现象：输入-3 + 2，程序要么报错，要么算出一个莫名其妙的大数。

原因：把-一律按二元运算符处理。表达式开头的-没有左操作数，弹栈时vs.top < 1触发了“表达式不合法”分支。这是中缀转后缀实现里最常见的坑。

解决：用“前一个有效字符”判断-的属性。前一个有效字符是数字或右括号，说明它是减号；否则它是一元负号。第 3.2 节的isPrevNumber函数就是干这个的。报告里一定要把这个判断单独写出来，因为评分老师通常会拿-3+2这种用例去试你的程序。

5.2 括号不匹配时没报错，程序静默算错

现象：输入( 1 + 2，程序没有提示错误，反而输出了结果。

原因：while循环把栈弹空也没遇到(，代码却没有检查栈是否为空，导致右括号丢失后程序继续往下跑。这个 bug 的特点是“有的表达式错，有的表达式对”，排查起来特别费劲。

解决：在弹出)的处理里，while结束后立刻检查isCharEmpty(&opStack)，为空就输出“括号不匹配”并退出。同样地，表达式扫描完但栈里还有(，也要报错。这个分支只有几行代码，但能让程序从“大概率正确”变成“对非法输入可预期地失败”。

5.3 除法结果变成整数，或者除零返回 inf

现象：输入7 / 2，程序输出 3 而不是 3.5；输入1 / 0，程序输出inf甚至直接崩。

原因：操作数栈定义成int类型；除零前没有检查除数。前者在实验报告代码里很常见，因为很多人为了省事把数字栈和运算符栈都定义成字符数组。

解决：数字栈一律用double，入队和出队都走 Token 的num字段。除零检查用fabs(b) < 1e-9而不是b == 0。另外说一个 C 语言特有的坑：如果实验要求里允许负数除法，C99 的整数除法是向零截断的，-7 / 2结果是-3，而 Python 的整数除法是向下取整，结果是-4。用 double 全程计算可以避开这个语义差异，这也是不推荐用 int 栈的另一个理由。

5.4 扫描结束后忘清空运算符栈，后缀表达式越算越短

现象：输入1 + 2，输出后缀只有1 2，结果变成 1 或直接报错。

原因：转换函数的主循环结束后，栈里剩余的运算符没有弹出。1 + 2扫描完时，+还在运算符栈里，没有被送进后缀队列，求值阶段自然就少了一个运算符。

解决：convertToRPN末尾一定要接一个while (!isCharEmpty(&opStack)) enqueue(...)。这个和 5.2 的括号检查一起，构成转换函数的收尾双保险。还有一个连带注意事项：修改代码时如果提前return，要确认收尾代码一定被执行到，建议把收尾逻辑放在主循环结束后、函数返回前，不要放在某个 if 分支里。

5.5 队列容量开太小，表达式一长就错乱

现象：测试短表达式一切正常，把表达式加长到 60 个字符后，后缀表达式末尾几个 Token 丢失。

原因：顺序队列容量定义成 50 或 100，转后缀时虽然 Token 总数不会超过原字符串可见字符数，但连续运算符和括号的交替会让队列峰值逼近上限。加上循环队列的tail追上head时，新元素会覆盖旧元素，结果就是“越长的表达式错得越离谱”。

解决：直接把MAX开到 128 或 256，实验规模下足够。如果想让代码更严谨，可以把队列容量设置成strlen(expr) + 1，在初始化时分配。报告里写清楚为什么不用链队列：本实验 Token 总数上界可预估，顺序队列实现更简单，指针操作反而引入新的出错点。这个理由在答辩时也能站住脚。

6. 验证算法正确性：批量断言与随机表达式对拍

6.1 把固定用例写成断言，一键检查

程序写完后别急着在命令行一条条手敲用例。把测试用例和期望结果写成一个函数，每次改完代码直接跑一遍，能省下大量时间。

void runSingleTest(const char* expr, double expected) { TokenQueue rpn = { .head = 0, .tail = 0 }; convertToRPN(expr, &rpn); double got = evaluateRPN(&rpn, 0); if (fabs(got - expected) < 1e-9) { printf("PASS: %s = %g\n", expr, got); } else { printf("FAIL: %s 期望 %g 实际 %g\n", expr, expected, got); } } int main(void) { runSingleTest("1 + 2", 3); runSingleTest("3 + 4 * 2", 11); runSingleTest("3 + 4 * 2 - ( 1 + 2 ) / 3", 10); runSingleTest("-3 + 2", -1); runSingleTest("1 - -3", 4); runSingleTest("1.5 * 2 + 0.5", 3.5); return 0; }

注意evaluateRPN(&rpn, 0)这里传 0，关闭过程打印，只保留 PASS/FAIL 输出。fabs(got - expected) < 1e-9是对浮点数做断言的统一做法，直接比较相等会偶发失败。

6.2 用 Python 随机生成表达式，和 eval 对拍

固定用例能抓低级错误，但抓不出“优先级表在某种少见组合下错位”的问题。这一步我用 Python 随机生成大量合法表达式，再调用编译好的 C 程序，拿结果和 Pythoneval的结果比对误差。对拍不是自动化测试的替代品，它是验证“实现与另一个独立实现结果一致”的手段。

import random import subprocess import sys def gen_expr(depth=0): if depth >= 3 or random.random() < 0.4: return str(random.randint(0, 20)) r = random.random() if r < 0.3: return f"( {gen_expr(depth+1)} + {gen_expr(depth+1)} )" elif r < 0.5: return f"{gen_expr(depth+1)} - {gen_expr(depth+1)}" elif r < 0.7: return f"{gen_expr(depth+1)} * {gen_expr(depth+1)}" else: b = gen_expr(depth+1) while b == "0": b = gen_expr(depth+1) return f"{gen_expr(depth+1)} / {b}" for i in range(10000): expr = gen_expr() expected = eval(expr.replace("/", " / ").replace(" [ ", " = ")) proc = subprocess.run(["./calc"], input=expr + "\n", text=True, capture_output=True) if proc.returncode != 0: print("CRASH:", expr, proc.stderr) sys.exit(1) out_line = [line for line in proc.stdout.splitlines() if line.startswith("计算结果")] got = float(out_line[0].split(":")[1]) if abs(got - expected) > 1e-6: print("MISMATCH:", expr, "expected", expected, "got", got) sys.exit(1) print("all passed")

几点说明：gen_expr故意只生成加减乘除和括号，把除号右侧的数生成为非零，避免 eval 抛 ZeroDivisionError 干扰对拍；表达式里的空格让 eval 能正确解析负号和中缀；子进程调用./calc时，C 程序的fgets会完整读入一整行，适合这种“一表达式一进程”的对拍方式。浮点误差阈值放宽到1e-6，因为随机生成的除法会有不可精确表示的循环小数，1e-9可能偶尔误报。

这个脚本在你改完优先级表、想确认没有破坏已有功能时非常值钱。我自己的习惯是：代码每改动一次，先跑固定断言，再跑一轮 1 万条随机对拍，全部通过才把代码贴进实验报告。报告里放一张对拍结果的截图，比任何“我觉得没问题”都有说服力。

6.3 把每一步栈状态打出来，亲手核对一遍

批量对拍验证的是“结果对不对”，但它不能让你理解“过程为什么对”。我建议最后一次核对时，选一个中等复杂的表达式，打开verbose模式跑一遍，把每一步的运算符栈和后缀队列写下来，和 2.2 节的手推表逐行对比。这一步虽然耗时，但对数据结构实验来说是值得的：它逼你亲手验证“什么时候弹出、什么时候压栈”的规则，而不是只对着最终结果猜。

我最开始做这个实验时，图省事直接扫字符串硬算，括号和优先级写了快 60 行 if，换一种嵌套方式就翻车。后来老老实实按“中缀转后缀 + 后缀求值”的重构思路，核心逻辑反而只剩 40 行，剩下的时间全花在调试负号和括号匹配上。从那以后我养成一个习惯：凡是涉及栈的算法，先在纸上手推一组例子，再写代码。建议你也试试，希望帮到你。

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