简介：《数据结构表达式求值实验报告》是一份面向计算机专业学生的课程设计文档，适用于数据结构课程中栈与队列专题实验、表达式求值算法实现及期末课程设计参考。内容以算术表达式求值为核心，针对运算符优先级和括号处理难题，详细说明了基于顺序栈的双栈方案，即运算符栈与操作数栈的协同工作方式，并完整覆盖了算符优先算法、ADT抽象类型描述、功能模块划分、存储结构定义以及主要算法流程图与关键代码。整个压缩包内容简洁，仅包含一个doc格式文档，整体大小约122KB，目前已有四百六十一人浏览学习，页面容量精炼，方便直接下载使用。除设计过程外，报告还提供了软件测试与总结章节，有助于读者了解边界条件测试、异常输入排查和算法优化思路；附录部分也便于对照关键实现代码。整体结构遵循课程设计报告规范，目录清晰，既能作为完成作业的写作模板，也能为阅读者理解表达式求值的栈实现提供扎实参考。
1. 表达式求值课设：这份双栈算符优先法实验报告能帮你省掉大半调试时间
搜过“数据结构 表达式求值”资料的同学应该都有体会：网上的源码一大把，但能把“为什么这么写”讲明白的很少。这份课设报告不一样，它把算术表达式求值收敛成一套完整的双栈算符优先解法——一个运算符栈 OPTR、一个操作数栈 OPND、一张 49 格的运算符优先关系表，让原本需要反复回看、不断回溯的求值过程变成一次干净的线性扫描。报告从顺序栈的存储结构、ADT 描述、核心函数代码到软件测试全齐了，特别适合还在啃数据结构 C 语言版课设、或者准备期末上机的人照着复现一遍。操作数限定正整数，运算符只有 + - * /，用 # 表示结束，边界收得很干净，正好用来练栈的理解。
2. 为什么是双栈而不是直接扫描：算符优先算法与 # 结尾的设计逻辑
2.1 从左到右求值为什么行不通
一个很直觉的想法是：拿到3+4*5#就从左往右扫，先算3+4，再乘 5，结果得到 35。但正确结果是 23，问题就出在运算符优先级上。*的优先级高于+，所以必须先算4*5，这意味着程序在读到+的时候并不能立刻决定“现在就算”，它得先往后看，确认后面有没有更高优先级的运算符。括号也一样：(7-2)里的减号必须等到右括号出现才能执行，因为括号人为改变了运算顺序。
这种“先记住，回头再算”的需求，恰好是栈的看家本领。顺序栈只允许在表尾插入和删除，后进先出，天然适合表达这种“暂时挂起、遇到条件再恢复”的计算过程。表达式求值之所以在数据结构课设里这么经典，就是因为它能用一个很小的模型，把栈、线性表、查找、字符串处理这些知识点串起来。这也是为什么几乎每个《数据结构与算法》课程都会留这道题。
2.2 两个栈的分工与算符优先算法的骨架
算符优先算法最核心的思路：不直接算，而是每读到一个运算符，先和栈顶运算符比优先级，再决定是压栈还是弹栈运算。为了同时记住“运算符”和“操作数”两类信息，必须用两个栈。OPTR 管运算符和括号，OPND 管操作数以及中间运算结果。
算法骨架可以用下面这段伪代码描述：
1. 初始化 OPND 为空栈 2. 把 '#' 压入 OPTR，作为栈底哨兵 3. 读入表达式的第一个字符 c 4. while (c != '#' || GetTop(OPTR) != '#') { 5. if (c 是操作数) { 6. 读取完整的多位数并压入 OPND 7. } else { 8. switch (Precede(GetTop(OPTR), c)) { 9. case '<': // 栈顶优先级低，当前运算符入栈 10. Push(OPTR, c); 读入下一个字符 11. case '=': // 脱括号 12. Pop(OPTR); 读入下一个字符 13. case '>': // 栈顶优先级高，弹出并运算 14. theta = Pop(OPTR); 15. b = Pop(OPND); a = Pop(OPND); 16. Push(OPND, Operate(a, theta, b)); 17. } 18. } 19. } 20. return GetTop(OPND);这段骨架里，第 2 步的#很关键：它既是表达式结束标志，又是 OPTR 栈底的哨兵。第 4 行的循环条件用的是||，意思是“当前字符不是 #，或者运算符栈还没清空，就得继续处理”。比如输入1+2#，当读到 # 时，OPTR 栈里还有#和+，循环继续，把+弹出来算掉1+2，直到 OPTR 栈顶也变成#才退出。
第 14 到 16 行是运算的核心动作：从 OPTR 弹出一个运算符，从 OPND 依次弹出两个操作数。这里弹出顺序特别讲究，必须先弹b再弹a，因为栈顶是最右边刚压进去的操作数，而二元运算要求被减数、被除数在前，顺序错了减法除法就会出大问题。
2.3 为什么 # 既能当结束符又能当哨兵
很多初学者第一次看这份报告都会困惑：表达式里并没有#，为什么偏要用它结尾？其实#承担了两个职责。第一个是输入终止标记，告诉程序“表达式到这里结束”；第二个是 OPTR 栈底元素，用来兜底。当 OPTR 栈里只剩一个#时，说明所有运算符都已经处理完，整个表达式求值结束。
报告里那个循环条件while(c!='#'||GetTop(OPTR)!='#')可以这样理解：c是当前读到的字符，GetTop(OPTR)是运算符栈顶。只有两个条件同时满足“遇到 #”时，才算彻底结束。用||是因为存在一种情况，表达式已经读完（c是 #），但栈里还有没算完的运算符；也存在一种情况，栈已经空了但表达式还没读完。||写法能同时照顾这两边，初学者最容易踩的坑就是把这个条件改成&&，结果栈里残留运算符就提前退出了。
3. 从表到代码：优先级关系表的一维数组映射与栈结构定义
3.1 两个顺序栈的类型定义：char 栈和 int 栈不能混用
表达式由操作数、运算符和界限符组成，其中运算符只有 1 个字符，但操作数可能是多位数。报告里定义了两个不同的结构体，这是有原因的：如果只用一个 char 类型栈，整数12会被拆成'1'和'2'两个字符压进去，完全没法还原成数值。所以操作数栈必须是 int 类型。
/* 定义字符类型栈，用于存储运算符和括号 */ typedef struct{ int stacksize; char *base; char *top; } Stack; /* 定义整型栈，用于存储操作数和中间运算结果 */ typedef struct{ int stacksize; int *base; int *top; } Stack2;代码逻辑上，两个结构体完全对称：base指向栈底，top指向栈顶的下一个位置，初始时top = base表示空栈。stacksize记录当前分配的最大容量。两者的区别只在base和top指针的类型上，一个 char 一个 int，这决定了它们能存什么数据。
参数方面的经验是：STACK_INIT_SIZE设为 100 在课设场景通常够用，表达式一般不会超过这个长度。但要注意，报告里的代码没有调用realloc扩容，如果输入表达式特别长，压栈时top会越过base + stacksize造成越界写，这是隐藏风险。想省事就把初始大小调到 200 或 256，或者干脆补一个扩容逻辑。不过就课设验收而言，100 一般不会被卡。
3.2 Precede 查表实现：49 种组合、四种关系、下标换算
优先级比较是算符优先算法的灵魂。Operate()只负责加减乘除，Precede()才决定这些运算按什么顺序执行。报告里用了一个长度为 49 的一维字符数组，把 7 个运算符两两组合的优先关系全部列出来。
char Precede(char c1, char c2) { int i = 0, j = 0; /* 按 + - * / ( ) # 的顺序组成 7x7 优先关系表 */ static char array[49] = { '>', '>', '<', '<', '<', '>', '>', '>', '>', '<', '<', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>', '<', '<', '<', '<', '<', '=', '!', '>', '>', '>', '>', '!', '>', '>', '<', '<', '<', '<', '<', '!', '=' }; switch(c1) { case '+': i = 0; break; case '-': i = 1; break; case '*': i = 2; break; case '/': i = 3; break; case '(': i = 4; break; case ')': i = 5; break; case '#': i = 6; break; } switch(c2) { case '+': j = 0; break; case '-': j = 1; break; case '*': j = 2; break; case '/': j = 3; break; case '(': j = 4; break; case ')': j = 5; break; case '#': j = 6; break; } return array[7 * i + j]; }这个函数做的事情很简单：先把 c1、c2 映射成行号i和列号j，然后用7*i+j算出在一维数组里的偏移量，直接返回该位置的字符。array用static修饰，是因为这张表是只读常量，不需要每次调用都重新初始化。
表中四种字符的含义分别为：'<'表示栈顶运算符优先级低于当前运算符，当前运算符要入栈；'>'表示栈顶优先级高，可以弹出栈顶做运算；'='表示优先级相等，只出现在左括号和右括号相遇时，此时要脱括号；'!'是非法组合，比如')'遇到'('和'#'遇到')'，说明表达式里有括号配对错误。这里有个细节值得注意：'('对其他所有运算符都返回'<'，这让左括号无条件入栈，等右括号出现再强制把括号里的算式算完；')'对除左括号外的运算符都返回'>'，效果是遇到右括号时先把栈里能算的都算掉，直到碰到左括号。
3.3 为什么把优先级写进表里而不是写在代码里判断
有的实现会写成“如果 c1 是*或/，返回'>'”，用 if 分支直接判断优先级。报告选择查表，好处是统一了所有边界情况。比如左括号、右括号、#三者之间的优先关系，用 if 写会很啰嗦，查表却是一张棋盘盖下去，任何两个运算符都能立刻得到结果。代价是表本身不能写错一个字符，否则算出来的结果会很诡异，而且非常难排查。报告中数组顺序是严格按 7×7 排列的，每 7 个字符一换行，和表 1 一一对应。自己复现这份代码时，建议把表抄成同样的 7 行格式，用换行对齐来降低抄错概率，我见过不少人把某个<抄成>，导致2+3*4这种普通式子算出 20。
4. EvalExpr 主循环拆解：多位数读取和三个分支的合作
4.1 主循环条件：表达式结束与 # 两侧的判定
EvalExpr()是整个程序的主控函数。它通过一个全局指针ptr逐个扫描表达式字符串，每轮循环处理一个字符。函数开头有个容易看走眼的操作：c = *ptr++;先把当前字符赋给c，再把指针后移一位。也就是说，c是“当前待处理字符”，ptr指向下一个未读字符。
主循环条件while(c!='#'||GetTop(OPTR)!='#')前面已经解释过，这里再从代码层面看一遍。假设表达式是3*(7-2)#，当c读到最后的#时，OPTR 栈里还有#、*等运算符，条件左边为假，但右边GetTop(OPTR)!='#'为真，所以循环继续，把*弹出来执行乘法。直到 OPTR 栈里只剩底部的#，两边同时为假，循环退出，此时 OPND 栈顶就是最终结果。如果错用&&，程序会在c变成#的瞬间退出循环，栈里的*永远没机会计算，结果就错了。
4.2 操作数识别那段“玄学”代码：atoi 加 ptr 回退
操作数处理的代码是整个程序里最绕的一段，很多人抄下来能用，但完全不知道它为什么这么写：
if(!In(c)) { if(!In(*(ptr-1))) ptr = ptr - 1; /* 如果前一个字符也是数字，指针回退到数字段开头 */ m = atoi(ptr); /* 从当前位置读出一整个整数 */ n = num(m); /* 计算这个整数占几位 */ Push2(&OPND, m); /* 操作数压栈 */ ptr = ptr + n; /* 跳过这个数字段，指向下一个运算符 */ c = *ptr++; }逐行拆开看。In(c)为假，说明当前字符不是运算符，那就是数字。此时出现一个关键判断：if(!In(*(ptr-1)))，它检查当前字符的前一个字符。如果前一个字符也不是运算符，说明当前字符是一个多位数的中间位，而不是数字段的开头。举例来说，输入12+3#，第一次循环读入'1'时，前一个字符是'\0'或无关字符，不是运算符，所以不进 if。此时ptr指向'2'，atoi(ptr)会连续读'1'、'2'，遇到'+'才停，得到整数 12。num(12)用itoa转成字符串求长度，得到 2，于是ptr = ptr + 2，把指针从'1'移到'+'，下次循环正常处理运算符。
再想一种情况：如果不在数字段开头，而是已经处理完'1'，下一轮循环读入'2'，此时前一个字符'1'也不是运算符，ptr就回退到指向'1'的位置，再用atoi把12一口气读出来，然后再跳过两位。这就是这份报告处理多位数的方法：不逐位累加，而是用atoi配合指针跳跃。
这里最值得提醒的一点是：atoi遇到非数字字符会停止读取，所以它天然适合“从当前位置读到运算符为止”。而num()函数的作用是算出atoi到底读了多少位，以便把ptr精确地挪到下一位。理解了这段，你才能解释为什么123+1#能被正确算成 124。如果直接把单个字符压栈，123会被拆成'1'、'2'、'3'三个操作数，根本没法做运算。
4.3 '<'、'='、'>' 三个分支的语义
操作数是数字时走上面的分支，是运算符时则要根据Precede的结果走三个 case 之一：
else switch(Precede(GetTop(OPTR), c)) { case '<': /* 栈顶优先级低，当前运算符入栈 */ Push(&OPTR, c); c = *ptr++; break; case '=': /* 左右括号相遇，弹出左括号，忽略括号 */ x = Pop(&OPTR); c = *ptr++; break; case '>': /* 栈顶优先级高，弹出运算符并执行运算 */ theta = Pop(&OPTR); b = Pop2(&OPND); a = Pop2(&OPND); Push2(&OPND, Operate(a, theta, b)); break; }'<'分支的含义：栈顶运算符优先级比当前字符低，说明当前运算符“资格更老”，要先处理它后面的运算，于是把它压栈，并读取下一个字符。比如3*4+5读入*时栈顶是#，#对*返回'<'，*入栈，接着读4。等到读入+时，栈顶是*，*对+返回'>'，于是进入第三个分支，先算3*4得 12，压回 OPND，再继续比较+和栈顶，此时栈顶又变成#，+入栈。
'='分支只在(和)相遇时出现。栈顶是(，当前字符是)，优先级表返回'='，意思是括号配对成功，把左括号弹出，读下一个字符，括号对本身的“计算”就完成了。
'>'分支是真正的执行点。弹出theta、b、a之后，调用Operate(a, theta, b)。注意弹栈顺序：先弹b再弹a。操作数栈是后进先出，栈顶是右操作数，下面是被左操作数。比如表达式8/2，先压 8 再压 2，弹出时先得到 2（b），再得到 8（a），这样才能算出8/2=4。如果反过来，结果就是2/8=0，除法整除直接变 0，这种 bug 在课设里非常常见。
4.4 完整追踪 3*(7-2)#：十二步看清栈的变化
用报告里的例子跑一遍，能直观看到两个栈怎么配合。下面表格按“步骤、OPTR 栈内容、OPND 栈内容、当前字符、主要操作”列出：
| 步骤 | OPTR 栈 | OPND 栈 | 当前字符 | 主要操作 |
|---|---|---|---|---|
| 1 | # | 空 | 3 | 3是数字，压入 OPND |
| 2 | # | 3 | * | *优先级高于#，压入 OPTR |
| 3 | # * | 3 | ( | (对栈顶*返回<，压入 OPTR |
| 4 | # * ( | 3 | 7 | 7是数字，压入 OPND |
| 5 | # * ( | 3 7 | - | -对栈顶(返回<，压入 OPTR |
| 6 | # * ( - | 3 7 | 2 | 2是数字，压入 OPND |
| 7 | # * ( - | 3 7 2 | ) | )对栈顶-返回>，弹出-，计算7-2=5压回 |
| 8 | # * ( | 3 5 | ) | )对栈顶(返回=，弹出( |
| 9 | # * | 3 5 | ) | )对栈顶*返回>，弹出*，计算3*5=15压回 |
| 10 | # | 15 | # | #两边相遇，循环结束 |
| 11 | # | 15 | # | 返回GetTop2(OPND)，结果为 15 |
第 7 步是个关键节点：读入右括号时，说明括号内的表达式已经可以结算了，于是栈里-被弹出，7-2得到 5，压回 OPND。第 9 步继续弹出*，做最后的乘法。括号的作用被消解成一次“优先结算”的触发器，这正是算符优先算法的精髓。
5. 软件测试与避坑：五个会让程序崩掉的高频输入
5.1 测试用例怎么设计：从单数字到括号嵌套
报告第 4 章的软件测试部分相对简略，实际动手时建议按四个层次准备用例。第一层是基础用例，比如3#、1+2#，确认最基本的功能；第二层是多位数用例，比如12+34#、123*2#，专门压测第 4.2 节那段多位数读取代码；第三层是括号嵌套用例，比如(1+2)*(3+4)#、3*(7-2)#，验证优先级表和括号配对；第四层是异常输入，比如空串、括号不匹配、1/0#，这些虽然报告没要求，但课设验收时老师经常顺手输入。
一个比较完整的测试表可以参考：
| 输入 | 期望结果 | 覆盖点 |
|---|---|---|
3# | 3 | 单数字，最简路径 |
1+2# | 3 | 基本加法 |
12+34# | 46 | 多位数读取 |
3*(7-2)# | 15 | 括号与优先级 |
(1+2)*(3+4)# | 21 | 括号嵌套 |
8/2/2# | 2 | 左结合顺序 |
(1+2# | 报错或栈残留 | 括号不匹配 |
表格里最后一行比较特殊：(1+2#缺少右括号，程序读到#时会尝试计算，但 OPTR 栈里还有(，最终很可能弹出空栈或者返回错误结果。报告没有做括号配平校验，这是边界，不是 bug，但你自己用的时候要知道它存在。
5.2 避坑记录：现象、原因、解决办法
坑 1：程序一运行就乱码或崩溃。现象：直接printf输出一堆奇怪的数字，或者进程卡住。原因：main()里InitStack(&OPTR)之后忘了Push(&OPTR, '#')，OPTR 栈底是空的，GetTop(OPTR)读到未初始化的堆内存。解决：一定要在InitStack之后立刻压#，顺序不能反。这也是报告代码第 12 页附录里反复强调的“初始化运算符栈并压入 #”这一步。
坑 2：输入12 + 34#带空格时算错。现象：结果为 44，而不是 46。原因：空格不是运算符，In(c)返回 0，程序把空格当成数字处理，atoi(" +34")读到空格返回 0，或者进入奇怪的逻辑分支。解决：在main()里读入表达式后先过滤空格，常见做法是再写一个小函数，把空格字符剔除后再传给EvalExpr。课设代码通常用gets读整行，这个坑很容易踩。
坑 3：输入12#，结果只算成 3 或者 1+2。现象：多位数没有被当一个整体。原因：多位数处理代码写错，比如没用atoi，而是逐字符压栈，或者ptr回退逻辑没写。解决：严格按报告第 4.2 节的写法，if(!In(*(ptr-1)))判断 +atoi+num跳过数字段这三步缺一不可。复现后先拿123#测一次，再拿12+34#测一次。
坑 4：减法或除法结果不对，8-2算出 -6、8/2算出 0。现象：结果明显异常，而且只有减法和除法有问题，加法乘法正常。原因：EvalExpr里b=Pop2(&OPND); a=Pop2(&OPND);这两行顺序写反了，把a弹成了 2、b弹成了 8，导致2-8=-6。解决：按先右后左的顺序弹栈，或者干脆每次运算前把a、b打出来确认。这是课设里出现频率最高的逻辑 bug，没有之一。
坑 5：输入1/0#，程序直接崩了。现象：整数除法除零，运行时崩溃。原因：Operate()函数里的case '/'直接return (a/b)，没检查b是否为 0。报告算法规定操作数是正整数，所以作者没有处理除零，但实际验收时很容易被输入一个1/0#试一下。解决：在case '/'里加if(b == 0) { printf("除数不能为0\n"); exit(0); }或者返回一个特殊错误码。这个属于低成本增强，建议加上，至少不会当场崩掉丢分。
6. 再往前走一步：输入校验、负数支持与栈打印调试法
6.1 给表达式加一层合法性校验
报告的代码没有单独做输入合法性检查。课设验收时老师喜欢顺手输入一些怪东西，建议在调用EvalExpr()之前先跑一个简单的校验函数，把一半崩溃拦截在计算之前。校验逻辑至少包括三条：括号配平，用计数法或栈检查左右括号数量相等；首字符不能是运算符（负号除外）；两个运算符不能连续出现。
int checkExpr(char *s) { int cnt = 0; while(*s != '#') { if(*s == '(') cnt++; if(*s == ')') cnt--; if(cnt < 0) return -1; /* 右括号比左括号多 */ s++; } return (cnt == 0) ? 0 : -1; /* 最后括号必须配平 */ }这个函数的逻辑非常直白：遍历到#之前，维护一个括号计数，左括号加一，右括号减一。中途cnt小于 0，说明右括号先出现了，直接判非法；结束前cnt必须等于 0。返回 0 表示合法，-1 表示非法。在main()里调用时，返回 -1 就直接提示输入错误并退出。
6.2 把栈打印作为通用调试手法
EvalExpr内部是个黑匣子，看输出结果只能判断对错，看不出错在哪一步。我的习惯是在循环开头加一个打印函数，把两个栈的内容逐层输出，这样能直观看到每一步压了什么、弹了什么：
void printStacks() { char *p = OPTR.base; int *q = OPND.base; printf("OPTR栈:"); while(p != OPTR.top) printf(" %c", *p++); printf("\nOPND栈:"); while(q != OPND.top) printf(" %d", *q++); printf("\n"); }调用方式是在while循环开头加一行printStacks();，然后就能在屏幕上看到每一步两个栈的实时状态。比如第 7 步执行完，会看到 OPND 栈从3 7 2变成3 5，说明7-2算对了。这个辅助函数不影响业务逻辑，调试完记得删掉，或者用宏开关包起来。
我第一次上手这个程序时，就是在循环条件上把||写成&&，然后又忘了给 OPTR 压初始#，两个低级错误加在一起，输出结果是彻底乱掉的。后来把打印函数加上，三分钟就定位了问题。从那以后我每次写栈相关的课设，都强制先跑一遍覆盖空格、多位数、括号不匹配的用例表，再确认循环条件和弹栈顺序，最后才敢交。这份报告里的 Precede 优先关系表和双栈思路，值得反复看几遍，照着敲一遍再改一改，收获会比单纯背代码大得多，希望帮到你。
本文还有配套的精品资源，点击获取
