简介这份实验报告围绕“算数表达式求值”课程设计展开面向正在学习数据结构与算法、需要完成栈相关课程设计的大中专学生。程序采用算符优先法处理含括号的加、减、乘、除混合表达式借助运算符栈oprt、数字栈num和临时栈temp完成运算从键盘读入以“#”为边界的合法表达式输出计算结果并显示输入序列和栈的变化过程。报告完整介绍了算法设计思想、运算符优先级关系、核心功能函数创建栈、出入栈、判空、取栈顶、优先级比较、中间计算等、主要流程图和运行效果截图还分析了时间与空间复杂度均为O(n)适合直接对照实现代码和撰写报告。文档额外补充了栈满动态扩容、除数为0、非法输入、括号不匹配等异常处理说明体现出从“能算”到“可靠”的工程考量。整个资源为1个docx文档压缩包大小2.29MB目前已有3620人浏览学习可作为课程设计报告模板、编码调试参考及答辩准备材料。1. 算数表达式求值这门数据结构实验卡住你的不是语法算数表达式求值是数据结构课程里出现频率最高的一类实验给一串中缀表达式比如12*3要按运算符优先级算出结果。很多人的程序调不通问题根本不是语法写错而是没想清楚栈的进出时机——运算符要等优先级更高的运算符算完才能出场这个“等待”正是栈存在的意义。这项实验覆盖的是线性结构上的状态记忆搞懂它之后括号匹配、编译原理的词法分析、逆波兰式计算器都能顺手打通。它适合正在写数据结构实验报告的学生、期末复习和考研刷题的人以及想补一补栈应用的开发者。本文按实验报告的顺序走先立原理再给可直接编译的 C 语言实现最后是翻车现场和批量验证方法。2. 中缀转后缀把人的优先级装进栈里2.1 人读中缀机器读后缀两种表达式的本质差异先看两个式子。中缀表达式12*3人一看就知道先乘后加结果是 7。但计算机从左读到右读到时并不知道后面还有个*在等着。如果直接“见一个运算符算一个”就会算出(12)*39错了。后缀表达式把运算顺序直接写进排列里1 2 3 * 从头到尾读一遍数字压栈遇到*弹出两个数相乘再压栈最后遇到弹出两个数相加结果是 7。整个过程中不需要任何优先级判断因为后缀式里*已经在前面时机被编码进了序列。后缀表达式也叫逆波兰式。它的核心价值是消除了括号和优先级的二义性任何中缀式都能无损转成后缀式转换时优先级和括号已经折算进序列。这就是为什么几乎所有求值程序都走“中缀转后缀、后缀求值”两步而不是在中缀上直接加优先级逻辑——后者要把优先级表嵌进求值循环边界情况多到难以收场。实验报告里常会问“为什么不直接扫描中缀求值”这里给一个可以写进报告的答案中缀求值必须随时预判后续运算符等效于在扫描过程中维护一个运算符优先级栈把这一步拆成显式的“转后缀”每个阶段只做一件事程序可读性和正确性都显著更好。这个思想就是编译原理里词法分析与语法分析分离的雏形。2.2 运算符优先级与栈的进出规则转后缀的规则可以浓缩成一张表。设当前读到的运算符为 op栈顶为 top当前字符动作数字直接输出到后缀式运算符栈空或栈顶为左括号直接入栈运算符栈顶优先级 当前优先级当前入栈运算符栈顶优先级 当前优先级弹出栈顶输出重复比较再把当前入栈左括号直接入栈栈内优先级视为最低右括号弹栈并输出直到弹出左括号左括号本身不输出扫描结束弹空栈全部输出优先级表最简单的一版和-同级1*和/同级2。左括号要特殊处理栈内优先级必须设得极低比如 0这样括号后的任何运算符都能压进去。右括号不参与比较它只负责触发“弹到左括号为止”。为什么“栈顶优先级 当前”就要弹出因为栈顶那个运算符更“急”它的操作数已经齐了不先算它会破坏优先级。拿12*3举例读入栈读 2 输出读*时栈顶优先级 1 低于*的 2所以*直接入栈读 3 输出结束后先弹*再弹得到1 2 3 * 。换1*23读*入栈读时栈顶*优先级 2 大等于的 1弹出*输出入栈得到1 2 * 3 。这一弹一压就是整个栈逻辑的核心。2.3 括号是作用域不是运算符括号不进入后缀式它只改变运算符的出栈时机。细节有三个。第一左括号入栈后括号内的运算符都要压在它上面所以左括号的栈内优先级必须最低否则括号内的运算符永远出不来。第二遇到右括号时不断弹栈直到弹出左括号如果栈弹空了还没见到左括号说明右括号多余这是最常见的输入错误。第三括号内部按同样的规则运行相当于开了一个局部作用域弹到左括号即自动退出——这和函数调用栈的返回行为是同一个模型。有一个容易忽略的点每次取栈顶前先判空永远是这类程序的基本卫生习惯。写代码时把isOperator、getPriority、pop拆开每个函数只做一件事调试时能省大量时间。很多人把左括号当普通运算符入栈最后又把它输出到后缀式这就是没理解括号是作用域标记不是运算。2.4 后缀求值一路压栈遇到运算符再算后缀求值的流程比转换更简单读 token数字压栈读到运算符弹出两个数先弹出的是右操作数后弹出的是左操作数算完把结果压回去扫描结束后栈顶就是答案。以2 3 4 * 为例2、3、4 依次压栈读到*弹出 4 和 3算 3*412 压回读到弹出 12 和 2算 21214。这里必须记住弹出顺序对1 2 -扫描 1 压栈、2 压栈读到-时栈顶是 2先弹出的是b2再弹出a1结果是a-b-1。写成apop(); bpop()就会得 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是二维数组每一行存一个 tokenpostfixLen记录 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截取一段连续数字加小数点的子串这就是处理多位数和小数的关键少了这个循环123一定会被拆成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 章会专门讲。bstack[top--]先取到的是栈顶也就是后压入的数运算顺序必须保持a-b、a/b。除零分支用exit(1)直接退出比返回一个特殊值更干净至少不会带着inf继续算。3.4 实验报告的结构与测试用例表报告骨架一般按这个顺序写问题描述、数据结构设计、算法描述、核心代码、测试、复杂度分析、总结。老师看报告时重点看两处数据结构为什么选栈以及测试用例有没有覆盖边界。选栈的理由要写“运算符的延迟运算与栈的后进先出语义一致”不要只写“用栈实现”。测试表格建议做成这样每个用例标注覆盖点输入后缀式输出覆盖点121 2 3基本加法12*31 2 3 * 7运算符优先级(12)*31 2 3 *9括号改变优先级2*(34)/52 3 4 * 5 /2.8混合运算与除法12.5-3.512.5 3.5 -9多位数与小数复杂度分析写 O(n) 时间、O(n) 空间并说明为什么是线性每个字符最多入栈出栈各一次。加上除零检测和括号匹配失败检测报告里可以明确写“程序对非法输入做了防御性检查”这会比只跑通 12 的实验高一个档次。4. 求值程序最容易翻车的5个坑现象、原因与处理4.1 多位数和小数被拆成单字符现象输入123结果算出 5或者后缀式变成1 2 3 。原因逐字符处理数字时遇到一个数字立刻输出一个 token没有把连续的数字串读完整。isdigit(infix[i])只判断当前字符不负责“聚拢”它后面的数字。解决在数字分支里用while (isdigit(infix[i]) || infix[i] .) i;一直读到数字串末尾再用strncpy截取完整 token。第 3 章代码已经是这个写法但很多人会把它简化成单字符输出这是后缀式错乱的第一个源头。4.2 括号匹配失败导致栈操作越界现象输入(12*3程序崩溃或输出乱码输入12)弹栈弹到空栈。原因右括号处理时没有判栈空直接无限弹栈直到越界左括号多余时最后收尾弹栈把空栈也弹了一遍data[--top]访问到非法下标。解决右括号的while循环里加!isEmpty条件弹出的左括号要单独pop一次不要输出到后缀式最后收尾弹栈前判空。更稳妥的做法是扫描开始时先做一遍括号匹配预检左右括号数量一旦不相等直接报错退出不进入后续逻辑。4.3 减法、除法把操作数顺序写反现象2-3算出 18/4算出 0.25乘法和加法却正常。原因后缀求值时先弹出的是栈顶也就是表达式里靠后的数它是右操作数后弹出的是左操作数。写了apop(); bpop()就全反了。解决固定写成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 负数和空格读入阶段被忽略的细节现象-32解析失败或者带空格的1 2把数字拆成多个 token。原因一元负号缺少处理空格没有在预处理阶段剔除isdigit的连续读数字循环遇到空格就断开了。解决读入阶段把所有空格、换行、制表符全部删掉这是最简单的止血方案。一元负号的处理方式是预处理把开头的-和左括号后面的-替换成0-比如-32变成0-32(-32)变成(0-32)。替换后完全复用现有算法不用动求值核心。这个方案在实验报告里写清楚比硬撑一个负号状态机更可靠。4.6 用 printf 大法定位栈状态现象结果不对但看不出是在转换阶段错还是求值阶段错。原因栈是黑匣子中间状态不可视化靠肉眼盯着代码很难定位。解决在push和pop的位置各加一行fprintf(stderr, push/pop: %s, top%d\n, val, s-top);跑一遍12*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], inputexpr \n, capture_outputTrue, textTrue) 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 变量替换让表达式支持字母进阶实验最常见的要求是支持变量比如ab*c进入求值前先给a、b、c赋值。常见做法是在读入后做一次字符替换遍历输入遇到a就替换成对应的数字字符串替换完再交给中缀转后缀。替换表用一个简单的结构体数组就够了两三个变量用if都可以。这个扩展不需要改动转换和求值核心却能让实验报告多出一节“扩展功能”在答辩或验收时是个不错的亮点。我做这个实验时中缀转后缀写了三版才完全跑通最后发现所有 bug 都集中在 4.3 提到的顺序问题上。从那以后我养成了习惯写栈程序先列测试用例再动手写逻辑不急着敲代码。这个习惯帮我避开了后面不少坑也希望帮到你。本文还有配套的精品资源点击获取