企业官网建设流程全解析

简介：这份数据结构实验报告面向大一下学期正在学习数据结构与算法课程的学生，聚焦「算数表达式求值」这一经典课程设计题目，帮助读者理解如何用栈与算符优先法解析含加减乘除及括号的表达式。报告完整呈现了设计思路、算法流程、核心函数封装、性能分析与运行结果，并给出除数为零、括号不匹配、非法符号等异常处理方案，还涉及栈的动态扩容与菜单交互设计。资源包为1个docx文档，约2.29MB，内容涵盖题目描述、运行环境、算法设计思想、流程图、函数调用关系、时间与空间复杂度分析及调试心得，结构完整，适合作为课程设计参考或算法练习的对照材料。目前已有3620人学习下载，读者可借此掌握双栈求值、优先级比较与边界处理等关键实现细节，并借鉴报告的组织方式与排错思路。

1. 从一份课程设计拆解算符优先法：栈到底在算什么

很多人第一次看到“算数表达式求值”这个题目，第一反应是“这不就是写个计算器吗”，然后随手用eval或者递归下降糊过去。但真正把这份数据结构课程设计从头到尾跑一遍，你会发现它考的不是“能不能算对”，而是“你知不知道栈在每一步到底存了什么”。这份资源是一份完整的 C++ 课程设计报告加源码，核心是用算符优先法配合两个栈——运算符栈和运算数栈——来解析并计算带括号的四则运算表达式。它适合正在做数据结构课设、想搞懂栈的实际应用、或者想拿一份能跑通的参考实现来对照调试的人。表达式以#作为起止标记，操作数限定为正整数，运算符只有加减乘除和英文括号，输入非法符号或除数为零时会直接终止并给出提示。整份代码三百多行，函数封装清晰，栈的扩容机制、优先级比较、中间结果保留两位小数这些细节都写进去了，拿来当课设底稿或者学习栈的实战案例都够用。

2. 算符优先法的核心机制：两个栈怎么配合

2.1 为什么是两个栈而不是一个

算符优先法的本质是把中缀表达式转成可顺序计算的形式，但它不像后缀表达式那样先转换再求值，而是一边读一边算。这里的关键在于：运算符的优先级决定了“什么时候能算”，而运算数需要按顺序暂存。一个栈存运算符，一个栈存运算数，两者通过优先级比较来联动。

具体来说，运算符栈oprt的栈顶元素代表“当前待处理的最高优先级运算符”，运算数栈num则按读取顺序存放已经解析出来的整数。每读到一个新运算符，就拿它和oprt栈顶比较：如果栈顶优先级更高，说明栈顶那个运算符的左右操作数已经齐了，可以立刻弹出计算；如果新运算符优先级更高，说明它要先算，那就压入oprt等后面的操作数；如果优先级相等，通常是括号匹配或者#对#，那就弹出栈顶但不计算。

这个机制的好处是不需要预先扫描整个表达式，读一个字符处理一个，时间复杂度 O(n)，空间复杂度也是 O(n)，因为最坏情况下三个栈（运算符栈、运算数栈、数字缓冲区）的深度都和输入长度成正比。

2.2 优先级比较函数的实现细节

源码里compare(char a, char b)这个函数是整份代码的逻辑核心，它返回<、>、=、!四种结果，分别对应“新运算符优先级高”“栈顶优先级高”“优先级相等”“非法组合”。下面把这段逻辑用表格整理出来，方便对照：

这张表建议直接对着源码看，因为compare函数里每个分支的返回值就是按这个逻辑写的。实际调试时如果发现计算结果不对，八成是某个分支的返回值写反了，比如把a == '(' && b == '#'写成了>而不是!，那遇到不匹配的括号就不会报错，反而会继续算下去。

2.3 数字缓冲区的处理逻辑

读入数字字符时不能直接压入num栈，因为像15这样的多位数需要先拼成完整的整数。源码里用了一个temp栈来暂存数字字符，每读到一个数字就压入temp，直到读到运算符时，再把temp里的字符按权重展开成整数。

这里有个容易翻车的点：temp栈的弹出顺序是反的。比如输入15，先读到1压栈，再读到5压栈，弹出时先出5再出1。所以拼数字的时候要用一个变量记录当前位的权重，从个位开始逐位累加。源码里虽然没有单独写一个temp栈的结构体，但逻辑上是等价的，用数组或者临时变量都能实现。

// 数字缓冲区拼装逻辑（从源码中提炼） double num = 0; int weight = 1; while (!tempEmpty()) { char digit; popTemp(&digit); // 从临时栈弹出字符 num += (digit - '0') * weight; weight *= 10; } pushNum(&numStack, num); // 拼好的整数压入运算数栈

这段代码的关键是weight每次乘 10，保证从低位到高位正确累加。如果写反了，15会变成51，而且这种错误在简单表达式里不容易发现，只有多位数运算时才会暴露。

3. 从零复现：编译、运行与栈变化追踪

3.1 环境准备与编译命令

这份源码支持 Dev C++ 和 Visual Studio 2019，但实际用 g++ 命令行编译也完全没问题。源码开头用了#include<iostream>、#include<string>、#include<stdlib.h>，没有依赖 Windows 特有的头文件，跨平台编译很省事。

# 假设源码文件名为 expression.cpp g++ -o expression expression.cpp -std=c++11 ./expression

编译时建议加上-Wall看警告，因为源码里有些地方用了malloc和realloc，如果忘记检查返回值或者类型转换不匹配，编译器会提醒。比如s->base = (char*)malloc(sizeof(char) * defaultsize);这行在 C++ 里需要显式转换，否则会报错。

运行后会先显示主菜单，提示输入x进入表达式计算，输入xxx退出。菜单逻辑在showMenu()和showMenu1()两个函数里，主菜单只在程序启动时显示一次，子菜单每次计算完成后显示，防止计算过程太长把主菜单刷掉。

3.2 输入合法表达式并观察栈变化

输入格式要求以#开头和结尾，比如#(7+15)*(23-28/4)#。程序会逐字符读取，每处理一个运算符就打印当前两个栈的内容。下面是一次典型运行的栈变化追踪：

这个追踪表建议自己跑一遍对照，因为源码里showStack函数会在每次入栈出栈后打印栈内容，但打印格式是%.2f，所以运算数栈里显示的是7.00、15.00这种。如果发现某一步栈内容和预期不符，就顺着compare函数的返回值往回查。

3.3 栈扩容机制的验证

源码里栈的默认大小是 10，每次扩容增加 5。这个机制在表达式很长或者嵌套括号很多的时候会触发。验证方法很简单：输入一个超过 10 个运算符的表达式，比如#1+2+3+4+5+6+7+8+9+10+11#，观察程序是否正常计算，以及有没有触发realloc。

// 扩容逻辑（运算符栈版本） if (s->top - s->base >= s->stacksize) { s->base = (char*)realloc(s->base, sizeof(char) * (s->stacksize + increasesize)); if (!s->base) { cout << "扩容失败！" << endl; return; } s->top = s->base + s->stacksize; // 重置 top 指针 s->stacksize += increasesize; }

这里有个隐藏的坑：realloc之后s->base的地址可能变了，所以s->top必须重新计算，不能保留原来的偏移。源码里s->top = s->base + s->stacksize;这行是对的，但如果有人自己改代码时忘了这步，扩容后top就指向了已释放的内存，程序会直接崩溃或者算出乱码。

4. 避坑与排查：那些让课设卡半天的细节

4.1 括号不匹配时程序不报错反而算错

现象：输入#(7+15*(23-28/4)#，少了一个右括号，程序没有提示错误，而是算出了一个莫名其妙的结果。

原因：compare函数里对(和#的组合返回了!，但主循环里遇到!时只是终止计算，没有打印具体的错误信息。更关键的是，如果左括号没闭合，oprt栈里会残留(，最后#对#的匹配条件不满足，程序会继续尝试计算，导致结果错误。

解决：在compare返回!时，除了终止计算，还要输出“括号不匹配”的提示。另外可以在主循环结束后检查oprt栈是否只剩一个#，如果不是就说明有未闭合的括号。

4.2 除数为零时直接崩溃

现象：输入#10/0#，程序没有给出友好提示，而是直接闪退或者输出inf。

原因：calculate函数里没有对除数做零值判断，直接做了除法。浮点数除以零在 C++ 里不会抛异常，但会得到inf或nan，后续压栈和显示都会出问题。

解决：在calculate函数开头加一个判断，如果operators == '/'且right == 0，就输出“除数不能为零”并终止计算。源码里其实已经提到了这个功能，但需要确认calculate函数里确实有这行判断。

double calculate(double left, double right, char operators) { if (operators == '/' && right == 0) { cout << "错误：除数为零！" << endl; exit(1); // 或者返回一个特殊值让上层处理 } switch (operators) { case '+': return left + right; case '-': return left - right; case '*': return left * right; case '/': return left / right; } return 0; }

4.3 非法符号导致死循环

现象：输入#7+15a#，程序没有提示非法字符，而是卡在某个循环里不动了。

原因：pd函数对非法字符返回 3，但主循环里没有处理返回值 3 的分支，导致a被当成数字字符继续走数字缓冲区的逻辑，而a - '0'得到的是一个很大的负数，后续计算出错。

解决：在主循环里对pd的返回值做完整判断，返回 3 时直接输出“非法字符”并终止。源码里pd函数已经写了这个逻辑，但主循环的调用处需要确认有没有漏掉else分支。

4.4 多位数拼装时权重算反

现象：输入#15+23#，结果是51+32=83而不是38。

原因：temp栈弹出顺序是从栈顶到栈底，如果拼数字时没有用权重累加，而是直接按弹出顺序拼接，就会把数字反转。

解决：严格按照“弹出字符乘以权重再累加”的方式拼装，权重从 1 开始每次乘 10。这个坑在单位数表达式里完全看不出来，只有多位数才会暴露，所以测试时一定要用两位数以上的操作数。

4.5 清屏后菜单丢失

现象：输入清屏指令后，窗口里只剩一个光标，主菜单和子菜单都不见了。

原因：清屏用的是system("cls")或system("clear")，清屏后没有重新调用showMenu()。

解决：清屏后立刻调用showMenu()重新打印主菜单。源码里showMenu1()的设计就是为了在每次计算后显示子菜单，清屏逻辑应该也走同样的路径。

5. 进阶技巧：把课设代码改成可复用的表达式求值模块

5.1 去掉菜单交互，暴露核心计算接口

课设代码把菜单和计算逻辑混在一起，想复用到其他项目里很不方便。最直接的办法是把main函数里的菜单循环抽掉，只保留createStack、push、pop、compare、calculate这几个核心函数，然后封装成一个evaluate(string expr)函数。

// 封装后的表达式求值接口 double evaluate(string expr) { OPRTstack oprt; NUMstack num; createStack(&oprt); createStack(&num); push(&oprt, '#'); int i = 0; while (i < expr.length()) { char c = expr[i]; if (pd(c) == 2) { // 解析完整数字 double val = 0; while (i < expr.length() && pd(expr[i]) == 2) { val = val * 10 + (expr[i] - '0'); i++; } push(&num, val); continue; } else if (pd(c) == 1) { char top = GetTop(&oprt); char cmp = compare(top, c); if (cmp == '<') { push(&oprt, c); i++; } else if (cmp == '>') { char op; pop(&oprt, &op); double right, left; pop(&num, &right); pop(&num, &left); push(&num, calculate(left, right, op)); } else if (cmp == '=') { char op; pop(&oprt, &op); i++; } else { cout << "表达式非法" << endl; return 0; } } else { cout << "非法字符" << endl; return 0; } } return GetTop(&num); }

这个接口的调用方式就是double result = evaluate("#(7+15)*(23-28/4)#");，返回352.00。注意表达式仍然需要以#开头结尾，如果想去掉这个限制，可以在函数内部自动补上。

5.2 支持负数和小数的改造思路

课设要求操作数是正整数，但实际用的时候难免遇到负数和小数。改造的关键点有两个：一是数字解析时要处理-作为负号而不是减号的情况，二是数字缓冲区要支持小数点。

负号的判断逻辑是：如果-出现在表达式开头、左括号后面、或者另一个运算符后面，那它就是负号而不是减号。可以在pd函数里加一个状态标记，记录上一个读到的字符类型。

小数点的处理更简单，在数字解析循环里加一个判断，遇到.就切换成小数模式，用weight除以 10 来累加小数部分。

// 支持小数的数字解析片段 double val = 0; double decimal = 0; double weight = 0.1; bool isDecimal = false; while (i < expr.length() && (pd(expr[i]) == 2 || expr[i] == '.')) { if (expr[i] == '.') { isDecimal = true; } else if (!isDecimal) { val = val * 10 + (expr[i] - '0'); } else { decimal += (expr[i] - '0') * weight; weight /= 10; } i++; } val += decimal;

这段代码在原有整数解析的基础上扩展了小数支持，改动量不大，但测试时要覆盖#3.14*2#、#0.5+0.25#这种边界情况。

5.3 用栈变化日志做自动化验证

课设要求显示栈的变化过程，这个功能其实可以反过来用作自动化测试的断言依据。比如写一个测试脚本，对每个表达式记录每一步的栈内容，然后和预期结果对比。如果某一步不一致，就能精确定位到是哪个运算符的优先级比较出了问题。

我一般会这样做：先把showStack的输出重定向到一个字符串流，然后在测试用例里逐行比对。虽然课设代码没有内置测试框架，但手动跑几个典型表达式——带括号的、多位数运算的、除数为零的、括号不匹配的——基本就能覆盖大部分逻辑分支。

从那以后我每次拿到类似的栈应用题，都会先把优先级比较表画出来，再对着表逐行检查compare函数的返回值，最后用多位数和嵌套括号的表达式跑一遍完整流程。这套习惯帮我省了不少调试时间，也希望帮到你。

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