《带括号算术表达式的计算》实验报告.docx
《《带括号算术表达式的计算》实验报告.docx》由会员分享，可在线阅读，更多相关《《带括号算术表达式的计算》实验报告.docx（25页珍藏版）》请在冰点文库上搜索。
《带括号算术表达式的计算》实验报告
四川大学
数据结构与算法分析实验报告
实验名称：
带括号的算术表达式求值
*****________***________
学院：
_______软件学院_______
专业：
_______软件工程_______
***________****________
学号：
_____*************____
班级：
________5班________
日期：
___2014年10月24日___
一、实验题目:
●带括号的算术表达式求值
二、实验目的和要求:
✓采用算符优先数算法,能正确求值表达式;
✓熟练掌握栈的应用;
✓熟练掌握计算机系统的基本操作方法,了解如何编辑、编译、链接和运行一个C程序;
✓上机调试程序,掌握查错、排错使程序能正确运行。
三、实验的环境:
✧硬件环境:
联想笔记本电脑
✧软件环境:
操作系统:
windows7旗舰版
编译软件:
VisualC++6.0
四、算法描述:
Ø
程序框图
Ø文字解释:
1.用户从键盘读入算术中缀表达式，以”=”结尾;
2.程序判断用户输入表达式是否正确;
3.若表达式正确，则用栈计算算术表达式;
4.打印输出计算过程和最终结果;
5.程序询问用户是否继续计算;
6.若继续，则执行第1步;若否定，则退出程序
7.若表达式错误，则打印错误信息，提示用户重新输入
8.返回第1步;
Ø函数及结构说明:
●结构体:
1）存储算数表达式的单链表:
structExpression{
charsign;
structExpression*next;
};
2）操作符和操作数栈:
typedefstruct{
char*top;
char*bottom;
intstack_size;
}Stack;
●构造函数:
1）栈相关操作函数:
初始化空栈intStackCreate（Stack*s）;
入栈操作intPUSH（Stack*s,charc）;
出栈操作intPOP（Stack*s,charc）;
获取栈顶元素charGetTop（Stack*s）;
2）计算相关操作函数:
利用栈计算算术表达式intCalculate（structExpression*exp）;
子式的值的计算intCount（charnum1,charsign,charnum2）;
判断字符是否为运算符intIsOpOrNum（charc）;
判断运算符优先级charJudgeLevel（charc1,charc2）;
判断表达式正确性intIsExpresiion（structExpression*exp）;
输出计算结果voidPrintResult（structExpression*exp,intresult）;
3）算术表达式输入函数:
键盘读入存于单链表structExpression*GetExp（）;
●
符号2
构造操作符优先级表
符号1
比较
●
+
-
*
/
（
）
=（#）
+
>
>
<
<
<
>
>
-
>
>
<
<
<
>
>
*
>
>
>
>
<
>
>
/
>
>
>
>
<
>
>
（
<
<
<
<
<
=
）
>
>
>
>
>
>
=（#）
<
<
<
<
<
=
五、源程序清单
Ø见附录
六、运行结果
Ø测试表
●本次测试采用用户从键盘输入算数表达式，共进行16组测试
序号
测试功能
测试内容
输入项
预期输出
实际输出
结果
1
基本计算操作
单括号运算
2*（3+4）+5*3=
29
29
通过
2
基本计算操作
多括号运算
3+（（4+3）*6）/3=
17
17
通过
3
基本计算操作
不能除整运算
6*（2+（3/2））=
21
18
有误差
4
基本计算操作
不能除整运算
（1+2+3）/4=
1.5
1
有误差
5
式子正误判断
括号不匹配
1+（1+3*2=
输出错误信息
输出错误信息
通过
6
式子正误判断
计算符多余
1++2*3+6=
输出错误信息
输出错误信息
通过
7
式子正误判断
含非计算符
x+y*z+w=
输出错误信息
输出错误信息
通过
8
式子正误判断
未输入”=”
1+2*3
7
7
通过
9
容错能力
除数为0
2+3/0=
输出除数为0
输出除数为0
通过
10
容错能力
自动去空格
1+2*（3+4）=
15
15
通过
11
容错能力
“=”输为”#”
2*（3+2）#
10
10
通过
12
拓展功能
多位正数计算
10*（2+13）=
150
输出错误信息
未通过
13
拓展功能
负数计算
4+3*（-4）+5=
-3
输出错误信息
未通过
15
拓展功能
小数计算
1+10*0.1/2=
6
输出错误信息
未通过
16
全体测试
最终测试
2*（4–（3+3））+3#
-1
-1
通过
Ø部分运行截图
●基本计算操作
不能整除运算（3）
多括号运算
（2）
●式子正误判断
●容错能力
●全体测试
七、实验运行情况分析
Ø优点:
●用户输入格式较为自由。
增添了一些能想到的容错系统，如用户未输入”=”，或是用户将”=”错输成”#”，或是用户在字符间输入空格，程序都会智能识别出正确的算数表达式，计算正确答案。
●防错报错系统较为完善。
多方面考虑输入方面的错误，如括号不匹配、计算符少输多输、输入非计算符等方面均考虑，并提示用户错误信息，便于用户检查输入状况。
●存储方式较为规范。
采用单链表存储用户输入的算术表达式，更加清晰简单,头结点存储表达式中符号的个数，方便在必要的时候统计对照最终结果的正确性。
Ø缺点:
●只能实现数字之间的四则运算，不能实现其他算数功能如平方，开方等。
●仅仅局限于个位数之间的运算，无法运算两位数或两位以上数字的运算。
●计算数字只能为0-9的整数，无法对负数或者小数进行计算。
●在除法中若遇到无法除尽的结果，只能保留其整数部分，造成最终结果跟预期结果存在误差
●由于控制台系统的限制，与用户交互性较差，界面太过简单单调。
Ø感受:
通过本次“带括号算数表达式的计算”实验，我不光复习了之前学习的单链表的相关知识并加以采用，而且还巩固了有关于栈的相关操作；在实现题目要求基本功能的基础上，还增加拓展了一些内容。
在为期两周的实验中，从刚开始的整理思路，到接下里的编写代码，到最后的填写实验报告，都是我自己一步步完成。
唯独可惜的是，由于知识掌握不够全面，导致只能实现最基本的功能，无法进行进一步的扩展和完善，致使用户输入一些运算式未得到预期的结构，这是比较遗憾的方面。
附录（源程序代码）
/*
*实验一：
带括号的算数表达式求值
*实现：
栈
*语言：
C
*作者：
马健
*/
#include
#include
#include
#defineSTACK_SIZE_FIRST100//栈的初始空间大小
#defineSTACK_SIZE_INCREASE20//栈的增加空间大小
/*---------------------------------算术表达式单链表----------------------------------*/
structExpression{
charsign;
structExpression*next;
};
/*---------------------------------操作符和操作数栈----------------------------------*/
typedefstruct{
char*top;
char*bottom;
intstack_size;//栈的空间大小
}Stack;
structExpression*GetExp（）;//键盘读入表达式存入单链表
/*---------------------------------栈相关的操作函数-----------------------------------*/
intStackCreate（Stack*s）;//初始化一个空栈函数
intPUSH（Stack*s,charc）;//入栈函数
intPOP（Stack*s,charc）;//出栈函数
charGetTop（Stack*s）;//取出栈顶元素
/*---------------------------------计算相关操作函数----------------------------------*/
intCalculate（structExpression*exp）;//带括号的算数表达式计算函数
intCount（charnum1,charsign,charnum2）;//两个数的计算
intIsOpOrNum（charc）;//判断一个字符是不是运算符
charJudgeLevel（charc1,charc2）;//判断两运算符优先级
voidPrintResult（structExpression*exp,intresult）;//打印最终结果
intIsExpresiion（structExpression*exp）;//判断是否为正确的算术表达式
voidmain（）
{
structExpression*head;
intResult=0;//定义最终计算结果
inttemp=0;//定义循环参数
charselect;
while（temp==0）
{
head=GetExp（）;//创建算术表达式单链表
if（IsExpresiion（head）==0||head==NULL）//算术表达式错误，重新输入
{
printf（"算术表达式错误，请认真检查并重新输入"）;
getch（）;
system（"cls"）;
}
else
{
Result=Calculate（head）;//计算算术表达式
PrintResult（head,Result）;//输出最终计算结果
printf（"是否继续计算?
是（y）否（n）\n"）;//是否继续
select=getch（）;
if（select=='n'||select=='N'）
temp=1;
else
system（"cls"）;
}
}
}
//读入算术表达式并存储于链表
structExpression*GetExp（）
{
printf（"\t带括号的算术表达式求值\n"）;
printf（"请输入需要计算的算数表达式:
（以'='结尾）\n"）;
charc;
intnumber=0;
structExpression*head=NULL,*p1,*p2,*first=NULL;//定义指针变量
head=（structExpression*）malloc（sizeof（structExpression））;
while（（c=getchar（））!
='\n'）
{
if（c!
=''）//若出现空格,自动删除
{
p1=（structExpression*）malloc（sizeof（structExpression））;
if（c=='='）
c='#';
p1->sign=c;
if（first==NULL）
first=p1;
else
p2->next=p1;
p2=p1;
number++;
}
}
if（p2->sign!
='#'）//若未输入'=',则自动补齐
{
p1=（structExpression*）malloc（sizeof（structExpression））;
p1->sign='#';
p2->next=p1;
p2=p1;
number++;
}
head->next=first;
head->sign=number+'0';//头结点存储表达式中字符个数
if（head->next!
=NULL）
p2->next=NULL;
returnhead;
}
//创建空栈
intStackCreate（Stack*s）
{
s->bottom=（char*）malloc（STACK_SIZE_FIRST*sizeof（char））;
if（s->bottom==NULL）
{
printf（"栈初始化失败!
\n"）;
exit（0）;
}
else
{
s->top=s->bottom;
s->stack_size=STACK_SIZE_FIRST;
}
return1;
}
//入栈
intPUSH（Stack*s,charc）
{
if（s->top-s->bottom>=STACK_SIZE_FIRST）
{
s->bottom=（char*）realloc（s->bottom,（STACK_SIZE_FIRST+STACK_SIZE_INCREASE）*sizeof（char））;
if（s->bottom==NULL）
{
printf（"增加栈空间失败!
\n"）;
exit（0）;
}
s->stack_size=s->stack_size+STACK_SIZE_INCREASE;
}
*（s->top）=c;//赋值需要入栈的元素
s->top++;//栈顶指针上移
return1;
}
//出栈
intPOP（Stack*s,charc）
{
if（s->top==s->bottom）
{
printf（"栈为空!
出栈失败!
\n"）;
exit（0）;
}
else
{
c=*（s->top）;
s->top--;
}
return1;
}
//获取栈顶元素
charGetTop（Stack*s）
{
charc;
if（s->top==s->bottom）
printf（"栈空，无法获取栈顶元素!
\n"）;
else
{
c=*（s->top-1）;
}
returnc;
}
//计算算术表达式
intCalculate（structExpression*exp）
{
exp=exp->next;//取表达式开始
charOpSign='';//存储出栈操作符
charNumSign1='',NumSign2='';//存储出栈数字符
charresult;//存储部分运算结果
chartemp='';//接受出栈操作数
Stacks_operator,s_number;
StackCreate（&s_operator）;//创建操作符栈
StackCreate（&s_number）;//创建数字栈
PUSH（&s_operator,'#'）;//先在操作栈底压入'#'
printf（"\n计算过程如下:
\n"）;
while（exp->sign!
='#'||GetTop（&s_operator）!
='#'）
{
//操作数存入操作数栈
if（IsOpOrNum（exp->sign）==0）
{
PUSH（&s_number,exp->sign）;
exp=exp->next;
}
//操作符存入操作符栈
elseif（IsOpOrNum（exp->sign）==1）
{
OpSign=GetTop（&s_operator）;//获取栈顶元素
switch（JudgeLevel（OpSign,exp->sign））//比较栈顶元素和运算符的优先级
{
case'<':
PUSH（&s_operator,exp->sign）;exp=exp->next;break;
case'=':
POP（&s_operator,OpSign）;exp=exp->next;break;
case'>':
POP（&s_operator,OpSign）;
NumSign1=GetTop（&s_number）;
POP（&s_number,temp）;
NumSign2=GetTop（&s_number）;
POP（&s_number,temp）;
result=Count（NumSign2,OpSign,NumSign1）;
PUSH（&s_number,result）;
break;
default:
break;
}
}
}
result=GetTop（&s_number）;//获取最终计算结果
returnresult-'0';
}
//判断两个运算符的优先级
charJudgeLevel（charc1,charc2）
{
switch（c1）
{
case'+':
switch（c2）{
case'*':
case'/':
case'（':
return'<';break;
default:
return'>';break;
}
break;
case'-':
switch（c2）{
case'*':
case'/':
case'（':
return'<';break;
default:
return'>';break;
}
break;
case'*':
switch（c2）{
case'（':
return'<';break;
default:
return'>';break;
}
break;
case'/':
switch（c2）{
case'（':
return'<';break;
default:
return'>';break;
}
break;
case'（':
switch（c2）{
case'）':
return'=';break;
default:
return'<';break;
}
break;
case'）':
switch（c2）{
case'+':
return'>';break;
default:
return'>';break;
}
break;
case'#':
switch（c2）{
case'#':
return'=';break;
default:
return'<';break;
}
break;
default:
return'<';break;
}
}
//计算一个符号的运算
intCount（charnum1,charsign,charnum2）
{
inta=0,b=0;
a=num1-'0';//取数字字符的值
b=num2-'0';
intresult=0;
switch（sign）
{
case'+':
result=a+b;break;
case'-':
result=a-b;break;
case'*':
result=a*b;break;
case'/':
result=a/b;break;
default:
break;
}
printf（"%d%c%d=%d\n",a,sign,b,result）;//输出计算过程
returnresult+'0';
}
//判断字符是运算符还是数字符
intIsOpOrNum（charc）
{
switch（c）
{
case'+':
case'-':
case'*':
case'/':
case'（':
case'）':
case'#':
return1;//操作符
break;
case'0':
case'1':
case'2':
case'3':
case'4':
case'5':
case'6':
case'7':
case'8':
case'9':
return0;//操作数
break;
default:
return-1;//其他
break;
}
}
//输出最终结果
voidPrintResult（structExpression*exp,intresult）
{
printf（"\n最终计算结果为:
\n"）;
exp=exp->next;
while（exp!
=NULL）
{
if（exp->sign=='#'）
exp->sign='=';
printf（"%c
升级会员 