数据结构算术表达式求值实验报告.docx
《数据结构算术表达式求值实验报告.docx》由会员分享，可在线阅读，更多相关《数据结构算术表达式求值实验报告.docx（21页珍藏版）》请在冰点文库上搜索。
数据结构算术表达式求值实验报告
软件技术基础实验报告
实验名称：
表达式计算器
系别：
通信工程
年级：
班级：
学生学号：
学生姓名：
《数据结构》课程设计报告
题目简易计算表达式的演示
【题目要求】
要求：
实现基本表达式计算的功能
输入：
数学表达式，表达式由整数和“+”、“-”、“×”、“/”、“（”、“）”组成
输出：
表达式的值
基本操作：
键入表达式，开始计算，计算过程和结果记录在文档中
难点：
括号的处理、乘除的优先级高于加减
1．前言
在计算机中，算术表达式由常量、变量、运算符和括号组成。
由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。
因而在程序设计时，借助栈实现。
算法输入：
一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。
为简化，规定操作数只能为正整数，操作符为+、-*、/、=，用#表示结束。
算法输出：
表达式运算结果。
算法要点：
设置运算符栈和运算数栈辅助分析算符优先关系。
在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。
2．概要设计
2.1数据结构设计
任何一个表达式都是由操作符，运算符和界限符组成的。
我们分别用顺序栈来寄存表达式的操作数和运算符。
栈是限定于紧仅在表尾进行插入或删除操作的线性表。
顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。
2.2算法设计
为了实现算符优先算法。
可以使用两个工作栈。
一个称为OPTR，用以寄存运算符，另一个称做OPND，用以寄存操作数或运算结果。
1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素；
2.依次读入表达式，若是操作符即进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为”#”）。
2.3ADT描述
ADTStack{
数据对象：
D={
|
∈ElemSet,i=1,2,…，n,n≧0}
数据对象：
R1={<
>|
i=2,…，n}
约定
端为栈顶，
端为栈底。
基本操作：
InitStack（&S）
操作结果：
构造一个空栈S。
GetTop（S）
初始条件：
栈S已存在。
操作结果：
用P返回S的栈顶元素。
Push（&S，ch）
初始条件：
栈S已存在。
操作结果：
插入元素ch为新的栈顶元素。
Pop（&S）
初始条件：
栈S已存在。
操作结果：
删除S的栈顶元素。
In（ch）
操作结果：
判断字符是否是运算符，运算符即返回1。
Precede（c1,c2）
初始条件：
c1,c2为运算符。
操作结果：
判断运算符优先权，返回优先权高的。
Operate（a,op,b）
初始条件：
a,b为整数，op为运算符。
操作结果：
a与b进行运算，op为运算符，返回其值。
num（n）
操作结果：
返回操作数的长度。
EvalExpr（）
初始条件：
输入表达式合法。
操作结果：
返回表达式的最终结果。
}ADTStack
2.4功能模块分析
1.栈的基本功能。
InitStack（Stack*s）和InitStack2（Stack2*s）分别构造运算符栈与构造操作数栈，
Push（Stack*s,charch）运算符栈插入ch为新的栈顶元素，
Push2（Stack2*s,intch）操作数栈插入ch为新的栈顶元素，
Pop（Stack*s）删除运算符栈s的栈顶元素，用p返回其值，
Pop2（Stack2*s）删除操作数栈s的栈顶元素，用p返回其值，
GetTop（Stacks）用p返回运算符栈s的栈顶元素，
GetTop2（Stack2s）用p返回操作数栈s的栈顶元素。
2.其它功能分析。
（1）In（charch）判断字符是否是运算符功能，运算符即返回1，该功能只需简单的一条语句即可实现，return（ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='（'||ch=='）'||ch=='#'）。
（2）Precede（charc1,charc2）判断运算符优先权功能，该函数判断运算符c1,c2的优先权，具体优先关系参照表1。
（3）Operate（inta,charop,intb）操作数用对应的运算符进行运算功能。
运算结果直接返回。
（4）num（intn）求操作数的长度功能，需要用itoa函数把int型转换成字符串型，strlen函数可求字符长度。
（5）EvalExpr（）主要操作函数运算功能。
分析详细见“3.详细设计…3.2”。
3．详细设计
3.1数据存储结构设计
因为表达式是由操作符，运算符和界限符组成的。
如果只用一个char类型栈，不能满足2位以上的整数，所以还需要定义一个int类型的栈用来寄存操作数。
/*定义字符类型栈*/
structstacklifei1//数字栈的定义
{
double*base;
double*top;
}s1;/
structstacklifei2//运算符栈的定义
{
char*base;
char*top;
}s2;
3.2计算功能的实现
voidjisuan（）//该函数对数字栈的前两个栈顶
//元素与符号栈的栈顶元素完成一次运算操作
{
doublea,b;
b=*（s1.top-1）;
s1.top--;
if（s1.top==s1.base）
{
error=1;
return;
}
a=*（s1.top-1）;
switch（*（s2.top-1））
{
case'+':
a=a+b;break;
case'-':
a=a-b;break;
case'*':
a=a*b;break;
case'/':
if（b==0）{error=2;s2.top=s2.base;return;}//除数不为0
elsea=a/b;break;
default:
error=1;
}
fprintf（file,"%lf%c%lf=%lf\n",*（s1.top-1）,*（s2.top-1）,b,a）;
*（s1.top-1）=a;//将运算结果入栈
s2.top--;
return;
}
3.3函数表达式求值功能的实现
voidqiuzhi（char*cr）
该函数完成对表达式的处理
{
inti=0,k,h,flag,fuhao=0;
doublesum,j;
s1.base=s1.top=shuzhi;
s2.base=s2.top=fuha;
*（s2.top）='#';
s2.top++;
while（s2.top!
=s2.base）
{
sum=0;
flag=0;
k=10;j=1;h=1;
while（cr[i]>='0'&&cr[i]<='9'||cr[i]=='.'）
//若当前的字符是数字，就将char型的数据转换为double型
{
if（cr[i]=='.'）
{
if（cr[i-1]<'0'||cr[i-1]>'9'||i==0||cr[i+1]<'0'||cr[i+1]>'9'）
{error=1;break;}
else
{k=1;h=10;}
}
else
{
flag=1;j=j*h;
sum=sum*k+（cr[i]-48）/j;
}
i++;
}
3.4对函数表达式每个字符的操作
switch（cr[i]）
{
case'-':
if（cr[i-1]=='（'||i==0）{fuhao=1;i++;break;}
//判断是不是负号，若不是则进行与加号相同的操作
//当'-'出现在表达式第一位或是'（'后第一位,则应将其判为负号
case'+':
//加、减号的优先级只比'（'和'='高，若栈顶元素为这两者之一
//就将其入栈，否则执行运算操作
if（*（s2.top-1）=='（'||*（s2.top-1）=='#'）
{
*（s2.top）=cr[i];
s2.top++;
i++;
}
elsejisuan（）;break;
case'*':
case'/':
//乘、除号的优先级只比'*'、'/'和'^'低，若栈顶元素为这三者之一
//就执行运算操作，否则将其入栈
if（*（s2.top-1）=='*'||*（s2.top-1）=='/'）jisuan（）;
else
{
*（s2.top）=cr[i];
s2.top++;
i++;
}break;
case'（':
*（s2.top）=cr[i];s2.top++;i++;break;
//未入栈时'（'的优先级最高，所以它一定要入栈
//但一入栈其优先级就应降为最低
case'）':
//注意：
由于'（）'运算优先级最高故我直接进行运算，
//直到栈顶元素为'（'后将'（'出栈，故符号栈中一定没有'）'，
//这也是我进行以上优先级判断的前提
if（*（s2.top-1）=='（'）
{
s2.top--;
i++;
}
elsejisuan（）;break;
case'=':
//表达式结束，若符号栈栈顶元素不为'#'，进行运算
//否则退栈，结束
if（*（s2.top-1）=='#'）
{
s2.top--;
}
elsejisuan（）;break;
default:
i++;//清除空格及未定义符号
}
3.5主菜单页面的实现
voidmain（）
{
charcr[60];
charc='a';
file=fopen（outfile,"w+"）;
//使用提示
printf（"*******************************************************************************\n"）;
printf（"*********************************李斐计算器************************************\n"）;
printf（"四则简易计算器\n\n"）;
printf（"输入表达式例如2+4=\n\n"）;
printf（"最后按#键则会退出保存\n\n"）;
printf（"谢谢使用\n\n"）;
printf（"------------------------------------------------------------------------------\n"）;
printf（"******************************************************************************\n"）;
//循环输入表达式，按'#'键退出
while（c!
='#'）
{
error=0;
printf（"输入表达式:
\n"）;
gets（cr）;
fprintf（file,"表达式：
%s\n",cr）;
qiuzhi（cr）;
printf（"任意键继续，按#键退出:
\n"）;
c=getch（）;
}
fclose（file）;
}
【附加一】算符间的优先关系如下：
+
-
*
/
（
）
=
#
+
>
<
<
<
<
>
>
>
-
>
>
<
<
<
>
>
>
*
>
>
>
>
<
>
>
>
/
>
>
>
>
<
>
>
>
（
<
<
<
<
<
=
>
>
）
>
>
>
>
=
>
>
>
=
<
<
<
<
<
<
=
<
#
<
<
<
<
<
<
>
=
4．软件测试
1.运行成功后界面。
2.输入正确的表达式后。
3.更改表达式，带括号输出
5．心得体会
这次课程设计让我再一次加了解大一学到的C和这个学期学到的数据结构。
课设题目要求不仅要求对课本知识有较深刻的了解，同时要求程序设计者有较强的思维和动手能力和更加了解编程思想和编程技巧。
这次课程设计让我有一个深刻的体会，那就是细节决定成败，编程最需要的是严谨，如何的严谨都不过分，往往检查了半天发现错误发生在某个括号，分号，引号，或者数据类型上。
就一点小小的错误也耽误了我几十分钟，所以说细节很重要。
程序设计时，也不要怕遇到错误，在实际操作过程中犯的一些错误还会有意外的收获，感觉课程设计很有意思。
在具体操作中这学期所学的数据结构的理论知识得到巩固，达到课程设计的基本目的，也发现自己的不足之出，在以后的上机中应更加注意，同时体会到C语言具有的语句简洁，使用灵活，执行效率高等特点。
发现上机的重要作用，特别算术表达式有了深刻的理解。
最后，感谢老师在这门数据结构课程的悉心指导，祝老师和助教身体健康，万事如意！
【参考文献】
1.《数据结构（C语言版）》严蔚敏清华大学出版社
2.《C程序设计》谭浩强清华大学出版社
【附录】
程序源代码：
#include
#include
#include
#include
structstacklifei1//数字栈的定义
{
double*base;
double*top;
}s1;
structstacklifei2//运算符栈的定义
{
char*base;
char*top;
}s2;
doubleshuzhi[40];//数字栈
charfuha[40];//符号栈
interror;//出错标识符
FILE*file;
charoutfile[30]="\lifeijisuanqi.txt";
voidjisuan（）//该函数对数字栈的前两个栈顶
//元素与符号栈的栈顶元素完成一次运算操作
{
doublea,b;
b=*（s1.top-1）;//取数字栈栈顶元素
s1.top--;
if（s1.top==s1.base）
{
error=1;
return;
}//若栈空，出错
a=*（s1.top-1）;//取数字栈栈顶元素
switch（*（s2.top-1））
{
case'+':
a=a+b;break;
case'-':
a=a-b;break;
case'*':
a=a*b;break;
case'/':
if（b==0）{error=2;s2.top=s2.base;return;}//除数不为0
elsea=a/b;break;
default:
error=1;
}
fprintf（file,"%lf%c%lf=%lf\n",*（s1.top-1）,*（s2.top-1）,b,a）;
*（s1.top-1）=a;//将运算结果入栈
s2.top--;//运算符退栈
return;
}
voidqiuzhi（char*cr）
//qiuzhi（）；该函数完成对表达式的处理
{
inti=0,k,h,flag,fuhao=0;
doublesum,j;
s1.base=s1.top=shuzhi;
s2.base=s2.top=fuha;//数字栈与符号栈初始化
*（s2.top）='#';//将'#'入栈，方便循环
s2.top++;
while（s2.top!
=s2.base）
{
sum=0;
flag=0;
k=10;j=1;h=1;
while（cr[i]>='0'&&cr[i]<='9'||cr[i]=='.'）
//若当前的字符是数字，就将char型的数据转换为double型
{
if（cr[i]=='.'）
{
if（cr[i-1]<'0'||cr[i-1]>'9'||i==0||cr[i+1]<'0'||cr[i+1]>'9'）
//判断小数点是否出错
{error=1;break;}
else
{k=1;h=10;}
}
else
{
flag=1;j=j*h;
sum=sum*k+（cr[i]-48）/j;
}
i++;
}
if（flag）//flag不为0表明有数据需要入栈
{
if（fuhao）{sum=-sum;fuhao=0;}
//fuhao是个标志记号，值不为0表明刚才转换的值为负数
*（s1.top）=sum;
s1.top++;
}
else
{
switch（cr[i]）
{
case'-':
if（cr[i-1]=='（'||i==0）{fuhao=1;i++;break;}
//判断是不是负号，若不是则进行与加号相同的操作
//当'-'出现在表达式第一位或是'（'后第一位,则应将其判为负号
case'+':
//加、减号的优先级只比'（'和'='高，若栈顶元素为这两者之一
//就将其入栈，否则执行运算操作
if（*（s2.top-1）=='（'||*（s2.top-1）=='#'）
{
*（s2.top）=cr[i];
s2.top++;
i++;
}
elsejisuan（）;break;
case'*':
case'/':
//乘、除号的优先级只比'*'、'/'和'^'低，若栈顶元素为这三者之一
//就执行运算操作，否则将其入栈
if（*（s2.top-1）=='*'||*（s2.top-1）=='/'）jisuan（）;
else
{
*（s2.top）=cr[i];
s2.top++;
i++;
}break;
case'（':
*（s2.top）=cr[i];s2.top++;i++;break;
//未入栈时'（'的优先级最高，所以它一定要入栈
//但一入栈其优先级就应降为最低
case'）':
//注意：
由于'（）'运算优先级最高故我直接进行运算，
//直到栈顶元素为'（'后将'（'出栈，故符号栈中一定没有'）'，
//这也是我进行以上优先级判断的前提
if（*（s2.top-1）=='（'）
{
s2.top--;
i++;
}
elsejisuan（）;break;
case'=':
//表达式结束，若符号栈栈顶元素不为'#'，进行运算
//否则退栈，结束
if（*（s2.top-1）=='#'）
{
s2.top--;
}
elsejisuan（）;break;
default:
i++;//清除空格及未定义符号
}
}
if（error）break;
}
if（error||s1.top-1!
=s1.base）
//若运行出错或是数字栈中的元素不是一个，就进行出错提醒
{
if（error==2）
{
printf（"除数不能为0！
\n"）;
fprintf（file,"%s\n","除数不能为0！
"）;
}
else
{
printf（"表达式错误！
\n"）;
fprintf（file,"%s\n","表达式错误！
"）;
}
}
else
//结果输出，输出小数点后六位，
{
fprintf（file,"结束\n"）;
printf（"%.6lf\n",*（s1.base））;
fprintf（file,"%.6lf\n",*（s1.base））;
}
return;
}
voidmain（）
{
charcr[60];
charc='a';
file=fopen（outfile,"w+"）;
//使用提示
printf（"*******************************************************************************\n"）;
printf（"*********************************李斐计算器************************************\n"）;
printf（"四则简易计算器\n\n"）;
printf（"输入表达式例如2+4=\n\n"）;
printf（"最后按#键则会退出保存\n\n"）;
printf（"谢谢使用\n\n"）;
printf（"------------------------------------------------------------------------------\n"）;
printf（"******************************************************************************\n"）;
//循环输入表达式，按'#'键退出
while（c!
='#'）
{
error=0;
printf（"输入表达式:
\n"）;
升级会员 