简介这是一份面向数据结构课程设计的大一下学期实验报告围绕“算数表达式求值”完整呈现利用栈与“算符优先法”解析包含加减乘除、括号及#边界符的表达式的实现过程。报告从问题描述、运行环境、算法思想与流程图、核心代码到性能分析层层展开并额外实现了动态扩容、非法符号与除零检测、括号匹配检查等功能适合学习栈应用、表达式求值算法或准备课程设计的读者参考。压缩包内共1个docx文件约2.29MB包含报告正文、代码说明及运行截图可直接用于文档结构对照与算法思路梳理。资源已有3620人学习对理解中缀表达式求值、双栈协作与运算符优先级处理有较实用价值。1. 算数表达式求值实验到底在做什么从“人读算式”到“机读算式”算数表达式求值是数据结构课程里出现频率最高的实验报告题目之一很多学校的课程设计、数据结构期末复习和考研机试都会拿它做原型。这个实验不涉及多复杂的算法但它把栈、运算符优先级、括号匹配、连续数字扫描这些知识点一次串起来很多人上课觉得听懂了真让程序算34*2和(34)*2时才发现结果对不上。这篇笔记按我实际写过、也帮人改过这类实验报告的经验来写讲清楚实现路径、关键代码和最容易翻车的地方。适合正在写实验报告的人也适合想用最短时间把这块知识补扎实的考研党。2. 为什么数据结构实验都选“中缀转后缀”优先级表、栈与选型理由2.1 为什么不是直接求值而是先转后缀一种适合实验报告的拆法人写的算式叫中缀表达式运算符夹在两个操作数中间比如34*2。机器直接读中缀很别扭因为和*谁先算不是由位置决定的而是由优先级表决定的再加上括号扫描一遍根本算不干净。后缀表达式则完全不同它把运算符放到操作数后面34*2写成3 4 2 * 这种形式没有括号、没有优先级只有“数字、数字、运算符”的线性序列。计算后缀表达式只需要一个栈遇到数字压栈遇到运算符弹两个数运算再压回去一遍扫完结果就在栈顶。为什么不直接用“双栈一次扫描”的算法双栈法确实能在一个循环里同时处理操作数和运算符但转换和计算耦合在一起中间状态只有两个栈出错了很难定位是优先级判断错还是求值错。递归下降法能力更强能处理一元负号、函数调用、赋值语句但对一份数据结构实验报告来说设计偏重而且递归的栈帧和“用数据结构栈”不是同一个考点。最稳妥的拆法是“中缀转后缀 后缀求值”两步走每一步都能打印中间结果单独验证报告里也能把“逆波兰式”这个考点一起覆盖。实验报告交上去老师问你为什么这么设计你可以直接说第一步负责消解优先级和括号第二步负责纯计算职责分离。这个拆法还有一层好处中缀转后缀的过程本身就是对栈“后进先出”语义最直观的展示。运算符压在栈里等待比自己优先级更高的运算符先输出括号用来强制改变等待顺序这比单纯用栈做括号匹配要深一层。报告里能把“栈在这里到底存了什么”讲清楚比贴一大段代码更有说服力。2.2 优先级表与转换四规则报告里这张表比代码更值钱中缀转后缀的规则可以浓缩成一张表。我的习惯是在报告里先画优先级表再写代码因为代码只是这张表的翻译运算符优先级数值说明-1二元加减左结合*/2二元乘除左结合(0压栈后视作最低保证括号内运算符先处理转换流程从左到右扫描输入串四句话就能说完数字连续读入直接输出到后缀串左括号无条件入栈右括号不断弹栈输出直到栈顶是左括号再把左括号弹出丢弃运算符与栈顶运算符比较优先级栈顶不低于当前运算符就弹栈输出重复这一步直到栈顶优先级更低或遇到左括号然后把当前运算符入栈。注意第4条用的是“不低于”也就是。原因是加减乘除都是左结合遇到同优先级运算符时要先让前一个出去。比如3-2-1如果栈顶是-再遇到一个-必须把栈里的-弹出来后缀才是3 2 - 1 -结果是0。写成会导致后缀变成3 2 1 - -计算时变成3-(2-1)2整份报告就错了。我在报告里还会补一句转换过程天然能检测括号匹配。如果遇到右括号时栈已经为空或者弹到底都没遇到左括号说明输入里括号不配对。这个细节写在“异常处理”小节里老师会认为你想过输入不合法的情况。调试时我的习惯是每处理完一个字符就把当前后缀串和栈内容打出来对照纸上手推的结果。转后缀这段逻辑一旦写错后面求值代码再对也白搭。2.3 后缀求值的弹出顺序一个栈够用但左右操作数不能反后缀求值的流程比转换更简单用一个例子就能讲明白。3 4 2 *读到3压栈读到4压栈读到弹出4和3算347压回去读到2压栈读到*弹出2和7算7*214结束。整个过程只有一个操作数栈运算符只是“信号”告诉程序现在该消费最近的两个操作数了。这就是选栈的核心理由中间结果被临时记住且消费顺序正好是最晚压栈的最先被用。这里有个隐蔽的考点几乎每个第一次写的人都会踩。弹出两个操作数的时候先弹出来的是右操作数。后缀表达式的顺序是a b op压栈时a先进b后进弹出时先拿到b再拿到a所以代码要写成b pop(); a pop();然后执行a op b。如果顺手写成b op a3-2会算出-1减法和除法全反。排查这个问题有个笨办法把后缀串和计算结果对着看3 2 -期望是1出来-1那一定就是弹出顺序反了。3. 用 C 语言手写算数表达式求值完整代码与参数设计3.1 完整可运行代码转换与求值两个函数一次实现下面这份代码是我给学生讲实验时常用的版本。它不追求一行代码写三个功能而是把每个分支单独列出来方便对照上一章的规则看。输入约定为操作数是整数运算符只支持 - * /和小括号不支持空格、小数和一元负号。计算结果用double保存避免整数除法截断。#include stdio.h #include string.h #include ctype.h #include stdlib.h #define MAX 100 // 表达式最大长度 // 运算符优先级数字越大越优先 int priority(char op) { switch (op) { case : case -: return 1; case *: case /: return 2; case (: return 0; // 左括号压栈后优先级最低保证括号内运算符先出栈 default: return -1; // 非法字符 } } // 中缀转后缀结果写入 postfix数字之间用空格分隔 void to_postfix(const char *expr, char *postfix) { char stack[MAX]; int top -1; int i, j 0; for (i 0; expr[i] ! \0; i) { char c expr[i]; if (isdigit(c)) { // 连续数字组成一个完整操作数整体输出 while (isdigit(expr[i])) { postfix[j] expr[i]; } postfix[j] ; // 操作数输出后加空格分隔 i--; // 回退到非数字字符for 循环的 i 会重新落到它 } else if (c () { stack[top] c; } else if (c )) { // 弹栈到左括号弹出来的运算符都进后缀串 while (top ! -1 stack[top] ! () { postfix[j] stack[top--]; postfix[j] ; } if (top ! -1) top--; // 弹出左括号本身括号不出现在后缀串里 } else if (priority(c) 0) { // 栈顶优先级不低于当前运算符时先弹栈保证左结合 while (top ! -1 stack[top] ! ( priority(stack[top]) priority(c)) { postfix[j] stack[top--]; postfix[j] ; } stack[top] c; } } // 扫描结束栈里剩下的运算符依次输出 while (top ! -1) { postfix[j] stack[top--]; postfix[j] ; } postfix[j] \0; } // 后缀求值返回最终结果 double eval_postfix(const char *postfix) { double stack[MAX]; int top -1; int i 0; while (postfix[i] ! \0) { if (postfix[i] ) { i; continue; } if (isdigit(postfix[i])) { double num 0; while (isdigit(postfix[i])) { num num * 10 (postfix[i] - 0); i; } stack[top] num; } else { double b stack[top--]; // 先弹出的是右操作数 double a stack[top--]; // 后弹出的是左操作数 switch (postfix[i]) { 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; } i; } } return stack[top]; } int main() { char expr[MAX]; char postfix[MAX * 2]; printf(请输入表达式整数、 - * / 和小括号不支持空格: ); scanf(%s, expr); to_postfix(expr, postfix); printf(后缀表达式: %s\n, postfix); printf(计算结果: %.6g\n, eval_postfix(postfix)); return 0; }逻辑说明to_postfix里四个分支和上一章的四条规则一一对应最容易看混的是数字分支里的i--。当while (isdigit(expr[i]))退出时i已经停在了非数字字符上i--回退一位交给for循环的i再前进最终刚好重新指向这个非数字字符。这个写法省一个辅助变量但注释一定要写清楚。eval_postfix的操作数栈是double数组运算符分支先弹b再弹a减法和除法必须按a op b计算。除零检查放在b 0时直接退出实验场景下比返回特殊值更直观。3.2 参数怎么调、输入怎么扩展栈容量、数值类型、格式串三个必改点下面这几个参数是实验变体里最常改的地方也是报告里“设计说明”一节可以写的内容参数/配置本代码取值实验扩展时的改法表达式最大长度MAX100改成strlen(expr)1动态分配栈或读入后先算长度再定数组后缀串数组大小MAX*2MAX*2足够容纳运算符和空格如果支持一元负号建议再加 50%操作数类型double输入仍按整数读运算用 double想支持小数需在数字扫描里加小数点判断输出格式%.6g自动去掉多余尾零5/2输出2.5如果实验要求支持带空格的表达式把scanf(%s, expr)换成fgets(expr, MAX, stdin)然后在to_postfix的循环开头跳过空白字符即可。注意fgets会把换行符也读进数组处理时要去掉末尾的\n。这个改动很小报告里可以单独写一小段“输入预处理”属于典型的白给步骤分。还有一个容易忽略的运行细节如果你改造成命令行传参比如./calc (12)*3那括号前后必须加双引号否则 shell 会把括号当成语法吞掉。从标准输入scanf读则没有这个问题。我在帮人调试时见过好几次“程序没问题是 shell 把参数拆了”的情况。4. 算数表达式求值的避坑清单从一元负号到测试用例的五个翻车点4.1 一元负号没处理-35直接把程序打崩溃现象输入-35或者2*-3程序要么输出错得离谱要么求值阶段直接算出负数加法的奇怪结果。原因一元负号和中缀减法在字符上都是-优先级表里只定义了二元减法没有定义“这个减号是负号”。转换阶段会把开头的-当成普通运算符压栈数字扫描又识别不了负号整个后缀串的顺序就是乱的。解决最简单的是在报告里明确写清“本实验只支持二元运算符”这不算偷懒很多教材版本就是二元起步。想做得完善常见做法是在词法层加一个判断如果-出现在表达式开头或者前一个字符是运算符或左括号就把它视为一元负号处理成“0 - 操作数”。比如-35在预处理阶段改写成(0-3)5后面逻辑完全不用动。这一步扩展量不大写在报告的“扩展实现”里很加分。4.2 右括号弹栈后忘了 pop 左括号后缀串里混进括号现象(12)*3正确结果应该是1 2 3 *实际输出变成1 2 ( 3 *或者计算时报错。原因右括号分支的while循环条件写成了“遇到左括号就停”循环结束后没有把左括号从栈里弹出。左括号留在栈里后续运算符弹栈时就会被它挡住甚至直接输出到后缀串。解决循环结束后补一句if (top ! -1) top--;把左括号丢弃。一个很实用的自检方法后缀串里一旦出现(或)说明右括号处理逻辑有 bug因为后缀表达式永远不该有括号。4.3 除法被 int 截断5/2算出2printf 打出垃圾值现象5/2期望2.5程序输出2。另一种更隐蔽的情况是结果算对了但printf用%d输出double屏幕上出现一串莫名其妙的数字。原因求值栈用的是int5/2在 C 里整除截断成2。后面一种则纯粹是格式化输出把 double 的位模式按整数解读属于未定义行为。解决操作数栈从int改成double所有运算按浮点走。printf 用%.6g它能把2.5输出成2.5把2.0输出成2最贴近人看的习惯。在报告的设计说明里写一句“运算全程使用 double 以避免整数除法精度丢失”老师一眼就能看到你考虑过数值边界。4.4 弹栈条件写成3-2-1被算成2现象100-50-20期望30程序算出70。3-2-1期望0算出2。原因弹栈条件写了而不是。遇到连续的两个同优先级运算符时前一个不弹栈导致后缀串变成3 2 1 - -。计算时对应3-(2-1)2减法和除法这类左结合运算符的语义被整体反转。解决把条件改成priority(stack[top]) priority(c)。这个坑的特征是加法和乘法没问题减法和除法一出错就是系统性的。测试用例里一定要放一条连续减法表达式比如100-50-20这条过了说明结合性基本正确。4.5 测试用例只有教科书样例加一张边界用例表报告立刻立体起来现象拿12*3和(12)*3测完就算“验证通过”交上去被老师指出嵌套括号、除法精度、连续减法都没测。解决构造一个覆盖边界的最小测试矩阵直接作为报告里的“测试与结果”表输入期望结果覆盖点12*37优先级基本规则(12)*39括号改变优先级100-50-2030左结合同优先级连续计算((12)*(34))-5/218.5嵌套括号与浮点除法5/22.5整数输入、浮点结果8/0除零错误异常分支这张表放进报告的“测试”章节比写三大段“测试充分”都有用。老师看报告时最关心的不是代码能不能跑而是你有没有想过边界条件。这张表本身就证明你想过了。5. 让实验报告再多拿 10 分用后缀表达式建树做自动对拍有精力的同学可以多做一步把后缀表达式进一步建成表达式树再用中序遍历把树还原成带括号的中缀表达式跟原始输入做对比。这相当于给求值器加了一个“自我检查”也是区分“能跑”和“可验证”的分水岭。做法不复杂。表达式树的后缀构建和后缀求值如出一辙遇到数字建叶子节点压栈遇到运算符弹出两颗子树组成新节点再压栈。我用数组模拟树的节点避免动态内存管理实验报告里更好解释typedef struct { double value; // 叶子存数值 int is_op; // 1 表示运算符节点 char op; // 运算符 int left, right; // 左右孩子在 nodes 数组中的下标 } TreeNode; int build_tree(const char *postfix, TreeNode nodes[], int *cnt) { int stack[MAX], top -1, i 0; while (postfix[i]) { if (postfix[i] ) { i; continue; } if (isdigit(postfix[i])) { double num 0; while (isdigit(postfix[i])) { num num * 10 postfix[i] - 0; } nodes[*cnt] (TreeNode){num, 0, 0, -1, -1}; stack[top] (*cnt); } else { int r stack[top--]; // 先弹出右子树 int l stack[top--]; nodes[*cnt] (TreeNode){0, 1, postfix[i], l, r}; stack[top] (*cnt); i; } } return stack[top]; // 树根在 nodes 中的下标 }建完树之后中序遍历并在恰当位置加括号就能还原出标准中缀表达式。把这个字符串和原始输入一比对转换和求值任何一步出错都会暴露出来。有余力还可以写一个小脚本随机生成合法表达式批量喂给程序把输出结果和期望值对拍。我当年写这个实验时只验证了三五个样例就交了后来被同学拿100-50-20一测就露馅那次教训之后我写任何表达式求值器都会先做一次树对拍。多花这 30 分钟报告的质量完全不在一个层次上。希望帮到你。本文还有配套的精品资源点击获取
