中缀表达式求值实验全解析：栈与队列的实现与避坑指南

简介：资源为“数据结构实验报告·栈与队列·中缀表达式求值”配套文档，适合高校计算机专业学生完成数据结构课程实验或复习栈的应用。内容涵盖实验内容与要求、数据结构与算法设计、函数模块说明、程序测试及C语言源代码，重点讲解运算符栈与操作数栈的协作、isp/icp优先级比较、括号与正负号处理、整数除法截断等实现细节。包内共1个docx文档，约51KB，便于直接查看和编辑。文档从基础要求到提高要求逐层展开，既能帮助入门者掌握中缀表达式求值流程，也为需要完成实验报告或代码设计的读者提供了完整参考。当前已有2899人浏览学习，适合作为课程实验的参考资料，也可用于复习栈与队列在表达式求值中的典型应用。

1. 中缀表达式求值实验：题目在考栈，队列为什么也要出现在报告里

中缀表达式求值几乎是每次数据结构实验必考的应用题，这份以“栈与队列”为题的实验报告，核心就一件事：把2+3*(4-1)这样的中缀表达式，用栈转换成后缀表达式，再用栈求出结果。考的不是代码能不能跑，而是你懂不懂栈的“先进后出”为什么恰好匹配运算符优先级，以及队列在这个过程里到底能承担什么角色。适合正在写实验报告想拿高分的学生，也适合想用一个晚上把这份实验彻底弄明白的自学者。下面按实验报告的完整结构，把原理、代码、测试和踩坑一次讲透，保证你能直接照着复现。

2. 为什么中缀转后缀和求值都必须用栈：从两个栈的设计说起

2.1 手推 2+3*(4-1)：看栈到底在压什么

我一般不在报告开头直接贴代码，先手推三组用例。中缀转后缀的经典算法叫调度场算法，核心是两张优先级表：isp（栈内优先级）和 icp（栈外优先级）。规则只有四条：数字直接输出；运算符 x 与栈顶 y 比较，若 icp(x) 大于 isp(y)，x 入栈，否则弹出 y 并输出；左括号直接入栈；右括号把栈内运算符一直弹出，直到遇到左括号。

手推2+3*(4-1)：数字 2 输出；+压栈；3 输出；*的 icp 是 4，大于栈顶+的 isp 3，压栈；左括号压栈；4 输出；-的 icp 是 2，大于栈顶(的 isp 1，压栈；1 输出；遇到右括号，弹出-和(；表达式读完，依次弹出*和+。最终后缀串是2 3 4 1 - * +。

这里最关键的一点：栈的先进后出正好承担了“运算符先压住，等右操作数算完再出来”这件事。*比+后进栈，却比+先出栈，所以乘法先于加法执行，括号内减法更先执行。这就是中缀转后缀必须用栈的根本理由——运算符的优先级结构本质上是一个嵌套括号结构，天然匹配栈的后进先出。对照《大话数据结构》和考研资料里关于栈的章节，中缀转后缀都被列为必背算法，不是因为它难，而是因为它把栈的“延迟输出”特性用到极致。

2.2 优先级表的设计：两个细节容易被扣分

isp 和 icp 为什么要两套数值？因为同一个运算符在栈内和栈外的优先级不同。以加减乘除为例，栈外 icp 依次是 2、2、4、4，栈内 isp 依次是 3、3、5、5。左括号栈外 icp 是 6，栈内 isp 是 1，右括号栈外 icp 是 1，栈内 isp 是 6。这套设计保证了两个效果：一是新来的运算符能压住栈里优先级更高或相等的运算符，二是左括号进栈后，括号内部的运算符依然能正常压栈，右括号到达时又能把括号内所有运算符一次性弹出。

如果只设一套优先级，(1+2)*3就会出问题：左括号进栈后，+的优先级如果小于等于栈顶，永远压不进去，括号内部的表达式直接算错。报告里这一张优先级表可以直接照抄，但要在表下加一句说明：#是栈底哨兵，作用是让清栈操作有一个明确的终止条件。部分实验要求支持取模%，它的优先级和乘除相同；乘方^涉及右结合，isp 和 icp 规则更复杂，普通实验课不建议加，加了反而要处理2^3^2到底是算(2^3)^2还是2^(3^2)的争议。

2.3 队列在表达式处理中的三个合理位置：不硬凑才不会被老师盯上

标题写的是“栈与队列”，但经典中缀转后缀算法只显式使用栈。怎么让队列合理出现而不是硬凑功能？我在实验报告里用过三个位置，都站得住脚。

第一，输入缓冲。表达式从控制台读入后，先按字符拆成一个环形队列，转后缀程序每次从队头取一个字符。这样扫描器的结构是“FIFO 顺序消费”，队列的先进先出和表达式从左到右的语义天然一致，而且能顺手把空格过滤掉。第二，后缀表达式缓冲。中缀转后缀的输出先入链队列，求值器再依次出队消费。后缀串本来就是从左到右求值的，用队列承载这个“待处理任务流”，逻辑上没有违和感。第三，只在概要设计里画出来。如果代码实在不想动，可以在报告的概要设计模块单独列一个“输入队列”的数据结构图，说明“若表达式长度固定，环形队列比链队列更省空间”，不写具体实现，老师也不会深究。

原则就一条：报告里明确写队列承担的是“缓冲”或“顺序消费”，不要写“用队列完成中缀表达式求值”，否则答辩时被追问一句“队列先进先出怎么体现运算优先级”，当场就会卡壳。常见做法是选输入缓冲或输出缓冲其中一个真正实现，另一个在设计中画出即可，代码和报告两头都稳。

3. 按实验报告要求逐段拆解“实验内容”：六个段落的完整写法

3.1 需求分析与概要设计：先写清楚输入输出再动手写代码

实验报告第一部分是需求分析，不要写空话。直接写：输入是一个中缀表达式，支持加减乘除和取模、括号、多位数、空格和小数点；输出是转换后的后缀表达式以及最终计算结果；程序对非法表达式要有错误返回，不能直接崩溃。再补一句“操作数使用 double 类型，避免整数除法截断”。

概要设计里列两个数据结构：算符栈（char 类型数组栈）和操作数栈（double 类型数组栈）。如果采纳了 2.3 的输入队列方案，再加一个环形队列。这一节的流程图用 Word 自带的文本框画，主流程四个框：读入表达式、预处理、中缀转后缀、后缀求值，最后输出结果。不要省略流程图，很多报告的评分点就在这里。

3.2 核心代码：中缀转后缀模块，可直接编译的版本

下面这段代码对应报告“详细设计”部分，可以直接放进 C 语言工程编译运行。栈结构用定长数组，MAX 取 100，实验课够用。优先级函数返回 int，数字判断同时支持小数点。

#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX 100 /* 字符栈：用于存运算符 */ typedef struct { char data[MAX]; int top; } CharStack; void InitStack(CharStack *s) { s->top = -1; } int Push(CharStack *s, char c) { if (s->top >= MAX - 1) return 0; s->data[++s->top] = c; return 1; } int Pop(CharStack *s, char *c) { if (s->top == -1) return 0; *c = s->data[s->top--]; return 1; } int GetTop(CharStack *s, char *c) { if (s->top == -1) return 0; *c = s->data[s->top]; return 1; } /* isp：栈内优先级；icp：栈外优先级 */ int isp(char op) { switch (op) { case '#': return 0; case '(': return 1; case '+': case '-': return 3; case '*': case '/': case '%': return 5; case ')': return 6; default: return 0; } } int icp(char op) { switch (op) { case '#': return 0; case '(': return 6; case '+': case '-': return 2; case '*': case '/': case '%': return 4; case ')': return 1; default: return 0; } } /* 数字判断：支持小数点，便于处理 12.5 这类操作数 */ int IsDigit(char c) { return (c >= '0' && c <= '9') || c == '.'; } /* 中缀转后缀：结果写入 postfix，操作数和运算符之间用空格分隔 */ void InfixToPostfix(const char *infix, char *postfix) { CharStack op; InitStack(&op); Push(&op, '#'); /* 栈底哨兵 */ int i = 0, j = 0; char c, top; while ((c = infix[i]) != '\0') { if (c == ' ') { /* 过滤输入中的空格 */ i++; continue; } if (IsDigit(c)) { /* 连续读取一个完整数字 */ while (IsDigit(infix[i])) postfix[j++] = infix[i++]; postfix[j++] = ' '; /* 数字之间必须有分隔符 */ } else { GetTop(&op, &top); if (icp(c) > isp(top)) { /* 新运算符优先级高，入栈 */ Push(&op, c); i++; } else if (icp(c) == isp(top)) { /* 左右括号相遇，弹出左括号 */ Pop(&op, &top); i++; } else { /* 栈顶运算符优先级更高，弹出 */ Pop(&op, &top); postfix[j++] = top; postfix[j++] = ' '; } } } while (Pop(&op, &top) && top != '#') { /* 清空剩余运算符 */ postfix[j++] = top; postfix[j++] = ' '; } postfix[j] = '\0'; }

这段代码的逻辑可以拆成三点说明。第一，postfix[j++] = ' '这句不能省，后缀表达式里数字和运算符全靠空格分隔，否则12+3转出来会变成123+，求值阶段完全无法还原操作数边界。第二，icp(c) > isp(top)是入栈条件，icp(c) == isp(top)只用于左右括号相遇，普通运算符不会出现相等的情况，这是优先级表设计决定的。第三，函数结束后必须有一个单独的 while 循环清空算符栈，很多人把清栈逻辑写在主循环里，最后一位运算符就会神秘失踪，后面避坑章会专门讲。

3.3 核心代码：后缀求值模块与主流程

后缀求值用另一个独立栈，存 double 类型。注意弹出顺序：先弹出的是右操作数 b，再弹出的是左操作数 a，除法必须写成a / b，很多初学者写成b / a，结果整个表达式反了。除零用 ok 标记拦截，不让程序直接崩溃。

/* 数字栈：用于后缀表达式求值 */ typedef struct { double data[MAX]; int top; } NumStack; void InitNumStack(NumStack *s) { s->top = -1; } int PushNum(NumStack *s, double v) { if (s->top >= MAX - 1) return 0; s->data[++s->top] = v; return 1; } int PopNum(NumStack *s, double *v) { if (s->top == -1) return 0; *v = s->data[s->top--]; return 1; } /* 二元运算封装：除零场景通过 ok 返回 0 表达错误 */ double Calc(double a, double b, char op, int *ok) { *ok = 1; switch (op) { case '+': return a + b; case '-': return a - b; case '*': return a * b; case '/': if (b == 0) { *ok = 0; return 0; } return a / b; case '%': if ((int)b == 0) { *ok = 0; return 0; } return (int)a % (int)b; default: *ok = 0; return 0; } } /* 后缀表达式求值：返回 1 表示成功，0 表示表达式非法 */ int EvalPostfix(const char *postfix, double *result) { NumStack st; InitNumStack(&st); int i = 0; char c; while ((c = postfix[i]) != '\0') { if (c == ' ') { i++; continue; } if (IsDigit(c)) { char token[32]; int k = 0; while (IsDigit(postfix[i]) && postfix[i] != '\0') token[k++] = postfix[i++]; token[k] = '\0'; PushNum(&st, atof(token)); /* atof 解析整数和小数 */ } else { double a, b; if (!PopNum(&st, &b)) return 0; /* 操作数不足 */ if (!PopNum(&st, &a)) return 0; int ok; double v = Calc(a, b, c, &ok); if (!ok) return 0; PushNum(&st, v); } } if (PopNum(&st, result) && st.top == -1) return 1; /* 栈里只剩一个值才算合法 */ return 0; } int main() { char infix[128], postfix[256]; double result; printf("输入中缀表达式: "); fgets(infix, sizeof(infix), stdin); infix[strcspn(infix, "\n")] = '\0'; /* 去掉 fgets 留下的换行符 */ InfixToPostfix(infix, postfix); printf("后缀表达式: %s\n", postfix); if (EvalPostfix(postfix, &result)) printf("计算结果: %.4f\n", result); else printf("表达式非法\n"); return 0; }

EvalPostfix 最后有个容易被忽略的校验：PopNum(&st, result) && st.top == -1。这行要求表达式结束后操作数栈里只能剩一个结果。如果输入(1+2这种左括号不匹配的表达式，转后缀阶段会留下未处理的左括号，或者操作数栈里残留多余数字，这里能直接拦下来。main 函数里用 fgets 代替 gets，再用strcspn去掉换行符，很多教材还停留在 gets 的写法，那是 C11 已经移除的不安全函数，实验报告里用了会被扣印象分。

3.4 调试分析与复杂度：报告里必须写的那两段话

调试分析这一节老师会重点看“遇到的问题”，不要只写“没有遇到问题”。把第 5 章里的任意一条踩坑记录搬过来就是现成的素材，比如 fgets 读入表达式会在末尾留换行符，如果不截断，转后缀阶段会把\n当成一个优先级为 0 的运算符，导致栈底#被错误弹出，表现为“合法表达式也报非法”。写清楚现象、原因、解决办法，这一节就充实了。

复杂度分析写给两行：中缀转后缀对表达式做一次线性扫描，时间复杂度 O(n)，n 为表达式字符数；后缀求值同样对后缀串做一次线性扫描，时间复杂度 O(n)；两个栈的总空间不超过表达式长度，空间复杂度 O(n)。报告里最好再加上一句“空格过滤和合法性校验都在一次扫描内完成，不额外增加复杂度”。这句话虽然短，但能明显拉高分。

4. 测试用例设计：让中缀表达式求值在边界上不翻车

4.1 测试用例表：覆盖多位数、空格、嵌套括号和负数

实验报告的测试结果部分最忌只截图一个“运行成功”。测试用例必须覆盖优先级、括号、多位数、空格、除零、非法输入这几类场景，每一条都要写出“输入、期望输出、实际输出、覆盖点”。下面这张表可以直接抄进报告，最后一列写清楚这个用例在测什么，答辩时老师问到任何一行都能答上。

表格里第 8 行要注意：基础版本的代码里除零和语法错误统一返回 0，main 里都打印“表达式非法”。如果想让测试报告更严谨，可以给 EvalPostfix 增加一个错误码参数，用 0 表示语法错误、-1 表示除零错误，main 里按错误码分别打印。这一点在答辩时属于加分项，后面 5.2 会展开说。

负数怎么测？基础版本里把-3+5写成(0-3)+5，就能绕开单目运算符。如果实验要求比较高，要支持直接输入-3+5，需要按 5.3 的方法做单目负号扩展，扩展完再补一组测试用例。报告里如果写了扩展，测试表里一定要有对应行，否则老师一眼看出测试和代码对不上。

4.2 表达式合法性校验：五个崩溃前的拦截规则

合法性校验不需要单独再扫描一遍表达式，在转后缀和求值的过程中顺带完成，省一次 O(n)。五个规则按顺序写进代码里：空串直接报非法；左括号不匹配由转后缀结束后栈里残留(暴露；连续运算符如1++2，会因为第二次扫描到+时栈内没有足够的操作数而求值失败；右括号多余会被icp(c) == isp(top)分支触发，等于号为#时 Pop 失败；除零在 Calc 里拦截。我一般会把第一个字符是*或/这种场景也归为连续运算符同一类，因为它们本质都是“运算符出现在不该出现的位置”。

这五个规则不需要每种都写独立 if，很多是算法天然的行为。比如1++2转后缀能成功，但求值阶段第二个+弹不出两个操作数，返回 0。报告里写测试用例时，把这五类输入都跑一遍，一一对应“表达式非法”的输出，就足够说明程序的健壮性了。

5. 中缀表达式求值避坑：五个最容易让实验报告重写的踩坑记录

5.1 现象：表达式末尾的运算符神秘失踪

输入1+2*3，期望后缀1 2 3 * +，实际输出却是1 2 3 *，加号丢了。第一次遇到这个问题的人很容易怀疑是优先级表写错，其实是转后缀主循环结束后，没有把算符栈里剩余的运算符全部弹出来。很多人把清栈逻辑写在循环体的某个分支里，遇到数字分支直接 continue，清栈语句被跳过；或者把清栈写在 while 外面但写成了只弹一次。

解决方法是单独写一个循环：while (Pop(&op, &top) && top != '#')，把所有非#运算符依次输出。这句话必须在主循环结束后无条件执行一次，不能放在任何分支里。排查时最快的方法是在清栈循环前加一行 printf 打印栈顶，看栈里到底还剩什么。

5.2 现象：除零错误让整份报告现场翻车

输入3/0，程序要么直接崩溃退出，要么输出一个巨大的负数。C 语言里整数除零会触发 SIGFPE 信号，浮点除零会得到 inf，都不是正常结果。很多初学者只在主函数里检查表达式是否合法，压根没想到要在 Calc 层面对除法单独拦截。

解决：Calc 函数的case '/'分支里判断if (b == 0)，置 ok 为 0 并返回。如果要区分错误类型，把 EvalPostfix 的返回类型从 int 改成带错误码的结构体，或者传一个int *err进去，0 表示语法错误，-1 表示除零错误。报告测试部分的截图里如果能分别看到“表达式非法”和“除数不能为零”两种输出，这份报告的测试严谨度就直接拉开差距了。

5.3 现象：单目负号被当成双目减号

输入-3+5，程序把开头的-当成减号，遇到右操作数时弹出栈里不存在的数字，直接报表达式非法。这是中缀转后缀算法最经典的坑，几乎所有初学者都会踩一次。

解决思路：扫描时判断当前-的前一个字符，如果表达式开头，或者前一个字符是运算符或左括号，则当前-是单目负号，而不是双目减号。常见做法是把它压入一个特殊标记，比如@，后缀求值时遇到@只弹出一个操作数取负。如果时间紧张，基础版本完全可以在需求分析里写明“负数请以 (0-负值) 形式输入”，这在实验课上是允许的。但你要是选择了扩展，记得把测试用例表补上-3+5这一行，代码和报告保持一致。

5.4 现象：符号栈和数栈共用一个结构体

有的同学为了省事，用一个typedef struct { int data[MAX]; } Stack同时存运算符和操作数，结果转后缀阶段正常，一到求值阶段拿到乱码。原因是 double 类型被 int 数组截断了，12.5 存进去变成 12，小数位全部丢失，而且字符和数字共用同一个栈会让栈顶判断彻底混乱。

解决：定义两个结构体，CharStack 存 char，NumStack 存 double，代码量多不了几行，但可读性和正确性都远好于一个通用栈。实验报告级别不需要引入 union 或者 void* 这类技巧，那是给代码库设计用的，不是给实验作业用的。两个结构体最大的好处是答辩时一句话就能说清设计意图：运算符栈和操作数栈类型不同，生命周期也不同，必须分开。

5.5 现象：报告只贴代码不贴测试过程

报告里放一大段源码，测试结果只写“运行成功”，没有任何输入输出截图和用例表格。这是实验报告评分最可惜的一种翻车：代码明明写对了，但因为测试部分太空，老师无法判断你是真跑通了还是从网上抄的。答辩时老师现场换一组输入，比如(2+3)*4，你在那里盯着控制台敲了半天，场面会非常尴尬。

解决：测试部分必须给表格，每一行写明“输入、期望输出、实际输出、覆盖点”，把错误用例也放进去，说明你的程序对非法输入有明确响应。截图可以是三张：一张正常表达式、一张多位数小数、一张除零错误。这三张就能覆盖大部分评分点，也足够证明代码不是黑匣子。

6. 从实验报告到答辩：中缀表达式求值还能往哪里问

6.1 双栈直接求值：不生成后缀串的另一种实现

如果老师追问“能不能不转后缀直接求值”，答案是双栈法：操作数栈存数字，运算符栈存运算符，数字直接压数栈，运算符压栈前先把栈里优先级更高或相等的运算符全部取出计算，遇到右括号计算到左括号。核心依然是栈，只是少了对后缀串的中间输出。这个方案和中缀转后缀本质是同一个算法，只是把输出后缀的动作换成了立即求值，答辩时能说出这层关系，说明你理解了原理。

6.2 表达式树与层次遍历：队列的第二个天然角色

把后缀表达式建成表达式树：操作数建叶子节点入栈，运算符弹出两棵子树作为左右孩子，新树再入栈。最后对表达式树做层次遍历，这时候队列就不再是“缓冲”角色，而是真正的算法本体——从根节点开始，逐层从左到右输出。如果实验报告还有“思考与展望”一栏，这一段写进去非常加分，因为它同时用到了栈和队列，和标题完美对应。

6.3 答辩被追问时的三句话准备

被问“为什么不用递归求值”，回答：递归本质也是栈，表达式树和后缀表达式用递归会有一层函数调用开销，显式栈在中缀转后缀场景更直观可控。被问“栈空间不够怎么办”，回答：定长数组栈可以改成链栈，用动态内存分配，代价是每次入栈要 malloc，慢一些但不会溢出。被问“怎么证明计算结果是对”的，回答：转后缀后先把后缀串打印出来，手工按后缀规则演算一遍，再对照结果，这是最笨也最可靠的方法。

我当年第一次交这份实验报告时，只贴了一段完整代码就交上去了，结果答辩老师让我现场跑(2+3)*4，我盯着控制台愣了几秒才意识到自己压根没准备测试数据。后来我养成了一个习惯：任何栈和队列的实验，动手写代码之前先在草稿纸上把三组用例手推完，再对照程序输出，最后才落笔写报告。这个习惯帮我躲过了很多次翻车现场，也会让你这份中缀表达式求值实验报告不用再交第二遍。希望帮到你。

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