施磊磊的数据结构课程设计及报告2 表达式求值问题.docx

1、施磊磊的数据结构课程设计及报告2 表达式求值问题课程设计题 目 名 称 表达式求值问题 课 程 名 称 数据结构课程设计 学 生 姓 名 施磊磊 学 号 0813022057 班 级 计082 指 导 教 师 管致锦 数据结构课程设计及报告 表达式求值一、问题描述实验题目为表达式求值。要求接受用户输入一个中缀表达式（运算符为加、减、乘、除），然后通过借助于顺序栈实现将其转换为后缀表达式并将其打印，最后求出其值。设计主函数，使用户可以重复输入中缀表达式，求得表达式的后缀表达式和表达式的值。二、数据结构算法设计（一） 堆栈ADTADT Stack数据:0个或多个元素的线性序列（a0,a1,.,an

2、-1）,其最大允许长度为MaxStackSize。运算：Create(): 建立一个空栈。Destroy(): 撤销一个栈。IsEmpty(): 若空栈，则返回true；否则返回false。IsFull(): 若栈满，则返回true；否则返回false。Top(): 在x中返回栈顶元素。若操作成功，则返回true；否则返回false。Push(): 在栈顶插入元素x（入栈）。若操作成功，则返回true；否则返回false。Pop(): 从栈中删除栈顶元素（出栈）。若操作成功，则返回true；否则返回false。Clear(): 清除堆栈中全部元素。（二）顺序栈类在此题目中，借助了c+的模板抽象

3、类来定义栈抽象数据类型，程序如下：顺序堆栈类：includetemplate class Stackprivate:T * stack; /指向数组的指针int top; /栈顶指针int maxTop; /最大栈顶指针public:Stack(); /构建一个构造函数；初始化栈void Push(T item); /进栈T Pop(); /出栈，删除栈顶元素T Peek(); /返回栈顶元素bool EmptyStack(); /判断是否为空栈Stack() delete stack; /释放并清空栈的存储空间void Clear()top=-1; /清除栈中全部元素三、算法原理（一）头文件

4、名在本程序中，运用的头文件有一些是在平时经常用到的，也有一些是少见甚至是很陌生的。它们为函数中的一些语句提供了帮助并发生着作用。（二）描述算法及算法原理1、 在class Stack 中1）Stack()：构建一个构造函数；用于初始化栈，构建一个空栈。要先给maxTop赋初值，再给 stack 分配新的存储空间，设置 top=-1 为空栈。2）Push(Titem)：进栈操作。如果栈满则进行分配新的存储空间或者就不可以进栈 ；若不为满，则可已进栈，并且top继续指向上一个指针，把 item 插入 stacktop指针当中。3）Pop()：出栈，删除并返回栈顶元素。在此，要考虑到栈是否为空，若栈

5、空，则给出提示 EMPTY STACK!CANNOT POP! ；否则，就否则就执行删除 top 指针往下移，并且返回 top的上一个指针 stacktop+14）Peek()：返回栈顶元素 。也要考虑到是否是空栈，若空则无元素返回，会给出提示EMPTY STACK,CANT GET ITS ELEMENT!空栈，无元素! ；若不空，则就返回栈顶元素 stacktop 。5）EmptyStack()：判断是否为空栈 。返回 top=-1 ，说明是空栈。6）Stack()：释放并清空栈的存储空间 。要用到 delete ，释放 stack 。7） Clear()：清除栈中全部元素。令top=-1

6、 ，说明栈内元素已全部清空，为空栈 。2、函数 InfixToPostfix（中缀转后缀）、Calculator（后缀表达式求值）在核心算法中再详 详细介绍。3、main函数：先对相关参数进行定义，设置answer并对其进行while循环。在该循环中设定对象Stack R，并调用InfixToPostfix( R,mid, post) 进行中缀转后缀 ，之后再运用Calculator(str)并输出后缀表达式的值。一直进行while循环。（二）类与类的层次结构本程序中使用了一个抽象模板类Stack和两个函数InfixToPostfix（中缀转后缀）、Calculator（后缀表达式求值）及一个

7、主函数main，另外还有两个调用函数Single1（判断负号是否是单目运算符），Single2（双目运算符中的负数运算）。在函数InfixToPostfix（中缀转后缀）中运用抽象模板类Stack的一个特化类对象Stack& R，并且调用了函数Single1（判断负号是否是单目运算符）和 Priority(操作符的优先级的比较)。在函数Calculator（后缀表达式求值）中运用抽象模板类Stack的一个特化类对象Stacks，并且调用了函数 Single2（双目运算符中的负数运算）。c）模板类Stack的成员函数的实现程序代码template Stack:Stack( ) /初始化栈maxT

8、op=50; /给maxTop赋初值50stack=(T*)malloc(maxTop*sizeof(T); /给 stack 分配新的存储空间top=-1; /空栈template void Stack:Push(T item) /入栈if(top=maxTop-1) /如果栈满int m=sizeof(T);stack=(T*)realloc(stack,2*m*maxTop); /存储空间分配maxTop=2*maxTop;top+; /top继续指向上一个指针stacktop=item;template T Stack:Pop() /退栈,并返回栈顶元素if(top=-1) /是空栈，

9、coutEMPTY STACK!CANNOT POP!;top-; / 否则就执行删除 top 指针往下移return stacktop+1;template T Stack:Peek() /取栈顶元素if(top=-1) /是空栈，coutEMPTY STACK,CANT GET ITS ELEMENT!空栈，无元素!;return stacktop; / 否则就返回栈顶元素template bool Stack:EmptyStack()/判断是否为空return top=-1;（三）算法分析：核心算法InfixToPostfix（中缀转后缀）和Calculator（后缀表达式求值）的算法时

10、间复杂度和空间复杂度均为O（n），其中n 代表输入的中缀表达式中包含的字符数。四、核心算法代码代码：void main()char mid50; /中缀char post50; /后缀char answer;while(answer)coutanswer;if(answer=Y|answer=y)cout请输入一个表达（以#结束）:mid;Stack R;InfixToPostfix(R,mid,post);cout对应的后缀表达式：ENDL;coutcout求值得到运算结果：ENDLENDL;coutENDL;elsecout按任意键结束.;exit(1);（二）核心算法本程序中用的是类St

11、ack，还有两个主要核心算法程序函数InfixToPostfix（中缀转后缀）、Calculator（后缀表达式求值）。1、函数InfixToPostfix（中缀转后缀）：1）算法思想：实现转换的关键是确定操作符的优先级转换算法自左向右，逐项扫描作为输入的中缀表达式，对不同类型的项作相应的处理，产生输出项序列，得到后缀表达式。初始时，先在栈的底部压入结束符。设x是扫描输入中缀表达式时，得到的当前项，根据x的类型，算法对x作以下处理：（1） 若x#，则输出栈中剩余运算符，算法终止。（2） 若x是操作数，则将x直接输出并加到输出项序列的尾部。（3） 若x)，则从栈中不断弹出运算符，直至遇到左括号(

12、为止。令左括号出栈，当前项x（即右括号）既不进栈，也不输出。（4） 若x是运算符，则将x的优先级与栈顶的运算符作比较，若当前项x的优先级小于等于栈顶运算符的优先级，则从栈中弹出栈顶运算符，加到输出项序列的尾部。重复执行这一操作，直到x的优先级大于栈顶运算符的优先级时，才令x进栈，并结束这一操作。2）中缀转后缀的程序：首先要编写一个操作符的优先级比较的函数，为函数InfixToPostfix(Stack& R,char * mid, char * post)中缀转后缀 的操作符是否进栈或弹出输出起关键作用。int Priority(char op) /操作符的优先级，用于实现操作符的进出栈，输出

13、操作符。函数InfixToPostfix（）中被调用。switch(op)case +:case -:return 1;case *:case /:return 2;default: return 0;void InfixToPostfix(Stack& R,char * mid, char * post) /中缀转后缀int i=0; /指示中缀表达式串mid的下标int index=0; /指示后缀表达式串post的下标R.Push(#);while(midi)if(midi= ) / 是空格 ，跳过继续i+;continue;else if( midi=() /遇 ( 进栈R.Push(

14、midi);i+;else if( midi=) ) /遇 )while(R.Peek()!=() /依次弹出 ( 上面的元素postindex=R.Pop(); /并赋给 postpost+index= ;index+;R.Pop(); /弹出左括号i+;else if ( midi=+|midi=*|midi=/ |(midi=- & !Single1(mid,i) while( Priority(midi) =0 & midi=9 | midi=. )postindex+=midi;i+;postindex+= ;/每个数字用空格作分隔符while(R.Peek()!=#) /输出栈中剩

15、余操作符postindex=R.Pop();post+index= ;index+;postindex=0; /结束 0表示空字符2、函数Calculator（后缀表达式求值）1）算法思想：从左往右顺序扫描后缀表达式，遇到操作数就进栈，遇到操作符就从栈中弹出两个操作数，执行该操作符规定的运算，并将结果进栈。如此下去，直到遇到结束符#结束，弹出栈顶元素即为最终结果。其中，双目操作符是在计算从栈中弹出的两个操作数时，先出栈的放在操作符的右边，后出栈的放在左边。在本程序中，不仅包括简单的 + - * / 运算外，还有考虑到负号的单目运算即操作数的浮点运算，涉及函数 Single1（判断负号是否是单目

16、运算符）和 Single2（双目运算符中的负数运算）。2）后缀表达式求值的程序：double Calculator(char * str)/表达式求值，其中 str 表示后缀表达式字符串Stacks;double x,y;int i=0;int flag;/默认为正，-1为负double n;while(stri)flag=1;if(stri= ) /跳过空格i+;continue;switch(stri) /根据操作符做相应的运算case +:x=s.Pop()+s.Pop();i+;break;case -:if(Single2(str,i)!=true)x=s.Pop()-s.Pop()

17、;x=-x;i+;elsegoto deal;break;case *:x=s.Pop()*s.Pop();i+;break;case /:x=s.Pop(); /此时，x为分母if(fabs(x)1e-5) /分母为0 ，则做出错处理cout=0 & stri=0 & stri=9)y=y+(stri+-0)/n;n*=10;x+=y; /再把x=x+ys.Push(x*flag);if(s.EmptyStack()coutERROR!Empty stack!;x=s.Pop(); /非空则把最后的值赋值给xif(s.EmptyStack()return x; / 返回x即表达式的值else

18、 coutERROR!Wrong expression!;程序调试与体会课程设计总结运用栈的基本操作顺利的解决表达式求值及转换问题，主要利用栈的先进后出结构，执行出栈进栈操作并在出栈时进行配对并输出配对情况，而整个过程不需要不需要移动元素使程序在空间复杂度上降到最小，采用指针的移动大大加快了程序的执行效率。并且对输入进行了改进，以防止用户随意输入时出现的各种意想不到的错误。系统整体上比较完美，无论是输入、输出，还是整个系统的界面，都非常美观、简洁、大方通过这段时间的课程设计，本人对计算机的应用、数据结构的作用以及C+语言的使用都有了更深的了解。在理论学习和上机实践的各个环节中，通过自主学习，我收获了不少。当然也遇到不少问题，也正是因为这些问题引发的思考给我带来了收获。从当初不喜欢上机写程序到现在能主动写程序，从当初拿着程序不知从何下手道现在知道如何分析问题，如何用专业知识解决实际问题的转变。我发现无论是专业知识还是动手能力，自己都有很大程度的提高。在实际上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力。所以相信通过此次课程设计实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。