数据结构课程设计_带括号的算术表达式求值

课程设计报告课程名称数据结构课程设计题目算术表达式求值指导教师设计起始日期 4.18~4.25学院计算机学院系别计算机科学与工程学生姓名班级/学号成绩一、需求分析设计一个算术表达式四则运算的程序，要求完成包括加、减、乘、除运算，包含括号的基本整数表达式的运算。

在这里运算数可以1位长度，也可以多位长度。

在运算之后输出的正确运算结果，输入表达式后演示在求值中运算数栈内的栈顶数据变化过程，最后得到运算结果。

（1）输入：3*（7-2）（2）输出：数据栈栈顶元素：3,7,2,7,5,3,15结果：15（3）自选数据二、概要设计1、使用栈的数据结构表示数据的存储。

2、设计算法将中缀表达式转换成后缀表达式，用栈的数据结构实现表达式的运算。

3、把中缀表达式转换为后缀表达式算法的基本思路是从头到尾地扫描中缀表达式中的每个字符，对于不同类型的字符按不情况进行处理。

三、详细设计数据结构：字符类型栈/* 定义字符类型栈*/typedef struct{char stackname[20];char *base;char *top;} Stack;算法：将中缀表达式转换为后缀表达式void Change(char* s1, char* s2)// 将字符串s1中的中缀表达式转换为存于字符串s2中的后缀表达式{Stack R; // 定义用于暂存运算符的栈InitStack(R); // 初始化栈Push(R,'#'); // 给栈底放入’#’字符，它具有最低优先级0int i,j;i=0; // 用于指示扫描s1串中字符的位置，初值为0j=0; // 用于指示s2串中待存字符的位置，初值为0char ch=s1[i]; // ch保存s1串中扫描到的字符，初值为第一个字符while( ch!='#'){ // 顺序处理中缀表达式中的每个字符if(ch==' ')// 对于空格字符不做任何处理，顺序读取下一个字符ch=s1[++i];else if(ch=='('){ // 对于左括号，直接进栈Push(R,ch);ch=s1[++i];}else if(ch==')'){ // 对于右括号，使括号内的仍停留在栈中的运算符依次// 出栈并写入到s2中while(Peek(R)!='(')s2[j++]=Pop(R);Pop(R); // 删除栈顶的左括号ch=s1[++i];}else if(ch=='+'||ch=='-'||ch=='*'||ch=='/'){ // 对于四则运算符，使暂存在栈中的不低于ch优先级// 的运算符依次出栈并写入到s2中char w=Peek(R);while(Precedence(w)>=Precedence(ch)){ // Precedence(w)函数返回运算符形参的优先级s2[j++]=w;Pop(R); w=Peek(R); }}四、调试分析调试：在设计过程中出现程序不能运行，发现不能找到结束标识符，因此在设计的时候需要人为动态添加结束标识符‘#’，顺利运行算法时间和空间分析：算法的运行时间主要花在while循环上，它从头到尾扫描后缀表达式中的每一个数据（每个操作数或运算符均为一个数据），若后缀表达式由n个数据组成，则此算法的时间复杂度为O(n)。

课程设计报告课程设计名称：数据结构课程设计课程设计题目：算术表达式求值的实现院（系）：*****专业：*****班级：*****学号：*****姓名：*****指导教师：*****目录1 课程设计介绍 (1)1.1课程设计内容 (1)1.2课程设计要求 (1)2 课程设计原理 (2)2.1课设题目粗略分析 (2)2.2原理图介绍 (2)2.2.1 功能模块图 (2)2.2.2 流程图分析 (3)3 数据结构分析 (5)3.1存储结构 (5)3.2算法描述 (5)4 调试与分析 (7)4.1调试过程 (7)4.2程序执行过程 (7)参考文献 (8)附录（关键部分程序清单） (9)1 课程设计介绍1.1 课程设计内容编写算法能够进行整型和实型数的表达式求值，能够根据运算的数据选择正确的运算结果的数据类型，表达式的运算符为：+，—，*，/，（，），且括号可以嵌套。

1.2 课程设计要求1.给出必要的输入、输出信息和提示信息。

2.参考相应的资料，独立完成课程设计任务。

3.交规范课程设计报告和软件代码。

2 课程设计原理2.1 课设题目粗略分析根据课设题目要求，拟将整体程序分为三大模块。

此三个模块相互独立，没有嵌套调用的情况，以下是三个模块的大体分析：1.首先依次定义字符类型栈、整型栈、运算符栈和操作数栈，构造运算符栈和操作数栈，然后运算符、操作数依次入栈。

2. 依次读入表达式，若是操作符即进OPND栈，若是运算符即进OPTR栈。

顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。

3. 按照运算符的优先级别对表达式进行求值运算。

2.2 原理图介绍该功能模块图介绍了这个程序的主要功能。

2.2.1 功能模块图图2.1功能模块图如图2.1所示,要实现表达式的求值，即必须要实现存储、读取和计算三项功能。

算术表达式的求解-数据结构课程设计报告数据结构》课程设计报告书题目：算术表达式的求解系别：计算机科学与应用数据结构课程设计目录一、需求分析1、设计要求：本程序需要实现对算术表达式的求解功能，可以支持基本的四则运算，包括加、减、乘、除，同时还需要支持括号的使用。

2、设计构想：我们将使用栈来实现算术表达式的求解。

具体地，我们将把中缀表达式转换为后缀表达式，然后再利用栈来求解后缀表达式。

二、概要设计1、本程序包含的模块：本程序包含两个模块：中缀表达式转后缀表达式模块和后缀表达式求解模块。

三、详细设计1、定义栈结构我们定义一个栈结构，用来存储算术表达式中的运算符和操作数。

具体地，栈中的每个元素都包含两个属性：元素的值和元素的类型。

元素的值可以是一个数字或一个运算符，元素的类型可以是数字或运算符。

我们使用一个数组来实现栈的结构。

为了方便起见，我们还需要定义一些基本的栈操作，如入栈、出栈、判断栈是否为空等。

2、栈的基本操作栈是一种常见的数据结构，具有后进先出（LIFO）的特点。

栈的基本操作包括初始化栈、入栈、出栈、取栈顶元素和运算模块。

1) 初始化栈初始化栈是指将栈的各项属性设置为初始状态。

通常包括将栈顶指针设为-1，表示栈为空。

2) 入栈入栈是指将元素压入栈顶。

入栈操作需要将栈顶指针加1，并将元素存入栈顶位置。

3) 出栈出栈是指将栈顶元素弹出。

出栈操作需要将栈顶元素取出，并将栈顶指针减1.4) 取栈顶元素取栈顶元素是指获取栈顶元素的值，但不将其弹出。

取栈顶元素操作只需要返回栈顶元素的值即可。

5) 运算模块栈可以用于实现各种运算，例如中缀表达式的转换和计算、括号匹配等。

运算模块需要根据具体需求进行设计和实现。

3、判断运算符的优先级在进行中缀表达式的转换和计算时，需要判断运算符的优先级。

通常采用栈来实现这一功能。

具体实现方法是将运算符入栈，当遇到新的运算符时，将其与栈顶运算符进行比较，如果新运算符的优先级高于栈顶运算符，则将其入栈，否则将栈顶运算符弹出并输出，直到新运算符可以入栈为止。

ＸＸXＸXX大学《数据结构》课程设计报告班级：学号：姓名：指导老师:目录一算术表达式求值一、需求分析二、程序得主要功能三、程序运行平台四、数据结构五、算法及时间复杂度六、测试用例七、程序源代码二感想体会与总结算术表达式求值一、需求分析一个算术表达式就是由操作数(oｐeranｄ）、运算符(operator）与界限符（deｌimiter)组成得。

假设操作数就是正整数，运算符只含加减乘除等四种运算符,界限符有左右括号与表达式起始、结束符“#”，如：＃(7+15）*（2３—２8/４）#。

引入表达式起始、结束符就是为了方便.编程利用“算符优先法”求算术表达式得值.二、程序得主要功能（1）从键盘读入一个合法得算术表达式，输出正确得结果。

(2）显示输入序列与栈得变化过程。

三、程序运行平台Ｖｉsｕaｌ C＋+6、0版本四、数据结构本程序得数据结构为栈。

（1）运算符栈部分：struct SqStaｃk ／/定义栈{char *base； //栈底指针ｃｈａr *toｐ; ／/栈顶指针inｔstacｋsiｚe； //栈得长度};inｔInitSｔack (SqＳｔack &ｓ) //建立一个空栈S{ｉf （!(s、ｂａse= (char ＊）ｍalloc(5０＊ｓizeof（chａr）)）)exｉt（0）；ｓ、ｔop=s、bａse;s、staｃksiｚｅ=５0；retuｒn OK；}ｃhar GeｔTop（SqStack s,char &e) /／运算符取栈顶元素｛iｆ (s、ｔop==s、ｂase) //栈为空得时候返回EＲROR｛ﻩ prｉntf(＂运算符栈为空！＼n")；ﻩ reｔurn ERＲＯR;｝elsee＝*（s、ｔoｐ-1); //栈不为空得时候用ｅ做返回值，返回S得栈顶元素，并返回OK returnＯＫ;｝ｉnt Push(SqStacｋ＆s，cｈａr ｅ） //运算符入栈｛if （s、tｏp—s、baｓe >= ｓ、ｓtacksｉzｅ）ﻩ{ｐriｎtf（＂运算符栈满!＼n"）;ﻩs、basｅ=（cｈaｒ*）reａlloｃ(s、bａｓe，(s、sｔackｓｉze+5)*ｓizeoｆ(cｈar））；//栈满得时候,追加5个存储空间ｉf(！s、basｅ)exｉt （OVERＦＬOW）；s、top=s、ｂａsｅ+s、ｓｔacｋsize;s、ｓtaｃksiｚｅ+=５;}ﻩ＊(s、ｔop）＋＋=e；／/把e入栈ﻩｒeturn OK;}ｉnｔ Pop(SqStaｃk &ｓ，char ＆ｅ） /／运算符出栈｛ｉｆ (s、toｐ==s、base) ／/栈为空栈得时候，返回ERＲOＲ｛ｐrintf（＂运算符栈为空!\n”）;ﻩ return ERROＲ;}else｛ﻩﻩe=＊-—ｓ、tｏp；/／栈不为空得时候用e做返回值，删除S得栈顶元素，并返回ＯK return OK；}}iｎt StackTｒaｖerse（ＳqStacｋ&ｓ)／/运算符栈得遍历｛ﻩchar ＊t；ﻩt=s、ｂａｓｅ；ﻩif (s、top＝=s、baｓe）｛ﻩ printｆ（”运算符栈为空！\ｎ”)； //栈为空栈得时候返回ＥＲRORｒeturn ERＲOＲ;}ｗhile（t！＝s、tｏp)｛ﻩﻩｐrｉｎｔf（" %c",＊t)； //栈不为空得时候依次取出栈内元素t++;ﻩ}ｒeturｎ EＲRＯR；｝（2）数字栈部分：strｕｃt SqSｔackn//定义数栈｛ｉnt *bａse; //栈底指针ｉnt＊tｏp； //栈顶指针ｉnｔ sｔacksｉze； //栈得长度｝;inｔIｎｉtStackｎ (SqSｔackn &s) //建立一个空栈Ｓ{s、base=（int＊）malｌoc（50*sｉzeof(int）);if(！ｓ、ｂase）eｘiｔ（OVEＲFLＯW）；//存储分配失败s、top=s、base；s、stacksizｅ=5０;reｔuｒn OK；｝ｉｎt GｅtToｐn(ＳqＳtａcｋn s,inｔ＆e) //数栈取栈顶元素{if（s、ｔop=＝s、base）{prinｔｆ(＂运算数栈为空!\ｎ＂);//栈为空得时候返回ERRORﻩ rｅturｎ ERROR;}eｌseﻩe＝＊（s、toｐ-1);／/栈不为空得时候，用e作返回值，返回S得栈顶元素，并返回OＫreturｎＯK；｝int Pｕshn（SｑStａckn ＆s，int ｅ) //数栈入栈｛if（s、tｏp—s、ｂasｅ＞＝s、stacksiｚe)｛ﻩﻩprｉｎｔf（"运算数栈满!\ｎ"）；／/栈满得时候,追加5个存储空间ﻩs、base=(int＊）realloc (s、baｓe,(s、stａcksize＋5)＊sｉzｅof（ｉnt));ｉf（!s、base) ｅxit (ＯＶERFLOW)；ﻩs、top=ｓ、bａsｅ＋ｓ、stacｋsize;//插入元素e为新得栈顶元素s、stacksｉｚe+=5；}*（s、top）++=e; /／栈顶指针变化returｎOK;}ｉｎt Popｎ(ＳｑSｔacｋn ＆s，iｎt &e)//数栈出栈｛ﻩif （s、top=＝ｓ、base）｛ﻩ pｒiｎtｆ（"运算符栈为空！\n＂);//栈为空栈得视时候，返回ERRＯＲﻩ retｕrn ERROR；ﻩ｝ｅlse｛ﻩﻩe=＊—-ｓ、tｏp；／/栈不空得时候，则删除S得栈顶元素,用e返回其值，并返回OK ﻩreturｎOK；｝}ｉnt StacｋＴraveｒsｅn（SqStackn &s)/／数栈遍历{ﻩiｎｔ＊t;ﻩｔ=s、basｅ ;ﻩif（s、top==s、basｅ）ﻩ｛pｒinｔf(＂运算数栈为空！\n”）；//栈为空栈得时候返回ERRORﻩ rｅｔｕrn ERＲＯＲ；ﻩ｝ﻩwｈile（t！=ｓ、ｔop)ﻩ{priｎtf(” ％d”，*ｔ); /／栈不为空得时候依次输出t＋＋;｝return ERRＯR；｝五、算法及时间复杂度１、算法:建立两个不同类型得空栈,先把一个‘＃’压入运算符栈。