栈应用实战：中缀表达式求值的C语言双栈实现与避坑指南

简介：面向西南交通大学数据结构课程‘栈与队列’实验，这份资源是与中缀表达式求值主题配套的完整实验报告。报告逐项给出实验内容要求，基础版覆盖加减乘除四则运算与括号、操作数零至九，提高版增加一元正负号、任意整型操作数及整数相除取整，并完整包含数据结构设计、算法设计、输入输出设计、主要函数说明、测试报告和源程序代码。实现上围绕运算符栈与操作数栈展开，通过栈内外优先级比较决定压栈或运算，使用动态内存分配与栈顶指针管理，代码分函数组织、注释清楚，同时附有各类运算的测试结果。文档保留学号、姓名等占位信息，可作为实验报告模板直接修改。压缩包内为单个docx文件，约51KB，已有2899人学习下载，适合正在学习数据结构、需要完成同类实验报告或深入理解栈与队列应用的读者。

1. 一份能直接交实验的栈应用代码：中缀表达式求值的地基与它的隐藏坑

中缀表达式求值是数据结构课程里栈的经典应用，也是实验报告里出镜率最高的选题之一。手头这份C语言代码，用一个运算符栈加一个操作数栈完成一次扫描求值，核心是isp/icp两套优先级编号：栈外优先级高就压栈，栈外优先级低就弹出计算。它覆盖了实验基本要求的 + - * / 与括号，也实现了提高要求里的一元正负号和任意int操作数，整数除法按C规则截断。适合三类人：要交数据结构实验报告的学生、准备408或考研机试的备考生、想从一份能跑的代码里拆出可复用栈思路的从业者。注意标题里的“队列”在代码里几乎没出场，这份资源真正的主角是栈。后文按“为什么这么设计→主流程怎么走→易错点在哪儿→怎么排查→如何改造成自己的工具”逐层拆开。

2. 双栈结构与isp/icp优先级表：为什么这套设计能支撑任意括号嵌套

2.1 为什么要两个栈：一次扫描背后的“延迟决定”

人算中缀表达式时，会在脑子里滞后处理优先级。看到2+3*4，会先记下+，等3*4算完再回头算2+12。程序没有这种临时记忆，只能拿栈当“记账本”。读到一个运算符时，程序不立刻决定计算，而是先和运算符栈顶比优先级：栈外新来的运算符比栈顶高，说明右边的运算要先做，于是压栈；比栈顶低或相等，说明栈顶运算符该先算，于是弹出栈顶，同时让操作数栈弹出两个数参与计算。

这就是一遍扫描求值的本质：把中缀表达式拆成一段“遇到高优先级就攒着、遇到低优先级就先结算”的序列。它和单调栈处理“左边第一个更大元素”是同一类思想——栈内维持一个有序性，区别在于这里维持的是优先级次序，而且每次比较都发生在栈顶，不需要遍历。

2.2 栈的C实现：动态分配、top=-1与容量M=25

原代码为运算符和操作数分别定义了两个结构体，写法上只有元素类型不同：运算符栈存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.n=M; 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){ e=s.elem[s.top--]; }

top初始化为-1，入栈用++top，出栈用top--，这是顺序栈的标准写法。malloc在堆上分配M个槽位，M定义为25，意味着表达式里同时需要的运算符层数不能超过25。括号嵌套很深、或者连续出现多个一元负号时，要留意这个上限，原代码没有做越界检查，这是实验代码的量级，能跑但别拿极端用例压它。

销毁栈用free释放elem，销毁后结构体变量本身还在，只是elem变成悬空指针。如果销毁后仍调用GetTopTR这类函数，属于未定义行为，调试时容易在莫名其妙的地方崩掉。

2.3 isp与icp：两张优先级表是怎么把括号“安排”明白的

整个算法最核心的一张表长这样：

左括号在栈外优先级最高（4），所以任何左边的运算符都压不过它，括号里的内容必然先入栈；一旦入栈，isp降到1，低于所有四则运算符，括号内的计算就能照常进行，直到等来右括号。右括号在栈外优先级最低（1），意思是它不参与压栈，只用来强制触发弹出；它在栈内优先级是4，一旦它在栈顶，谁都得让位。这两张表的不对称是刻意设计。

验证一下括号配对的核心场景：当栈顶是左括号、新读到右括号时，isp=icp=1，此时i==j成立，但左括号不应触发任何计算，只能被弹出。这个判断在原代码里写成if(h!='(' && i==j || i>j)，C语言里&&优先级高于||，实际含义是((h!='(') && (i==j)) || (i>j)。拆清楚这句话，括号逻辑就通了一半，后面第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，低于所有运算符 g=getchar(); // 读第一个字符 while(g!='#'||GetTopTR(tr)!='#'){ // 主逻辑：数字进操作数栈，运算符比优先级 } PopND(nd,c); // 最终结果 DelStackTR(tr); DelStackND(nd); return c; }

栈底压入#有两个作用。一是作为比较基准，它的isp=0，低于所有真实运算符，保证第一个真正读到的运算符能顺利入栈。二是停机判断：只有输入读到#且运算符栈只剩栈底#，才说明所有运算符都已结算完毕，循环退出。

while条件里用的是逻辑或||，意思是“输入没结束，或者栈没清空”，两个条件同时为假才退出。如果误写成&&，会出现输入已经结束但栈里还剩运算符未计算、程序提前退出的情况，这是自己重写时最容易踩的第一个坑。

3.2 连续数字与一元负号：两个隐藏状态l和k

基本要求里操作数只有0到9，一个数字字符就能用一个int存。提高要求放开到任意整型，就必须把连续读到的数字字符拼成真正的多位数，比如输入12时，先读到1，再读到2，要拼成12。

int Getnum(int x,int y){ if(x<0){ return 10*x-y; } // x已经是负数时，继续接低位 return 10*x+y; // 正常情况：高位乘10加低位 } // 数字分支内： if(!WheOperator(l)){ // 上一个字符也是数字，说明这是多位数 PopND(nd,a); b=Transform(g); // 当前字符转数字 a=Getnum(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='!'; // 标记：下一个数字要取负 g=getchar(); continue; }

l变量记住上一个读入的字符，k变量记住“刚读到一个负号，下一个数字需要取负”。触发条件要求上一个字符也是运算符，这样3-2里的减号不会被误当成负号，因为此时l是数字'3'。如果l初值不设成'-'，表达式开头的负号就无法识别，这也是一个典型翻车点。

3.3 优先级比较落地：i<j压栈，i>=j弹出计算

运算符分支的主体是比优先级然后决定压栈还是计算。

h=GetTopTR(tr); // 运算符栈顶 i=isp(h); // 栈内优先级 j=icp(g); // 栈外优先级，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表示栈顶优先级不低，栈顶运算符可以先结算。比如2+3*4读到*时，栈内是+，isp(2) < icp()(3)，*压栈；读到4后读到#时，栈内是*，isp(3) > icp(#)(0)，先弹*算34，再弹+算2+12。

Connect函数里执行四则运算，减法除法必须注意操作数顺序：先弹出来的是b（右操作数），后弹出来的是a（左操作数），a-b和b-a结果完全不同。Connect的返回类型是char，把int结果塞进char在实验范围内一般不炸，但接近int极限时会出现截断，后面排查章再细说。

4. 括号黑匣子与整数除法边界：把if条件彻底拆开

4.1 右括号的真实流程：为什么同一个右括号会被处理两轮

很多读者卡在这一行if(h!='(' && i==j || i>j)。C语言运算符优先级里&&高于||，所以它等价于：

((h!='(') && (i==j)) || (i>j)

全程用右括号触发。以(2+3)*4为例，读到第一个右括号时，运算符栈顶是+，isp(+)=2，icp())=1，i>j成立，于是弹出+计算2+3，continue回到循环顶部。注意此时g仍然是右括号，没有被重新读入。

第二轮再进入运算符分支，栈顶变成左括号，isp(()=1，icp())=1，i==j成立，但h是左括号，第一个条件h!='('为假，所以不弹操作数。程序进入else分支把左括号弹出栈，右括号自然就被“消费”掉了，随后读取下一个字符。

右括号从头到尾没有压入过运算符栈。它靠“同一个g被continue保留，连续两轮处理”来完成配对：第一轮把括号内剩余运算符结算完，第二轮把左括号弹出。如果自己重写时漏了else分支里的continue，右括号会被当成普通字符进入下一次判断，行为立刻变成死循环或越界。

提示：这段代码读起来像天书，拆开就是两步——右括号先清空括号内的运算符，再弹掉左括号。理解了这个流程，其余分支全是体力活。

4.2 整型操作数与整数除法：C语言截断规则带来的边界

基本要求的操作数只有0到9，提高要求放开到任意int值。操作数栈用int存储，运算直接用y=x/y，除法结果按C语言规则向零截断。

这意味着-7/2得到-3，不是数学上的-4。如果实验报告或测试用例预期的是“向下取整”，需要特别说明；如果按C语言惯例，这反而是正确行为。很多同学只测正整数，看不到这个差异，但提高要求里“整数相除只保留整数商”这句话，其实已经隐含了按C截断规则的意思。

另一个容易忽略的边界是int溢出。两个接近INT_MAX的值相加是未定义行为，INT_MIN取负后仍然是INT_MIN，因为补码表示下负数的绝对值比正数范围大1。代码没有对这些边界做保护，符合实验要求“程序可不处理语法错误”，但想拿高分的话，这两处补上检查是显著加分项。

4.3 五个小函数的分工表：每个函数到底负责什么

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两个操作数顺序写反

现象：输入12+3#，预期15，实际得到24，或者得到更离谱的负值。

原因：连续数字分支里先PopND弹出栈里已有的高位a，再用Getnum(a,b)合并。Getnum约定高位在前、低位在后，返回10*a+b。如果把参数顺序写成Getnum(b,a)，12会被拼成21，表达式变成21+3，输出24。

解决：改回高位在前；同时在合并前打印a和b，确认谁先出栈。出栈顺序本身也值得检查——先弹的是最近压入的数字，也就是表达式中靠后的数字，这在多位数字合并时尤其容易搞混。

5.3 括号嵌套算错或程序不结束：优先级表或continue位置错了

现象：输入((2+3))*4#，结果不是20，而是中间某一步的值；或者程序迟迟不输出，像死循环。

原因：两种可能。一是isp表里左括号的栈内优先级设错，比如设成和+ -一样的2，那么右括号到来时，栈顶左括号的isp=2、右括号icp=1，i>j成立，左括号会被当成普通运算符参与计算，括号语义直接崩坏。二是else分支里漏了continue，右括号弹出后没有保持g不变，而是照常执行l=g; g=getchar();，右括号被当作已处理字符丢弃，配对的左括号永远卡在栈里，栈清不了，循环退不出。

解决：对照第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(y==0)的判断，输出错误信息并结束；拼接多位整数时用long long做中间运算，最后检查是否落在int范围内再压栈。实验要求允许不处理语法错误，但数据边界处理属于工程习惯，补上之后代码档次明显不一样。

5.6 排查手段：循环顶部打印状态，十分钟定位问题

栈类逻辑最难的不是算法，而是“看不见状态”。推荐在while循环体开头插一段调试输出，把每轮的输入字符和两个栈的内容打出来：

// 调试用：每轮循环开头打印当前状态，定位完删除 printf("g=%c l=%c k=%c | 运算符栈:", g, l, k); for(int idx=0; idx<=tr.top; idx++){ printf("%c ", tr.elem[idx]); } printf(" | 操作数栈:"); for(int idx=0; idx<=nd.top; idx++){ printf("%d ", nd.elem[idx]); } printf("\n");

对照表达式手动模拟一遍，就能清楚看到是压栈方向错、优先级比较错，还是continue位置不对。比如第5.3节的括号残留问题，打印后左括号会一直出现在运算符栈里，现象一目了然。

另外，程序正常路径会在Calculate末尾调用DelStackTR和DelStackND释放内存。如果中途有提前return或异常分支，两个栈的malloc内存就会泄漏。用valgrind跑一遍，看leak summary就能确认释放路径是否完整。

6. 把作业代码改造成趁手工具：测试矩阵、整行读入和一张表验证法

6.1 测试矩阵：从“能跑”到“证明它正确”

验收栈程序，光跑几个正整数用例远远不够。建议准备一组覆盖各种边界的测试矩阵：

其中8/4*2#特别容易被人手算错。按数学直觉可能先算乘法得到1，但C语言里乘除同优先级，从左到右结合，实际是先 8/4=2 再 2*2=4。这个用例能验证代码没有在i==j时提前计算，而是严格按栈内栈外优先级规则结算。

6.2 改造成自己的工具：整行读入、空格过滤和栈容量

原代码用getchar逐字符读，输入约定是无空格、以#结尾。实际用的时候，这种输入方式不太友好。最常见的改造是先用fgets整行读入，过滤空格和换行，再喂给原来的状态机：

char line[128]; fgets(line, sizeof(line), stdin); for(int i=0; line[i]; i++){ if(line[i]==' ' || line[i]=='\n') continue; // 把line[i]按原逻辑交给Calculate的状态机处理 }

这样测试时1 + 2 * ( 3 - 4 )这种带空格的表达式也能正常跑，不需要刻意控制输入格式。

栈容量M=25也可以顺手加大，比如改成128，避免深层括号嵌套时越界。更工程化的做法是给Push函数加一个扩容检查，栈满时realloc，但实验场景里改常量就够了。记住这份代码的主逻辑很紧凑，所有修改都围绕“输入方式”和“容量上限”做，不要动isp/icp表和负号标记的状态机，那部分动了就要重新过一遍整个测试矩阵。

从那以后，我每次写栈相关的作业或机试题，都先把isp/icp两张表默写在草稿纸上，再开始动代码。优先级表就是表达式的“规则说明书”，定了它，后面的入栈出栈全是体力活；不定它，调试全是玄学。这份实验报告完整代码可以直接下载，建议你照着测试矩阵敲一遍，把每个函数为什么存在、为什么是这个返回类型讲清楚，比直接抄代码收获大得多。希望帮到你。

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