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

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

《施磊磊的数据结构课程设计及报告2 表达式求值问题.docx》由会员分享，可在线阅读，更多相关《施磊磊的数据结构课程设计及报告2 表达式求值问题.docx（12页珍藏版）》请在冰点文库上搜索。

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

课程设计

题目名称表达式求值问题

课程名称数据结构课程设计

学生姓名施磊磊

学号0813022057

班级计082

指导教师管致锦

数据结构课程设计及报告表达式求值

一、问题描述

实验题目为表达式求值。

要求接受用户输入一个中缀表达式（运算符为加、减、乘、除），然后通过借助于顺序栈实现将其转换为后缀表达式并将其打印，最后求出其值。

设计主函数，使用户可以重复输入中缀表达式，求得表达式的后缀表达式和表达式的值。

二、数据结构算法设计

（一）堆栈ADT

ADTStack{

数据:

0个或多个元素的线性序列（a0,a1,...,an-1）,其最大允许长度为MaxStackSize。

运算：

Create（）:

建立一个空栈。

Destroy（）:

撤销一个栈。

IsEmpty（）:

若空栈，则返回true；否则返回false。

IsFull（）:

若栈满，则返回true；否则返回false。

Top（）:

在x中返回栈顶元素。

若操作成功，则返回true；否则返回false。

Push（）:

在栈顶插入元素x（入栈）。

若操作成功，则返回true；否则返回false。

Pop（）:

从栈中删除栈顶元素（出栈）。

若操作成功，则返回true；否则返回false。

Clear（）:

清除堆栈中全部元素。

}

（二）顺序栈类

在此题目中，借助了c++的模板抽象类来定义栈抽象数据类型，程序如下：

顺序堆栈类：

include

template

classStack

{

private:

T*stack;//指向数组的指针

inttop;//栈顶指针

intmaxTop;//最大栈顶指针

public:

Stack（）;//构建一个构造函数；初始化栈

voidPush（Titem）;//进栈

TPop（）;//出栈，删除栈顶元素

TPeek（）;//返回栈顶元素

boolEmptyStack（）;//判断是否为空栈

~Stack（）{delete[]stack;};//释放并清空栈的存储空间

voidClear（）{top=-1;}//清除栈中全部元素

三、算法原理

（一）头文件名

在本程序中，运用的头文件有一些是在平时经常用到的，也有一些是少见甚至是很陌生的。

它们为函数中的一些语句提供了帮助并发生着作用。

（二）描述算法及算法原理

1、在classStack中

1）Stack（）：

构建一个构造函数；用于初始化栈，构建一个空栈。

要先给maxTop赋初值，再给stack分配新的存储空间，设置top=-1为空栈。

2）Push（Titem）：

进栈操作。

如果栈满则进行分配新的存储空间或者就不可以进栈；若不为满，则可已进栈，并且top继续指向上一个指针，把item插入stack[top]指针当中。

3）Pop（）：

出栈，删除并返回栈顶元素。

在此，要考虑到栈是否为空，若栈空，则给出提示"EMPTYSTACK!

CANNOTPOP!

"；否则，就否则就执行删除top指针往下移，并且返回top的上一个指针stack[top+1]

4）Peek（）：

返回栈顶元素。

也要考虑到是否是空栈，若空则无元素返回，会给出提示"EMPTYSTACK,CAN'TGETITSELEMENT!

[空栈，无元素!

]"；若不空，则就返回栈顶元素stack[top]。

5）EmptyStack（）：

判断是否为空栈。

返回top==-1，说明是空栈。

6）~Stack（）：

释放并清空栈的存储空间。

要用到delete，释放stack。

7）Clear（）：

清除栈中全部元素。

令top=-1，说明栈内元素已全部清空，为空栈。

2、函数InfixToPostfix（中缀转后缀）、Calculator（后缀表达式求值）在核心算法中再详详细介绍。

3、main函数：

先对相关参数进行定义，设置answer并对其进行while循环。

在该循环中设定对象StackR，并调用InfixToPostfix（R,mid,post）进行中缀转后缀，之后再运用Calculator（str）并输出后缀表达式的值。

一直进行while循环。

（二）类与类的层次结构

本程序中使用了一个抽象模板类Stack和两个函数InfixToPostfix（中缀转后缀）、Calculator（后缀表达式求值）及一个主函数main，另外还有两个调用函数Single1（判断负号是否是单目运算符），Single2（双目运算符中的负数运算）。

在函数InfixToPostfix（中缀转后缀）中运用抽象模板类Stack的一个特化类对象Stack&R，并且调用了函数Single1（判断负号是否是单目运算符）和Priority（操作符的优先级的比较）。

在函数Calculator（后缀表达式求值）中运用抽象模板类Stack的一个特化类对象Stacks，并且调用了函数Single2（双目运算符中的负数运算）。

c）模板类Stack的成员函数的实现程序代码

template

Stack:

:

Stack（）//初始化栈

{

maxTop=50;//给maxTop赋初值50

stack=（T*）malloc（maxTop*sizeof（T））;//给stack分配新的存储空间

top=-1;//空栈

}

template

voidStack:

:

Push（Titem）//入栈

{

if（top==maxTop-1）//如果栈满

{

intm=sizeof（T）;

stack=（T*）realloc（stack,2*m*maxTop）;//存储空间分配

maxTop=2*maxTop;

}

top++;//top继续指向上一个指针

stack[top]=item;

}

template

TStack:

:

Pop（）//退栈,并返回栈顶元素

{

if（top==-1）//是空栈，

{

cout<<"EMPTYSTACK!

CANNOTPOP!

";

}

top--;//否则就执行删除top指针往下移

returnstack[top+1];

}

template

TStack:

:

Peek（）//取栈顶元素

{

if（top==-1）//是空栈，

{

cout<<"EMPTYSTACK,CAN'TGETITSELEMENT!

[空栈，无元素!

]";

}

returnstack[top];//否则就返回栈顶元素

}

template

boolStack:

:

EmptyStack（）//判断是否为空

{

returntop==-1;

}

（三）算法分析：

核心算法InfixToPostfix（中缀转后缀）和Calculator（后缀表达式求值）的算法时间复杂度和空间复杂度均为O（n），其中n代表输入的中缀表达式中包含的字符数。

四、核心算法代码

代码：

voidmain（）

{

charmid[50];//中缀

charpost[50];//后缀

charanswer;

while（answer）

{

cout<<"是否要输入另一个表达式？

【Y/N】\n";

cin>>answer;

if（answer=='Y'||answer=='y'）

{

cout<<"请输入一个表达（以#结束）:

"<

cin>>mid;

StackR;

InfixToPostfix（R,mid,post）;

cout<<"对应的后缀表达式：

"<

cout<

cout<<"求值得到运算结果：

"<

cout<<

}

else

{

cout<<"按任意键结束...";

exit

（1）;

}

}

}

（二）核心算法

本程序中用的是类Stack，还有两个主要核心算法程序函数InfixToPostfix（中缀转后缀）、Calculator（后缀表达式求值）。

1、函数InfixToPostfix（中缀转后缀）：

1）算法思想：

实现转换的关键是确定操作符的优先级转换算法自左向右，逐项扫描作为输入的中缀表达式，对不同类型的项作相应的处理，产生输出项序列，得到后缀表达式。

初始时，先在栈的底部压入结束符‘＃’。

设x是扫描输入中缀表达式时，得到的当前项，根据x的类型，算法对x作以下处理：

（1）若x＝‘#’，则输出栈中剩余运算符，算法终止。

（2）若x是操作数，则将x直接输出并加到输出项序列的尾部。

（3）若x＝‘）’，则从栈中不断弹出运算符，直至遇到左括号‘（’为止。

令左括号出栈，当前项x（即右括号）既不进栈，也不输出。

（4）若x是运算符，则将x的优先级与栈顶的运算符作比较，若当前项x的优先级

小于等于栈顶运算符的优先级，则从栈中弹出栈顶运算符，加到输出项序列的

尾部。

重复执行这一操作，直到x的优先级大于栈顶运算符的优先级时，才令

x进栈，并结束这一操作。

2）中缀转后缀的程序：

首先要编写一个操作符的优先级比较的函数，为函数InfixToPostfix（Stack&R,char*mid,char*post）中缀转后缀的操作符是否进栈或弹出输出起关键作用。

intPriority（charop）//操作符的优先级，用于实现操作符的进出栈，输出操作符。

函数InfixToPostfix（）中被调用。

{

switch（op）

{

case'+':

case'-':

return1;

case'*':

case'/':

return2;

default:

return0;

}

}

voidInfixToPostfix（Stack&R,char*mid,char*post）//中缀转后缀

{

inti=0;//指示中缀表达式串mid的下标

intindex=0;//指示后缀表达式串post的下标

R.Push（'#'）;

while（mid[i]）

{

if（mid[i]==''）//是空格，跳过继续

{

i++;

continue;

}

elseif（mid[i]=='（'）//遇'（'进栈

{

R.Push（mid[i]）;

i++;

}

elseif（mid[i]=='）'）//遇'）'

{

while（R.Peek（）!

='（'）//依次弹出'（'上面的元素

{

post[index]=R.Pop（）;//并赋给post

post[++index]='';

index++;

}

R.Pop（）;//弹出左括号

i++;

}

elseif（mid[i]=='+'||mid[i]=='*'||mid[i]=='/'||（mid[i]=='-'&&!

Single1（mid,i）））{

while（Priority（mid[i]）<=Priority（R.Peek（）））

//刚弹出的栈顶操作符优先级高时输出

{

post[index]=R.Pop（）;

post[++index]='';

index++;

}

R.Push（mid[i]）;//栈外操作符则进栈

i++;

}

else

{

while（（mid[i]=='-'&&Single1（mid,i））||mid[i]>='0'&&mid[i]<='9'||mid[i]=='.'）

{

post[index++]=mid[i];

i++;

}

post[index++]='';//每个数字用空格作分隔符

}

}

while（R.Peek（）!

='#'）//输出栈中剩余操作符

{

post[index]=R.Pop（）;

post[++index]='';

index++;

}

post[index]='\0';//结束'\0'表示空字符ＮＵＬＬ

2、函数Calculator（后缀表达式求值）

1）算法思想：

从左往右顺序扫描后缀表达式，遇到操作数就进栈，遇到操作符就从栈中弹出两个操作数，执行该操作符规定的运算，并将结果进栈。

如此下去，直到遇到结束符‘#’结束，弹出栈顶元素即为最终结果。

其中，双目操作符是在计算从栈中弹出的两个操作数时，先出栈的放在操作符的右边，后出栈的放在左边。

在本程序中，不仅包括简单的+-*/运算外，还有考虑到负号的单目运算即操作数的浮点运算，涉及函数Single1（判断负号是否是单目运算符）和Single2（双目运算符中的负数运算）。

2）后缀表达式求值的程序：

doubleCalculator（char*str）//表达式求值，其中str表示后缀表达式字符串

{

Stacks;

doublex,y;

inti=0;

intflag;//默认为正，-1为负

doublen;

while（str[i]）

{

flag=1;

if（str[i]==''）//跳过空格

{

i++;

continue;

}

switch（str[i]）//根据操作符做相应的运算

{

case'+':

x=s.Pop（）+s.Pop（）;

i++;

break;

case'-':

if（Single2（str,i）!

=true）

{

x=s.Pop（）-s.Pop（）;

x=-x;

i++;

}

else

gotodeal;

break;

case'*':

x=s.Pop（）*s.Pop（）;

i++;

break;

case'/':

x=s.Pop（）;//此时，x为分母

if（fabs（x）<1e-5）//分母为0，则做出错处理

{

cout<<"ERROR!

Dividedbyzero~!

";

}

else

x=s.Pop（）/x;

i++;

break;

default:

deal:

x=0;

if（Single2（str,i）==true）

{

flag=-1;

i++;

}

while（str[i]>='0'&&str[i]<='9'）//该部分是用于求浮点的整数部分的。

if（str[i]=='.'）//浮点运算

{

i++;

y=0;

n=10;

while（str[i]>='0'&&str[i]<='9'）

{

y=y+（str[i++]-'0'）/n;

n*=10;

}

x+=y;//再把x=x+y

}

}

s.Push（x*flag）;

}

if（s.EmptyStack（））

{

cout<<"ERROR!

Emptystack!

";

}

x=s.Pop（）;//非空则把最后的值赋值给x

if（s.EmptyStack（））

returnx;//返回x即表达式的值

else{

cout<<"ERROR!

Wrongexpression!

";

}

}

程序调试与体会

课程设计总结

运用栈的基本操作顺利的解决表达式求值及转换问题，主要利用栈的先进后出结构，执行出栈进栈操作并在出栈时进行配对并输出配对情况，而整个过程不需要不需要移动元素使程序在空间复杂度上降到最小，采用指针的移动大大加快了程序的执行效率。

并且对输入进行了改进，以防止用户随意输入时出现的各种意想不到的错误。

系统整体上比较完美，无论是输入、输出，还是整个系统的界面，都非常美观、简洁、大方

通过这段时间的课程设计，本人对计算机的应用、数据结构的作用以及C++语言的使用都有了更深的了解。

在理论学习和上机实践的各个环节中，通过自主学习，我收获了不少。

当然也遇到不少问题，也正是因为这些问题引发的思考给我带来了收获。

从当初不喜欢上机写程序到现在能主动写程序，从当初拿着程序不知从何下手道现在知道如何分析问题，如何用专业知识解决实际问题的转变。

我发现无论是专业知识还是动手能力，自己都有很大程度的提高。

在实际上机操作过程中，不仅是让我们了解数据结构的理论知识，更重要的是培养解决实际问题的能力。

所以相信通过此次课程设计实习可以提高我们分析设计能力和编程能力，为后续课程的学习及实践打下良好的基础。