企业官网建设流程全解析

简介：这是一份《数据结构》课程设计实验报告，主题为表达式求值，面向计算机相关专业学生或需要完成同类课设的读者。报告围绕算术表达式求值问题，重点讲解如何借助运算符栈与操作数栈实现算符优先算法，使包含正整数、+ - * / 及括号的表达式能按正确优先级完成计算。内容按前言、概要设计、详细设计、软件测试、总结等章节展开，包含顺序栈存储结构设计、ADT Stack抽象类型描述、算符优先关系表、关键算法流程与代码，并提供测试与总结，便于读者理解栈在表达式解析中的典型应用。资源为1个doc文档，压缩后约122KB，文档结构完整、目录清晰，可直接作为课设报告写作参考或算法实现复盘资料。已有461人学习浏览，适合正在准备数据结构课程设计、复习栈应用或需要参考实验报告格式的学习者。

1. 表达式求值实验：最难的不是写代码，是让括号和优先级听话

做数据结构课程设计时，“表达式求值”实验几乎是绕不开的一道坎：要你用栈把中缀表达式转成后缀，再算出结果。很多同学第一反应是“这不就一个计算器”，实际动手才发现，翻车大多发生在括号匹配和运算符优先级这两处，而不是算法本身。这篇笔记按数据结构 C 语言版的经典路线，把中缀转后缀、后缀求值、实验报告.doc 的写法，以及我踩过的几个坑完整过一遍。适合正在赶数据结构实验报告、准备期末复习或考研数据结构的同学照着做，也适合想补栈应用的人。

2. 中缀转后缀：优先级表是核心，先把这个定明白

2.1 为什么实验要求先转后缀：直接求值要背两个锅

不少人的第一版方案是“扫一遍中缀表达式，遇到运算符就原地算”，很快就会发现死路：读入1+2*3时，刚看到+还不能算，因为后面可能跟着*或/这种更高优先级的运算符。所以要么往后多看一位，要么把已读到的操作数暂存起来。往后多看一位在括号嵌套时非常难看，比如(1+2)*(3+4)，向右看根本看不完；暂存又等于自己造了一个操作数栈。这就是中缀表达式天然的模糊性，优先级和括号把“什么时候该算”这件事藏在了后面。

转后缀表达式的核心价值在于：把“优先级、括号、左结合”这些规则，在转换阶段一次性消化干净。后缀串里没有括号，越靠前的运算符越先算，求值阶段只需要机械地“遇数入栈、遇运算符弹两个”，不需要回头、不需要比较优先级。这样两个阶段各干各的，程序容易调试，实验报告里的流程图也好画。从考研角度说，中缀转后缀的手算步骤也是 408 和期末卷子上反复出现的题型，大话数据结构和王道里都用栈这个例子来讲。所以哪怕不是为了交实验，把转换规则吃透也不亏。

2.2 优先级表与转换代码：C 语言完整实现

先定义字符栈。转换阶段只处理字符，所以栈里存char：

#include <stdio.h> #include <stdlib.h> #define MAX 100 typedef struct { char data[MAX]; int top; } CharStack; void init(CharStack *s) { s->top = -1; } int is_empty(CharStack *s) { return s->top == -1; } void push(CharStack *s, char c) { s->data[++(s->top)] = c; } char pop(CharStack *s) { return s->data[(s->top)--]; } char peek(CharStack *s) { return s->data[s->top]; } int priority(char op) { if (op == '+' || op == '-') return 1; if (op == '*' || op == '/') return 2; return 0; // '(' 的优先级设为最低 }

priority是转换算法的唯一决策依据：乘除返回 2，加减返回 1，左括号返回 0。这里不写%和^，实验要求里没有就不加，报告里也要标清楚“本程序只处理 + - * / 四种运算”。MAX 取 100 够应付课程作业的表达式长度，但报告里应当写明这是“顺序栈大小上限”，不是理论限制。

转换函数如下：

void infix_to_postfix(const char *infix, char *postfix) { CharStack s; init(&s); int i = 0, j = 0; while (infix[i] != '\0') { char ch = infix[i]; if (ch >= '0' && ch <= '9') { // 连续数字拼成一个操作数，输出到后缀串 while (infix[i] >= '0' && infix[i] <= '9') { postfix[j++] = infix[i++]; } postfix[j++] = ' '; // 数字结束，用空格分隔 } else if (ch == '(') { push(&s, ch); i++; } else if (ch == ')') { // 弹出栈顶直到左括号为止 while (!is_empty(&s) && peek(&s) != '(') { postfix[j++] = pop(&s); postfix[j++] = ' '; } if (!is_empty(&s)) pop(&s); // 弹出左括号 i++; } else if (ch == '+' || ch == '-' || ch == '*' || ch == '/') { // 栈顶优先级 >= 当前运算符时，先弹出栈顶 while (!is_empty(&s) && peek(&s) != '(' && priority(peek(&s)) >= priority(ch)) { postfix[j++] = pop(&s); postfix[j++] = ' '; } push(&s, ch); i++; } else { i++; // 跳过空格或其他非法字符 } } // 表达式扫描完，把栈里剩下的运算符全部弹出 while (!is_empty(&s)) { if (peek(&s) != '(') { postfix[j++] = pop(&s); postfix[j++] = ' '; } else { pop(&s); // 处理输入自带未闭合左括号的情况 } } postfix[j] = '\0'; }

整体逻辑分四类：数字入后缀、左括号入栈、右括号弹栈、运算符先弹再入。这里最容易出错的是运算符分支里的 while 条件：priority(peek(&s)) >= priority(ch)，注意是大于等于。同优先级也要弹，否则会破坏左结合律。比如1-2+3，读到+时栈顶是-，两者优先级相等，必须先把-弹出来，后缀变成1 2 - 3 +，先算1-2再+3，结果才是 2。如果写成>不弹，后缀就是1 2 3 - +，算成1-(2-3)，结果变成 2 却是歪打正着，换个式子立刻翻车。

转换阶段的空间也讲一下：栈深最坏情况和括号嵌套深度相关，输入((((1+2))))这种，四个左括号都会压栈，所以 MAX 取 100 时，理论上能处理约 99 层嵌套，对作业足够。

2.3 括号和多位数：两个一起处理，一次说清

括号处理的原则是：遇到(无条件入栈，遇到)弹出栈顶所有运算符直到(。这个“无条件入栈”初学者容易写成“和栈顶比较优先级再决定”，如果这么写，(会被*或+挡住进不了栈，括号内的算式就全乱套。抓一个记忆点：(不是运算符，它只是分组的标记，优先级表里给它 0 是为了占位，真正比较时永远先判断“栈顶是不是(”，是就直接入栈。

多位数处理看起来简单，坑却不少。12+3不加空格地转，会变成1 2 3 +，求值时按1+2+3=6算，直接错了。所以要先把连续的数字字符拼成一个串，再在后缀串里用空格隔开。这也是为什么上面代码里数字分支有一个内层 while 循环。常见做法是：给后缀串加一个分隔符空格，求值阶段读到空格就跳过，这样12和3在串里是谁也分得清的。用表格看一组转换结果更直观：

3. 后缀表达式求值：第二个栈把结果算出来

3.1 求值算法与 int 栈：遇数入栈、遇符弹两个

后缀求值的规则只有三条：数字入栈；遇到运算符弹出两个数，先弹出的是右操作数，后弹出的是左操作数；运算结果重新入栈。整个串扫完，栈顶就是最终结果。这个栈里存的是整数数值，不是字符，所以不能复用第 2 章的 CharStack，要单独定义一个存int的栈：

typedef struct { int data[MAX]; int top; } IntStack; void init_int(IntStack *s) { s->top = -1; } int is_empty_int(IntStack *s) { return s->top == -1; } void push_int(IntStack *s, int v) { s->data[++(s->top)] = v; } int pop_int(IntStack *s) { return s->data[(s->top)--]; } int evaluate_postfix(const char *postfix) { IntStack s; init_int(&s); int i = 0; while (postfix[i] != '\0') { if (postfix[i] >= '0' && postfix[i] <= '9') { int num = 0; while (postfix[i] >= '0' && postfix[i] <= '9') { num = num * 10 + (postfix[i] - '0'); i++; } push_int(&s, num); i++; // 跳过数字后面的空格 } else if (postfix[i] == '+' || postfix[i] == '-' || postfix[i] == '*' || postfix[i] == '/') { int b = pop_int(&s); // 先弹出的是右操作数 int a = pop_int(&s); // 再弹出的是左操作数 int res = 0; switch (postfix[i]) { case '+': res = a + b; break; case '-': res = a - b; break; case '*': res = a * b; break; case '/': if (b == 0) { printf("ERROR: divide by zero\n"); exit(1); } res = a / b; break; } push_int(&s, res); i++; } else { i++; // 跳过空格 } } return pop_int(&s); }

这里有两个必须写清楚的细节。一是操作数顺序：后缀串5 2 -，遇到-时先弹出 2，再弹出 5，计算的是5-2，不是2-5。初学者容易写成a-b却把 a、b 认反，减法和除法会直接算错。二是除零保护：整数除法除零在 C 里是未定义行为，最常见的是程序直接崩溃，报告里如果不处理会显得很不严谨。

3.2 操作数顺序与整数除法：卷面上爱考的两个细节

先弹出的是右操作数，这个顺序来源于后缀表达式的定义：在中缀a-b转成后缀a b -的过程中，a 比 b 先进入后缀串，所以求值时 a 先入栈、b 后入栈，弹出时自然 b 在前、a 在后。记住“先弹出的是右边那个”就不会乱。想验证的话，手算一个8/4/2：后缀是8 4 / 2 /，第一次除法算出 2，第二次2 2 /算出 1，符合从左到右的结合。

整数除法是实验中一个容易忽略的预设条件。C 语言里5/2结果是 2，如果实验指导书没有要求浮点结果，这样写就行，但报告开头的问题描述里必须写明“本实验仅处理整数四则运算”。如果验收时老师输入5/2期望2.5，那就需要把 IntStack 里的int全部换成double，push_int、pop_int同步改，弹出来参与运算的数也按 double 处理。后者的坑在于%d输出要换成%g或%.2f，这属于报告“运行环境”里必须交代的细节。

3.3 main 函数串起来：收尾与运行验证

int main() { char infix[MAX]; char postfix[MAX]; printf("请输入中缀表达式（数字为多位数，运算符仅 + - * /）: "); scanf("%s", infix); infix_to_postfix(infix, postfix); printf("后缀表达式: %s\n", postfix); int result = evaluate_postfix(postfix); printf("计算结果: %d\n", result); return 0; }

scanf("%s")适合实验场景，输入不能带空格，因为字符串会被空格截断。如果想让程序支持带空格的输入，就用gets或fgets，但gets有缓冲区安全问题，报告里不建议写。实验报告通常会要求给出“输入 -> 后缀 -> 输出”的三行样例，上面这段代码本身就能输出这三样，截图时直接截这个就够了。

4. 实验报告.doc 怎么写：数据结构、算法描述、测试用例才是得分点

4.1 报告开头：问题描述与输入输出格式

很多人的实验报告第一段就写“本实验实现了中缀表达式求值”，太干，拿不到分。问题描述部分要写清楚三件事：程序输入什么样、输出什么样、处理范围是什么。我一般这样组织：

程序输入为一个中缀表达式，表达式由十进制整数、运算符 + - * / 和左右圆括号组成，整数支持多位；程序输出两行，第一行是对应的后缀表达式，第二行是计算结果。本实验约定只处理整数四则运算，除数不为 0，表达式中不含空格以外的非法字符。

这几句话把边界全部框死。老师验收时拿不进边界的输入，他也怪不到你，因为报告里写明了。反过来，你代码里如果没处理除零，报告又没写这个约定，那就是你翻车。另外提一句，问题描述里不要写“任意表达式”，写成“约定范围内”更诚实，也更好收尾测试用例。

4.2 数据结构定义与算法设计：栈的抽象数据模型怎么画

报告的数据结构部分要贴代码，但不需要贴完整程序，核心是栈的定义和四个基本操作。我建议放这段 ADT 描述：

#define MAXSIZE 100 typedef struct { char data[MAXSIZE]; int top; } SeqStack; // 基本操作： // InitStack(&S): 初始化，top = -1 // StackEmpty(S): 判断栈空 // Push(&S, e): 元素 e 入栈，top 加 1 // Pop(&S): 栈顶元素出栈，top 减 1 // GetTop(S): 取栈顶元素，不弹出

算法设计部分不要大段复制程序源码，而要写“转换规则”和“求值规则”两条文字过程。我常用四条转换规则和三条求值规则组织：

1. 扫描中缀表达式，遇数字直接输出到后缀串。
2. 遇(入栈；遇)弹出栈顶运算符并输出，直到遇(为止。
3. 遇运算符：当栈不空且栈顶不是(且栈顶优先级不低于当前运算符时，弹出栈顶并输出；然后当前运算符入栈。
4. 扫描结束把栈中剩余运算符全部弹出。

求值的规则可以写成一两句：“从左到右扫描后缀串，数字入栈，运算符弹出两个操作数运算后将结果入栈”。这比把完整程序贴上去要清爽得多，老师在报告上找的就是这几条规则，而不是代码本身。流程图如果能画，画一个“转换”的框和“求值”的框串起来的双框流程图，是报告加分的常见操作。

4.3 复杂度分析：这几分是白送的

实验报告的复杂度部分常常被忽略，但它是数据结构实验报告必须有的内容。这里可以直接抄作业式地写三段：

时间方面，中缀转后缀对表达式扫描一遍，每个字符最多入栈出栈各一次，所以转换阶段时间复杂度 O(n)，n 为表达式长度。后缀求值同样扫描一遍后缀串，每个数字和运算符处理一次，O(n)。两个阶段串行，整体时间复杂度 O(n)。

空间方面，程序有两个栈，栈深最坏情形的表达式形如((((1+2))))，嵌套括号全部压栈，栈深约等于表达式长度，空间复杂度 O(n)。由于两个栈是分开定义的，不会互相挤占，容量各为 MAXSIZE。

第一句“每个字符最多入栈出栈各一次”是复杂度成立的关键，写成这样老师知道你理解了为什么不是 O(n²)。

4.4 测试用例表与实验截图：用一张表讲清覆盖范围

测试部分最好用表格，因为表格能直接说明“每种输入覆盖了什么边界”。这是我当年交实验报告时用过的表，直接照抄逻辑：

这 6 条用例覆盖了转换阶段的全部边界，第 4 条和第 5 条是很多测试表里漏掉的。实验截图部分，运行结果直接贴控制台文本或者截图都行，但报告要别忘写一句“以上结果通过编译环境验证，与人工计算结果一致”。这里的“人工计算”不用真列出来，列出期望结果那列就等于人工算过了。

4.5 结果分析：写结论不如写局限

结果分析是报告收尾最容易敷衍的部分。一句“实验结果正确”没有说服力，我建议写两部分。第一部分写“6 组测试用例全部通过”，这里的通过标准是输出后缀与期望一致、计算结果与期望一致。第二部分主动写局限：不支持小数运算、不支持一元负号（如-5+3）、表达式内不含空格。这三点写出来，报告反而显得专业，因为你自己指出了边界，老师就不会拿边界来打你。

5. 表达式求值实验的踩坑记录：4 个高频翻车点排查

5.1 括号不匹配：程序没报错，但结果莫名其妙

现象：输入1+2)程序没报错，输出了一个看起来合理但实际不对的结果；输入(1+2时后缀串尾部多出一个(，求值阶段直接崩溃或报错。
原因：infix_to_postfix里遇到右括号时没有检查栈空，栈为空还继续弹；左括号在转换末尾也没有做残留检查。
解决：遇到)时先判断is_empty(&s)，为空就说明缺少匹配的左括号，直接输出错误信息返回。转换结束后遍历栈，如果还剩(，说明缺少右括号。实验代码里可以在两个位置加if判断，报告里写明“对括号不匹配输入返回 ERROR”。处理方式不唯一，但报告里必须说明你处理了。

5.2 优先级写反：1+2*3算出 9

现象：输入1+2*3，程序输出 9 而不是 7。
原因：优先级函数里把*的返回值写成了 1，+写成 2；或者是转换分支里priority(peek(&s)) > priority(ch)写了严格大于，导致同优先级不弹出，1-2+3这种式子也会错。
解决：先对照优先级表检查priority两个返回值，乘除必须是 2，加减必须是 1。再检查比较符是不是>=，同优先级必须弹栈。我在调试时最喜欢加一行打印：每遇到一个运算符，把“当前字符、栈顶字符、两个 priority 值”打出来，一眼就能看出是谁没弹。

5.3 多位数被拆散：12+3算成 6

现象：输入12+3，后缀输出1 2 3 +，结果 6。
原因：数字分支没有做连续拼接，每读到一个数字字符就立刻输出到后缀串，12被当成了1和2两个数。
解决：数字分支里加一个内层 while 循环，把连续的数字字符全部读进来，拼成一个整数后再输出；后缀串必须用空格分隔数字与运算符。对应的求值阶段也要在数字分支里把连续字符转成 int，再跳过后面那个空格。这两个“拼数 + 跳空格”是配套的，只改转换不改求值，照样会错。

5.4 整数除法与除零：程序崩溃还是在报告里提前声明

现象：输入5/0程序崩溃；输入5/2输出 2，老师却问“为什么不是 2.5”。
原因：整数除零触发未定义行为，C 环境通常会直接异常终止；int栈和int操作数导致小数部分被截断。
解决：除法分支里先判断右操作数是否为 0，为 0 就输出错误并退出，这是程序健壮性问题；整数除法的问题，属于报告约束条件的声明问题。我在实验报告的问题描述部分一定会写“本实验仅处理整数四则运算，除数不为 0”，同时代码里仍然保留除零判断。两种手段一起上，程序和文档就都对得上。

6. 从合格到优秀：给表达式求值实验加三个说服力技巧

第一个技巧是在转换函数里加调试打印。每处理一个字符，就把当前字符、栈内剩余内容、已生成的后缀串打出来，像这样：

printf("处理 '%c' | 栈: ", ch); for (int k = 0; k <= s.top; k++) printf("%c ", s.data[k]); printf("| 后缀: %s\n", postfix);

这个打印对排查优先级问题就是后悔药级别的存在，哪一步弹错了，控制台上看得一清二楚。完成调试后把它注释掉或者用#ifdef DEBUG包起来，报告里提一句“程序内含调试输出，可在宏 DEBUG 开启下观察转换过程”，比贴一堆过程截图还省事。

第二个技巧是用脚本批量验证。手输 6 个用例可以交差，但想验证 50 个不重样的表达式，就得靠 shell 脚本。把每个表达式作为一行放进cases.txt，然后：

#!/bin/bash while IFS= read -r expr; do printf "%s => " "$expr" echo "$expr" | ./expr_eval done < cases.txt

脚本跑完，对照第 4 章那张测试表，看每一行的输出是否符合预期。这个习惯我在后面做命令行工具时也一直在用，凡是和“解析输入”沾边的程序，批量样本永远比手点快。

第三个技巧是做一个“转换过程手工对照表”。选择(1+2)*3这类包含括号和优先级的表达式，在报告测试节里用一小段文字逐步列出：读到(入栈、读到1输出、读到+入栈、读到2输出、读到)弹出+、读到*入栈、读到3输出、最后弹出*。这张表让老师能按步骤核对你的程序逻辑，比单纯贴输出结果有说服力得多。我从写这个实验开始养成的习惯是：程序里加调试输出、报告里留步骤记录、边界条件主动声明，这三个习惯后来帮我少加了不少班。希望帮到你。

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