算术表达式求值问题课程设计报告.docx

算术表达式求值问题课程设计报告.docx

《算术表达式求值问题课程设计报告.docx》由会员分享，可在线阅读，更多相关《算术表达式求值问题课程设计报告.docx（23页珍藏版）》请在冰点文库上搜索。

算术表达式求值问题课程设计报告

合肥学院

算术表达式求值演示

一、问题分析和任务定义

实验题目：

算术表达式求值：

一个算术表达式是由操作数（operand），运算符（operator）和界限符（delimiter）组成的。

假设操作数是正整数，运算符只含加减乘除等四种运算符，界限符有左右括号和表达式起始，结束符“#”，如：

#（7+15）*（23-28/4）#。

引入表达式起始、结束符是为了方便。

编程利用“算符优先法”求算术表达式的值。

要求：

（1）从键盘读入一个合法的算术表达式，输出正确的结果。

（2）显示输入序列和栈的变化过程。

选作内容：

操作数类型扩充到实数。

问题分析：

在带括号的的算术表达式中，界限符包括左右括号以及表达式起始、结束符“#”。

假设运算符只有加、减、乘、除4种，则对一个简单的算术表达式的运算规则如下：

（1）从左至右运算表达式。

（2）先乘、除，后加、减。

（3）先括号内，后括号外。

要想能够实现这个问题，首先，你要从键盘中输入一个字符并判别该字符是运算符还是运算数。

如果是运算数就直接进运算数栈。

如果是运算符，则与运算符栈的栈顶元素进行优先级的比较（可以单独写一个优先级比较函数，将每个运算符与其他运算符之间的优先级一一比较出来，可以设置为“>”、“<”、“=”），如果比较后为“>”，则将运算数栈依次出栈两次，将该运算符和刚出栈的两个运算数进行计算（单独写一个函数，将“+”、“-”、“*”、“/”四种情况一一写出来），然后将计算的结果入运算数栈，将读入的运算符入运算符栈；如果比较后为“<”，则将该运算符入运算符栈；如果是“=”，同“>”，但要注意如果从运算符栈出栈的元素为“#”和“（”，则运算数栈无需出栈，并且运算符栈也无需入栈。

按照上面的步骤，一一读完所有的字符。

这样，运算数栈中最后剩下的元素就是该算术表达式的最终结果。

注意：

整个算法结束的条件是运算符栈为空。

（即表达式的起始、结束符相遇）

任务定义：

为统一算法的描述，将运算符和界限符统称为算符。

这样，算符集为+，-，*，/，（，），#}。

根据上述3条运算规则，两个前后相继出现的算符a1、a2间的优先关系可以归纳如下：

（1）若a1、a2同为“*”、“/”或同为“+”、“-”，则运算符a1的优先级大于a2。

（2）“*”、“/”的优先级大于“+”、“-”。

（3）由于“先括号内，后括号外”，若a1为“+”、“-”、“*”、“/”，a2为“（”；或者，a1为“（”，而a2为“+”、“-”、“*”、“/”，则a1的优先级小于a2。

（4）同理，若a1为“+”、“-”、“*”、“/”，a2为“）”；或者，a1为“）”，而a2为“+”、“-”、“*”、“/”，则a1的优先级小于a2。

（5）若a1,a2同为“（”，则a1的优先级小于a2；若a1,a2同为“）”，则a1的优先级大于a2。

（6）表达式的起始、结束符“#”的优先级小于其他所有合法出现的算符。

（7）若a1为“（”，a2为“）”或a1，a2同为“#”，则a1，a2的优先级相同。

表1：

算符a1和a2间的关系

测试用例：

输入的运算表达式为：

#9*（18+2）+10#

输出格式：

显示每一步操作，并且同时显示操作后的序列和栈的变化过程，最后显示正确的结果。

二、概要设计和数据结构的选择

1、数据结构的选择

因为一个算术表达式就是由运算符和运算数两部分构成的，表达式的求值过程就是对这两部分进行操作，并且由运算符的具体操作来控制运算数。

所以为了方便操作，首先可以分别设置一个运算符栈OPTR和一个运算数栈OPND，然后，依次读入表达式中的每个字符。

若是操作数则进运算数栈OPND，反之，则与栈OPTR的栈顶算符进行优先级比较，并作如下处理：

1、若栈顶算符的优先级大于读入的算符，则让该算符入算符栈OPTR；

2、若栈顶算符的优先级高于刚读入的算符，则将栈顶算符出栈，同时，将运算数栈OPND出栈两次，得到两个操作数x,y，对x,y用栈顶算符运算后，再将运算结果入运算数栈OPND；

3、若栈顶算符和读入算符的优先级相等，说明左右括号相遇，或者是表达式的起始、结束符相遇。

只需将OPTR退栈即可。

运算符栈和运算数栈的定义：

typedefstruct//创建运算符栈的类型

{chardata[maxlen];

inttop;

}stack1;

typedefstruct//创建运算数栈的类型

{intdata[maxlen];

inttop;

}stack2;

2、概要设计

程序中实现各个功能的函数有：

1、初始化运算符类型的栈：

voidinitstack1（stack1*s）；

2、初始化运算数类型的栈：

voidinitstack2（stack2*s）；

3、入运算符栈：

voidpushfu（stack1*s,charc）；

4、入运算数栈：

voidpushshu（stack2*L,intp）；

5、出运算符栈：

voidpopfu（stack1*s,char*p）;

6、出运算数栈：

voidpopshu（stack2*s,int*p）；

7、得到运算符栈的栈顶元素：

chargettop1（stack1*s）；

8、/得到运算数栈的栈顶元素：

intgettop2（stack2*s）；

9、输出运算符栈里的所有算符：

voidvisitoptr（stack1*c）；

10、输出运算数栈里的所有算数：

voidvisitopnd（stack2*c）；

11、判断字符c是不是运算符：

intjudge（charc）；

12、判断优先级：

charyouxianji（charch1,charch2）；

13、进行运算函数：

intopreate（inta,charfu,intb）；

主函数实现的流程图如下：

否

=

图1：

主函数的流程

三、详细设计和编码

1、初始化运算符类型的栈思想：

申请一个运算符栈类型的指针变量后，将它的top置为-1，即使它为空，然后返回该指针。

voidinitstack1（stack1*s）

{s=（stack1*）malloc（sizeof（stack1））;

s->top=-1;

}

2、初始化运算数类型的栈思想：

申请一个运算数栈类型的指针变量后，将它的top置为-1，即使它为空，然后返回该指针。

voidinitstack2（stack2*s）

{s=（stack2*）malloc（sizeof（stack2））;

s->top=-1;

}

3、入运算符栈思想：

如果要入的栈不满，就使它的top加1，然后将要插入的算符赋值给top指向的data域中。

voidpushfu（stack1*s,charc）

{if（s->top==maxlen-1）

{cout<<"栈已满，输入错误!

"<

else

{（s->top）++;

s->data[s->top]=c;

}}

4、入运算数栈思想：

如果要入的栈不满，就使它的top加1，然后将要插入的算符赋值给top指向的data域中。

voidpushshu（stack2*L,intp）

{if（L->top==maxlen-1）

{cout<<"栈已满，输入错误!

"<

else

{（L->top）++;

L->data[L->top]=p;}}

5、出运算符栈思想：

先将该栈的栈顶元素赋值给同类型的形参变量，然后使得top减1。

voidpopfu（stack1*s,char*p）

{*p=s->data[s->top];

（s->top）--;

}

6、出运算数栈思想：

先将该栈的栈顶元素赋值给同类型的形参变量，然后使得top减1。

voidpopshu（stack2*s,int*p）

{*p=s->data[s->top];

（s->top）--;}

7、得到运算符栈的栈顶元素

chargettop1（stack1*s）

{returns->data[s->top];}

8、得到运算数栈的栈顶元素

intgettop2（stack2*s）

{returns->data[s->top];}

9、输出运算符栈里的所有算符

voidvisitoptr（stack1*c）

{inti;

{for（i=0;i<=c->top;i++）

cout<data[i];}

cout<<"\t\t";}

10、输出运算数栈里的所有算数

voidvisitopnd（stack2*c）

{inti;

{for（i=0;i<=c->top;i++）

cout<data[i]<<",";}

cout<

11、判断字符c是不是运算符：

思想是如果该字符等于“+”，“-”，“*”，

“/”，“（”，“）”，“#”中的一个就是运算符，并返回确认1，如果不是，就返回0。

intjudge（charc）

{if（（c=='+'）||（c=='-'）||（c=='*'）||（c=='/'）||（c=='（'）||（c=='#'）||（c=='）'））

return1;

elsereturn0;}

12、判断优先级：

思想见上面任务定义部分。

charyouxianji（charch1,charch2）

{charch;

switch（ch1）//将ch1和ch2相比较

{case'+':

if（（ch2=='*'）||（ch2=='/'）||（ch2=='（'））ch='<';elsech='>';break;

case'-':

if（（ch2=='*'）||（ch2=='/'）||（ch2=='（'））ch='<';elsech='>';break;

case'*':

if（ch2=='（'）ch='<';elsech='>';break;

case'/':

if（ch2=='（'）ch='<';elsech='>';break;

case'（':

if（ch2=='）'）ch='=';elsech='<';break;

case'#':

if（ch2=='#'）ch='=';elsech='<';break;}

returnch;}

13、进行运算函数：

intopreate（inta,charfu,intb）

{ints;

switch（fu）

{case'+':

s=a+b;break;

case'-':

s=a-b;break;

case'*':

s=a*b;break;

case'/':

s=a/b;break;}

returns;}

四、上机调试

1、调试过程中的问题：

（1）、在调试过程中，发生了许多小细节上的问题，提醒了我在编程的时候要注意细节，比即使是一个括号的遗漏或者一个字符的误写都会造成大量的错误，浪费许多时间，总结的教训是要仔细。

（2）、第一次调试时，错误为出栈时不能得到栈顶的值，导致了后面的运算操作不正确，只是地址无算数，后检查发现，在出栈时，定义的函数形式为voidpopshu（stack2*s,intp）更改为voidpopshu（stack2*s,int*p）。

（3）、当编译无误时，开始运行程序，但却出现了内存不能read的错误，但是在进行栈的初始化时已经申请了内存空间，所以不是没有申请空间。

后来上网查阅资料知道也许时初始化栈时使用了无效的指针的错误，所以将初始化运算符栈的函数更改为：

stack1*initstack1（）

{stack1*s;

s=（stack1*）malloc（sizeof（stack1））;

s->top=-1;

return（s）;}

将初始化运算数栈的函数更改为：

stack2*initstack2（）{stack2*s;

s=（stack2*）malloc（sizeof（stack2））;

s->top=-1;

return（s）;}

这时程序才能正常的读写内存。

（4）、在测试程序时，发现如果输入了一个不是个位数的数时，程序的运行结果错误。

经检查发现在读入字符时，一个大于个位数的数是分开来从左向右一个一个的输入的，所以在主函数中读入数时要定义一个开关变量，来判别读入的数下一个字符是否还是一个数，如果是就将该数乘以10并赋值给总量后继续读入下个数；如果不是就将得到的总量直接放入运算数栈中并读入一个运算符。

2、算法性能分析

（1）.算法时间性能分析

对于算术符优先级比较算法，首先将每个待入栈的运算符判断，这样若有n个算术符，则要判断n次，而接下来又需对栈顶运算符比较，这样，又可分为两种情况，a.栈顶元素优先级高于待入栈运算符，b.栈顶元素优先级低于待入栈运算符，共需判断2n次，而在判断前以判断了n次，所以，这一种情况的比较次数就为2n^2次，像这样的情况共有5种，综合时间复杂度为T（n）=O（5*2*n^2）=O（10*n^2）

对于表达式格式判定算法，因比较复杂，外层为3种情况，而其中一种又有5种情况，这样若有n个字符，则总的判断次数为：

n*n*（3*n^2+n+n^3）,所以时间复杂度T（n）=O（n^5+3n^4+n^4）

（2）.空间性能分析

一个算术表达式输入时，存储在一维数组里，对于求表达式算法，一个表达式最少占有空间1（只有一个数子的情况），最多占有空间2n-1（n-1个位置全部有符号），平均一下，平均占空间是3n/2，所以该算法空间复杂度是:

S（n）=（3n/2）*4n-1,取f（n）=n*22n,limS（n）/f（n）=3/8。

所以空间复杂度为：

O（n*22n）。

对于表达式求值出入栈算法，若该表达式共有n个字符，而共有运算符栈和运算数栈，所以平均为n^2/4，这样，空间复杂度为：

O（n*n^2/4）。

五、测试结果与分析

（1）、输入#7+8#，结果显示如下所示：

图2：

算式#7+8#运行截屏

结果分析：

经过亲自将结果运算式计算一遍，证明程序运算正确。

控制算术表达式结束的条件就是“gettop2（OPTR）==’#’”。

（2）、输入：

#9*（18+2）/（12-2）#,结果显示如下所示：

图3：

算式#9*（18+2）/（12-2）#运行截屏

结果分析：

该表达式输入了十位数，使得程序的功能得到充分实现。

六、用户使用说明

1.打开“Debug”文件夹，运行“算术表达式求值问题.exe”。

2.用户输入想要求值的算术表达式并以“#”结束。

3.程序会自动显示每步操作并同时显示两个栈的变化过程，最终输出正确的结果。

4.用户选择“Y”或者“y”继续输入表达式求值；选择“N”或者“n”时，按“Enter”键就会直接退出。

七、参考文献

[1]王昆仑，数据结构与算法，北京：

中国铁道出版社，2007

[2]谭浩强，c程序设计，北京：

清华大学出版社，2005

[3]郑莉、董渊、张瑞丰，C++语言程序设计，北京：

清华大学出版社，2003

[4]严蔚敏，数据结构：

ｃ语言版，北京：

清华大学出版社，2002

[5]胡学钢，数据结构与算法设计指导，北京：

清华大学出版社，1999

[6]徐士良，Ｃ常用算法程序集，北京：

清华大学出版社，1995

[7]关治、陈景良，数值计算，北京：

清华大学出版社，1993

八、附录：

源程序

#include

#include

#definemaxlen100

usingnamespacestd;

intn=0;//定义一个全局变量n并赋值为0

typedefstruct//创建运算符栈的类型

{chardata[maxlen];

inttop;

}stack1;

typedefstruct//创建运算数栈的类型

{intdata[maxlen];

inttop;

}stack2;

intjudge（charc）//判断字符c是不是运算符

{if（（c=='+'）||（c=='-'）||（c=='*'）||（c=='/'）||（c=='（'）||（c=='#'）||（c=='）'））

return1;

elsereturn0;

}

stack1*initstack1（）//初始化运算符类型的栈

{stack1*s;

s=（stack1*）malloc（sizeof（stack1））;

s->top=-1;

return（s）;

}

stack2*initstack2（）//初始化运算数类型的栈

{stack2*s;

s=（stack2*）malloc（sizeof（stack2））;

s->top=-1;

return（s）;

}

voidpushfu（stack1*s,charc）//入运算符栈

{if（s->top==maxlen-1）

{cout<<"栈已满，输入错误!

"<

else

{（s->top）++;

s->data[s->top]=c;

}

}

voidpushshu（stack2*L,intp）//入运算数栈

{if（L->top==maxlen-1）

{cout<<"栈已满，输入错误!

"<

else

{（L->top）++;

L->data[L->top]=p;}

}

voidpopfu（stack1*s,char*p）//出运算符栈

{*p=s->data[s->top];

（s->top）--;

}

voidpopshu（stack2*s,int*p）//出运算数栈

{*p=s->data[s->top];

（s->top）--;

}

charyouxianji（charch1,charch2）//判断优先级

{charch;

switch（ch1）//将ch1和ch2相比较

{case'+':

if（（ch2=='*'）||（ch2=='/'）||（ch2=='（'））ch='<';elsech='>';break;

case'-':

if（（ch2=='*'）||（ch2=='/'）||（ch2=='（'））ch='<';elsech='>';break;

case'*':

if（ch2=='（'）ch='<';elsech='>';break;

case'/':

if（ch2=='（'）ch='<';elsech='>';break;

case'（':

if（ch2=='）'）ch='=';elsech='<';break;

case'#':

if（ch2=='#'）ch='=';elsech='<';break;

}

returnch;

}

chargettop1（stack1*s）//得到运算符栈的栈顶元素

{returns->data[s->top];

}

intgettop2（stack2*s）//得到运算数栈的栈顶元素

{returns->data[s->top];

}

intopreate（inta,charfu,intb）//进行运算函数

{ints;

switch（fu）

{case'+':

s=a+b;break;

case'-':

s=a-b;break;

case'*':

s=a*b;break;

case'/':

s=a/b;break;

}

returns;

}

voidvisitoptr（stack1*c）//输出运算符栈里的所有算符

{inti;

{for（i=0;i<=c->top;i++）

cout<data[i];}

cout<<"\t\t";

}

voidvisitopnd（stack2*c）//输出运算数栈里的所有算数

{inti;

{for（i=0;i<=c->top;i++）

cout<data[i]<<",";}

cout<

}

voidprintstep（）//输出步骤编号

{

n++;

cout<

}

voidmain（）

{

charc,t,x,jixu;

inti=0,sum=0;

intk=1,j=1;//设置了开关变量

inta,b;

stack1*OPTR;//定义运算符栈OPTR

stack2*OPND;//定义运算数栈OPND

OPTR=initstack1（）;//初始化运算符栈

pushfu（OPTR,'#'）;//#号压入栈OPTR

OPND=initstack2（）;//初始化运算数栈

for（;;）

{

cout<<"请输入算术表达式并以#号结束（形如3*（4+5）#）:

"<

cout<<"#";

cin>>c;

cout<<"*******************表达式求值演示*****************"<

cout<<"步骤"<<"\t\t";

cout<<"操作\t\t";

cout<<"运算符栈"<<"\t";

cout<<"运算数栈"<

printstep（）;//第一步是将#号入栈OPTR

cout<<"#号入运算符栈"<<"\t\t";

visitoptr（OPTR）;

cout<<"\t\t"<

while（c!

='#'||gettop1（OPTR）!

='#'）//当c是#或者运算符栈栈顶是#时结束操作，输出结果

{

if（judge（c）==0）//如果输入的字符是数字，就将其入运算数栈

{

sum=0;

while（judge（c）==0）

{

if（!

j）//如果开关变量j不为1时，说明输入的不是个位数

{

sum=c-'0';

}

else

sum=sum*10+（c-'0'）;

cin>>c;

}

pushshu（OPND,sum）;//将得到的数入运算数栈

printstep（）;//输出步骤，操作，以及运算符栈、运算数栈的变化

cout<<"输入"<

visitoptr（OPTR）;

visitopnd（OPND）;

j=1;

}

else

if（k）

{

switch（youxianji（gettop1（OPTR）,c））//如果得到的数据是运算符，就将它和运算符栈的栈顶元素比较优先级

{

case'<':

pushfu（OPTR,c）;//如果c的优先级小于栈顶运算符，就将c入运算符栈并继续输入

printstep（）;

cout<