栈的应用：C语言实现中缀表达式转后缀表达式求值

简介：这份实验报告围绕“算数表达式求值”课程设计展开，面向正在学习数据结构与算法、需要完成栈相关课程设计的大中专学生。程序采用算符优先法处理含括号的加、减、乘、除混合表达式，借助运算符栈oprt、数字栈num和临时栈temp完成运算；从键盘读入以“#”为边界的合法表达式，输出计算结果，并显示输入序列和栈的变化过程。报告完整介绍了算法设计思想、运算符优先级关系、核心功能函数（创建栈、出入栈、判空、取栈顶、优先级比较、中间计算等）、主要流程图和运行效果截图，还分析了时间与空间复杂度均为O(n)，适合直接对照实现代码和撰写报告。文档额外补充了栈满动态扩容、除数为0、非法输入、括号不匹配等异常处理说明，体现出从“能算”到“可靠”的工程考量。整个资源为1个docx文档，压缩包大小2.29MB，目前已有3620人浏览学习，可作为课程设计报告模板、编码调试参考及答辩准备材料。

1. 算数表达式求值这门数据结构实验，卡住你的不是语法

算数表达式求值是数据结构课程里出现频率最高的一类实验：给一串中缀表达式，比如1+2*3，要按运算符优先级算出结果。很多人的程序调不通，问题根本不是语法写错，而是没想清楚栈的进出时机——运算符要等优先级更高的运算符算完才能出场，这个“等待”正是栈存在的意义。这项实验覆盖的是线性结构上的状态记忆，搞懂它之后，括号匹配、编译原理的词法分析、逆波兰式计算器都能顺手打通。它适合正在写数据结构实验报告的学生、期末复习和考研刷题的人，以及想补一补栈应用的开发者。本文按实验报告的顺序走：先立原理，再给可直接编译的 C 语言实现，最后是翻车现场和批量验证方法。

2. 中缀转后缀：把人的优先级装进栈里

2.1 人读中缀，机器读后缀：两种表达式的本质差异

先看两个式子。中缀表达式1+2*3，人一看就知道先乘后加，结果是 7。但计算机从左读到右，读到+时并不知道后面还有个*在等着。如果直接“见一个运算符算一个”，就会算出(1+2)*3=9，错了。后缀表达式把运算顺序直接写进排列里：1 2 3 * +，从头到尾读一遍，数字压栈，遇到*弹出两个数相乘再压栈，最后遇到+弹出两个数相加，结果是 7。整个过程中不需要任何优先级判断，因为后缀式里*已经在+前面，时机被编码进了序列。

后缀表达式也叫逆波兰式。它的核心价值是消除了括号和优先级的二义性：任何中缀式都能无损转成后缀式，转换时优先级和括号已经折算进序列。这就是为什么几乎所有求值程序都走“中缀转后缀、后缀求值”两步，而不是在中缀上直接加优先级逻辑——后者要把优先级表嵌进求值循环，边界情况多到难以收场。

实验报告里常会问“为什么不直接扫描中缀求值”，这里给一个可以写进报告的答案：中缀求值必须随时预判后续运算符，等效于在扫描过程中维护一个运算符优先级栈；把这一步拆成显式的“转后缀”，每个阶段只做一件事，程序可读性和正确性都显著更好。这个思想就是编译原理里词法分析与语法分析分离的雏形。

2.2 运算符优先级与栈的进出规则

转后缀的规则可以浓缩成一张表。设当前读到的运算符为 op，栈顶为 top：

优先级表最简单的一版：+和-同级（1），*和/同级（2）。左括号要特殊处理，栈内优先级必须设得极低，比如 0，这样括号后的任何运算符都能压进去。右括号不参与比较，它只负责触发“弹到左括号为止”。

为什么“栈顶优先级 >= 当前”就要弹出？因为栈顶那个运算符更“急”，它的操作数已经齐了，不先算它会破坏优先级。拿1+2*3举例：读+入栈，读 2 输出，读*时栈顶+优先级 1 低于*的 2，所以*直接入栈，读 3 输出，结束后先弹*再弹+，得到1 2 3 * +。换1*2+3：读*入栈，读+时栈顶*优先级 2 大等于+的 1，弹出*输出，+入栈，得到1 2 * 3 +。这一弹一压就是整个栈逻辑的核心。

2.3 括号是作用域，不是运算符

括号不进入后缀式，它只改变运算符的出栈时机。细节有三个。第一，左括号入栈后，括号内的运算符都要压在它上面，所以左括号的栈内优先级必须最低，否则括号内的运算符永远出不来。第二，遇到右括号时不断弹栈，直到弹出左括号；如果栈弹空了还没见到左括号，说明右括号多余，这是最常见的输入错误。第三，括号内部按同样的规则运行，相当于开了一个局部作用域，弹到左括号即自动退出——这和函数调用栈的返回行为是同一个模型。

有一个容易忽略的点：每次取栈顶前先判空，永远是这类程序的基本卫生习惯。写代码时把isOperator、getPriority、pop拆开，每个函数只做一件事，调试时能省大量时间。很多人把左括号当普通运算符入栈，最后又把它输出到后缀式，这就是没理解括号是作用域标记，不是运算。

2.4 后缀求值：一路压栈，遇到运算符再算

后缀求值的流程比转换更简单：读 token，数字压栈；读到运算符，弹出两个数，先弹出的是右操作数，后弹出的是左操作数，算完把结果压回去；扫描结束后，栈顶就是答案。以2 3 4 * +为例：2、3、4 依次压栈，读到*弹出 4 和 3，算 3*4=12 压回，读到+弹出 12 和 2，算 2+12=14。

这里必须记住弹出顺序：对1 2 -，扫描 1 压栈、2 压栈，读到-时栈顶是 2，先弹出的是b=2，再弹出a=1，结果是a-b=-1。写成a=pop(); b=pop()就会得 1-2 还是 2-1 搞反，减法除法全错。很多人的求值程序翻车都翻在这一行，不是算法理解问题，是“先弹出的是右操作数”这个直觉没建立。

转移与求值都是线性扫描：中缀转后缀每个字符最多进出栈一次，O(n)；后缀求值每个 token 进出栈一次，O(n)。总体时间 O(n)，栈深度不超过运算符数量，空间 O(n)。实验报告里写“时间 O(n²)”是错的，那只有在弹栈时反复遍历栈才会出现。

3. 用C语言跑通求值程序：完整可抄的实现与报告要点

3.1 栈的封装与表达式读入

我一般用字符串数组做栈，而不是单字符栈。原因很直接：后缀式里的数字可能是多位数或小数，单个char存不下。用 token 数组，每个元素存一个字符串，转换和求值两个阶段都能复用。

#include <stdio.h> #include <stdlib.h> #include <string.h> #include <ctype.h> #define MAX 100 typedef struct { char data[MAX][MAX]; /* 每个元素存放一个 token：运算符或数字字符串 */ int top; } Stack; void init(Stack *s) { s->top = -1; } void push(Stack *s, char *val) { strcpy(s->data[++(s->top)], val); } char *pop(Stack *s) { return s->data[(s->top)--]; } char *getTop(Stack *s) { return s->data[s->top]; } int isEmpty(Stack *s) { return s->top == -1; } int main() { char expr[MAX], cleaned[MAX]; char postfix[MAX][MAX]; int postfixLen, i, j = 0; printf("请输入表达式: "); fgets(expr, MAX, stdin); /* 去掉空白字符，避免空格打断数字和运算符的扫描 */ for (i = 0; expr[i] != '\0'; i++) { if (expr[i] != ' ' && expr[i] != '\n' && expr[i] != '\t') cleaned[j++] = expr[i]; } cleaned[j] = '\0'; infixToPostfix(cleaned, postfix, &postfixLen); printf("后缀式: "); for (i = 0; i < postfixLen; i++) printf("%s ", postfix[i]); printf("\n"); double result = evaluatePostfix(postfix, postfixLen); printf("结果: %g\n", result); return 0; }

fgets比gets安全，不会越界。清洗阶段把空格、换行、制表符全部删掉，后面读数字的循环就不用考虑空白打断。postfix是二维数组，每一行存一个 token，postfixLen记录 token 总数。注意MAX是固定上限，实验规模够用，如果要处理超长表达式，改成动态分配即可。

3.2 核心算法一：中缀转后缀

转换函数接收清洗后的中缀字符串，输出后缀 token 数组。优先级函数用switch写最直白，左括号栈内优先级设为 0，保证比任何运算符都低。

int getPriority(char op) { switch (op) { case '+': case '-': return 1; case '*': case '/': return 2; case '(': return 0; /* 左括号在栈内优先级最低 */ default: return -1; } } int isOperator(char c) { return c == '+' || c == '-' || c == '*' || c == '/'; } void infixToPostfix(char *infix, char postfix[][MAX], int *postfixLen) { Stack opStack; init(&opStack); int i = 0, k = 0; while (infix[i] != '\0') { if (isdigit(infix[i]) || infix[i] == '.') { /* 连续读数字和小数点，形成一个完整 token，避免把 12 拆成 1 和 2 */ int start = i; while (isdigit(infix[i]) || infix[i] == '.') i++; strncpy(postfix[k], infix + start, i - start); postfix[k][i - start] = '\0'; k++; continue; } if (infix[i] == '(') { push(&opStack, "("); } else if (infix[i] == ')') { /* 弹出运算符直到左括号，左括号不输出 */ while (!isEmpty(&opStack) && strcmp(getTop(&opStack), "(") != 0) { strcpy(postfix[k++], pop(&opStack)); } if (!isEmpty(&opStack)) pop(&opStack); } else if (isOperator(infix[i])) { char op[2] = {infix[i], '\0'}; /* 栈顶优先级 >= 当前，先弹出，保证乘除先于加减 */ while (!isEmpty(&opStack) && strcmp(getTop(&opStack), "(") != 0 && getPriority(getTop(&opStack)[0]) >= getPriority(op[0])) { strcpy(postfix[k++], pop(&opStack)); } push(&opStack, op); } i++; } /* 全部弹空 */ while (!isEmpty(&opStack)) { strcpy(postfix[k++], pop(&opStack)); } *postfixLen = k; }

数字分支里的strncpy从infix + start截取一段连续数字加小数点的子串，这就是处理多位数和小数的关键，少了这个循环，12+3一定会被拆成1、2、3三个 token。运算符分支的while条件写全三个判断：栈非空、栈顶不是左括号、栈顶优先级不低于当前，少一个都会出错。最后收尾弹空栈不能漏，否则栈里剩下的运算符全部丢失。

提示：strncpy不保证目标字符串以\0结尾，所以下一行必须手动写postfix[k][i - start] = '\0'。这一步漏掉，后续strcmp和printf都会读到脏数据。

3.3 核心算法二：后缀求值

求值栈用double数组，因为运算结果是浮点数。遇到数字就atof转换，遇到运算符就弹出两个数。

double evaluatePostfix(char postfix[][MAX], int len) { double stack[MAX]; int top = -1; int i; for (i = 0; i < len; i++) { if (postfix[i][0] >= '0' && postfix[i][0] <= '9') { stack[++top] = atof(postfix[i]); } else { double b = stack[top--]; /* 先弹出右操作数 */ double a = stack[top--]; /* 再弹出左操作数 */ switch (postfix[i][0]) { case '+': stack[++top] = a + b; break; case '-': stack[++top] = a - b; break; case '*': stack[++top] = a * b; break; case '/': if (b == 0) { printf("除零错误\n"); exit(1); } stack[++top] = a / b; break; } } } return stack[top]; }

postfix[i][0]判断首字符是数字还是运算符，能覆盖正数情况。负数目前不支持，第 4 章会专门讲。b=stack[top--]先取到的是栈顶，也就是后压入的数，运算顺序必须保持a-b、a/b。除零分支用exit(1)直接退出，比返回一个特殊值更干净，至少不会带着inf继续算。

3.4 实验报告的结构与测试用例表

报告骨架一般按这个顺序写：问题描述、数据结构设计、算法描述、核心代码、测试、复杂度分析、总结。老师看报告时重点看两处：数据结构为什么选栈，以及测试用例有没有覆盖边界。选栈的理由要写“运算符的延迟运算与栈的后进先出语义一致”，不要只写“用栈实现”。

测试表格建议做成这样，每个用例标注覆盖点：

复杂度分析写 O(n) 时间、O(n) 空间，并说明为什么是线性：每个字符最多入栈出栈各一次。加上除零检测和括号匹配失败检测，报告里可以明确写“程序对非法输入做了防御性检查”，这会比只跑通 1+2 的实验高一个档次。

4. 求值程序最容易翻车的5个坑：现象、原因与处理

4.1 多位数和小数被拆成单字符

现象：输入12+3，结果算出 5，或者后缀式变成1 2 3 +。

原因：逐字符处理数字时，遇到一个数字立刻输出一个 token，没有把连续的数字串读完整。isdigit(infix[i])只判断当前字符，不负责“聚拢”它后面的数字。

解决：在数字分支里用while (isdigit(infix[i]) || infix[i] == '.') i++;一直读到数字串末尾，再用strncpy截取完整 token。第 3 章代码已经是这个写法，但很多人会把它简化成单字符输出，这是后缀式错乱的第一个源头。

4.2 括号匹配失败导致栈操作越界

现象：输入(1+2*3，程序崩溃或输出乱码；输入1+2)，弹栈弹到空栈。

原因：右括号处理时没有判栈空，直接无限弹栈直到越界；左括号多余时，最后收尾弹栈把空栈也弹了一遍，data[--top]访问到非法下标。

解决：右括号的while循环里加!isEmpty条件；弹出的左括号要单独pop一次，不要输出到后缀式；最后收尾弹栈前判空。更稳妥的做法是扫描开始时先做一遍括号匹配预检，左右括号数量一旦不相等直接报错退出，不进入后续逻辑。

4.3 减法、除法把操作数顺序写反

现象：2-3算出 1，8/4算出 0.25，乘法和加法却正常。

原因：后缀求值时先弹出的是栈顶，也就是表达式里靠后的数，它是右操作数；后弹出的是左操作数。写了a=pop(); b=pop()就全反了。

解决：固定写成double b = stack[top--]; double a = stack[top--];，再做a-b、a/b。这一条几乎每个做求值实验的人都踩过，我当年也翻过一次车，后来每次写栈相关代码都会先默念一遍“先出栈的是右操作数”。

4.4 除零没有显式处理

现象：8/0在部分环境直接浮点异常崩溃，在另一些环境输出inf，后续判断产生脏数据。

原因：C 语言对除以 0 的行为依赖运行时，double除法在 IEEE 754 下可能给inf，整数除法或某些编译环境直接崩。

解决：在除法分支显式检查if (b == 0)，打印错误并退出。实验报告里把“除零检测”写成独立函数或一个判断分支，属于加分项。不要依赖平台的默认行为，那是玄学，不是程序逻辑。

4.5 负数和空格：读入阶段被忽略的细节

现象：-3+2解析失败，或者带空格的1 + 2把数字拆成多个 token。

原因：一元负号缺少处理；空格没有在预处理阶段剔除，isdigit的连续读数字循环遇到空格就断开了。

解决：读入阶段把所有空格、换行、制表符全部删掉，这是最简单的止血方案。一元负号的处理方式是预处理：把开头的-和左括号后面的-替换成0-，比如-3+2变成0-3+2，(-3+2)变成(0-3+2)。替换后完全复用现有算法，不用动求值核心。这个方案在实验报告里写清楚，比硬撑一个负号状态机更可靠。

4.6 用 printf 大法定位栈状态

现象：结果不对，但看不出是在转换阶段错还是求值阶段错。

原因：栈是黑匣子，中间状态不可视化，靠肉眼盯着代码很难定位。

解决：在push和pop的位置各加一行fprintf(stderr, "push/pop: %s, top=%d\n", val, s->top);，跑一遍1+2*3，对比栈里运算符的进出顺序是否符合 2.2 节的规则。定位到具体字符后，把调试输出删掉即可。调试栈程序的技巧永远是“看它的进出序列”，而不是猜。

5. 批量自测与变量扩展：给你的实验报告加点分量

5.1 用脚本批量验证正确性

手动输入几个用例很难覆盖所有边界，我一般会写一个 Python 脚本随机生成表达式，把 C 程序的输出和 Python 的eval结果比对。

import subprocess import random ops = ['+', '-', '*', '/'] def gen_expr(): n = random.randint(2, 4) expr = str(random.randint(1, 20)) for _ in range(n): expr += random.choice(ops) + str(random.randint(1, 20)) return expr for _ in range(100): expr = ' '.join(gen_expr()) # 故意加空格，测试清洗逻辑 out = subprocess.run(['./calc'], input=expr + '\n', capture_output=True, text=True) got = float(out.stdout.strip().split('结果: ')[1]) expected = eval(expr.replace(' ', '')) if abs(got - expected) > 1e-6: print('不匹配:', expr, got, expected) break else: print('100 条全部通过')

脚本把随机生成的式子通过管道喂给编译好的calc程序，再对比输出。生成的表达式故意带空格，是为了连预处理逻辑一起测。eval只用来做测试参照，不参与 C 程序的实现。跑通 100 条随机用例后，把测试结果截图放进报告，比只写“测试通过”更有说服力。

5.2 变量替换：让表达式支持字母

进阶实验最常见的要求是支持变量，比如a+b*c，进入求值前先给a、b、c赋值。常见做法是在读入后做一次字符替换：遍历输入，遇到a就替换成对应的数字字符串，替换完再交给中缀转后缀。替换表用一个简单的结构体数组就够了，两三个变量用if都可以。这个扩展不需要改动转换和求值核心，却能让实验报告多出一节“扩展功能”，在答辩或验收时是个不错的亮点。

我做这个实验时，中缀转后缀写了三版才完全跑通，最后发现所有 bug 都集中在 4.3 提到的顺序问题上。从那以后我养成了习惯：写栈程序先列测试用例，再动手写逻辑，不急着敲代码。这个习惯帮我避开了后面不少坑，也希望帮到你。

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