表达式求值.docx
《表达式求值.docx》由会员分享，可在线阅读，更多相关《表达式求值.docx（13页珍藏版）》请在冰点文库上搜索。
表达式求值
表达式求值问题
目录
1、数据结构课程设计任务书１
1.1、题目１
1.2、要求１
2、总体设计１
2.1、功能模块设计１
2.2、所有功能模块的流程图１
3、详细设计１
3.1、程序中所采用的数据结构及存储结构的说明１
3.2、算法的设计思想２
3.3、稀疏矩阵各种运算的性质变换２
4、调试与测试：
２
4.1、调试方法与步骤：
２
4.2、测试结果的分析与讨论：
３
4.3、测试过程中遇到的主要问题及采取的解决措施：
３
5、时间复杂度的分析：
４
6、源程序清单和执行结果４
7、C程序设计总结８
8、致谢８
9、参考文献８
1、数据结构课程设计任务书
1.1、题目
表达式求值问题
1.2、要求
（1）以字符序列的形式从终端输入语法正确的、不含变量的表达式；
（2）利用给定的运算符优先关系；
（3）实现对算术四则运算表达式的求值；
（4）演示在求值过程中运算符栈、操作数栈、输入字符和主要操作的变化过程。
2、总体设计
2.1、功能模块设计
根据课程设计题目的功能要求，各个功能模块的组成框图如下：
2.2、所有功能模块的流程图
3、详细设计
模块功能说明：
如函数功能、入口及出口参数说明，函数调用关系描述等；
3.1、程序中所采用的数据结构及存储结构的说明
以顺序存储结构来表示三元组表，则可得到稀疏矩阵的一种压缩存储方式——三元组顺序表。
//-----------稀疏矩阵的三元组顺序存储表示-------------
#defineMAXSIZE100/*假设非零元个数的最大值为20*/
typedefstruct
{
inti,j;/*该非零元的行下标和列下标*/
intv;
}Triple;
typedefstruct
{
Tripledata[MAXSIZE+1];/*非零元三元组表,data[0]未用*/
intmu,nu,tu;/*矩阵的行数,列数和非零元个数*/
}TSMastrix;
在此，data域中表示非零元得三元组是以行序为主序顺序排列的，这样有利于进行某些矩阵运算。
3.2、算法的设计思想
a）相加运算
对于两个稀疏矩阵相加，即行与行，列与列相加
b）相乘运算
若设Q=M*N其中M是m1*n1矩阵，N是m2*n2矩阵，只有当n1=m2时才可以相乘。
乘积矩阵Q中元素
Q（i，j）=∑M（i，k）*N（k，j）1≤i≤m1，1≤j≤n2
在算法中，不论M（i，k）和N（k，j）的值是否为零，都要进行一次乘法运算，而实际上，这两者有一个值为零时，其乘积也为零。
因此，在对稀疏矩阵进行运算时，应免去这种无效操作，只需在M.data和N.data中找到相应的各对元素（即M.data中的j值和N.data中的i值相等的各对元素）相乘即可。
c）转置运算
对于一个m*n的矩阵M，它的转置矩阵T是一个n*m的矩阵，且T（i，j）=M（j，i），
1≤i≤n，1≤j≤m。
完成一个稀疏矩阵的转置分为三步：
（1）将矩阵的行列值相互交换；
（2）将每个三元组中的i和j相互调换；
（3）重排三元组之间的次序便可实现矩阵的转置；
3.3、稀疏矩阵各种运算的性质变换
a）加法运算
两个稀疏矩阵的加和矩阵仍然是稀疏矩阵
b）乘法运算
两个稀疏矩阵的乘积矩阵不是稀疏矩阵
c）转置运算
一个稀疏矩阵的转置矩阵仍然是稀疏矩阵
4、调试与测试：
4.1、调试方法与步骤：
4.2、测试结果的分析与讨论：
（测试要写出测试用例及每个用例结果的的截图）
4.3、测试过程中遇到的主要问题及采取的解决措施：
（略）
5、时间复杂度的分析：
a）加法运算
由于两矩阵行列相等，故时间复杂度为O（行*列）
b）乘法运算
设M是m1*n1矩阵，N是m2*n2矩阵，则时间复杂度是O（m1*n1*n2）
c）转置运算
时间复杂度和原矩阵的列数及非零元的个数的乘积成正比，即O（mu*nu）
6、源程序清单和执行结果
#include
#defineStackSize100
#defineQueueSize100
/*队列的相关操作*/
TypedefcharDataType;
Typedefstruct{
chardata[100];
intfront,rear;
}Sequeue;//定义队列类型
voidInitQueue（SeqQueue*Q）//初始化队列
{
Q->front=0;
Q->rear=0;
}
intQueueEmpty（SeqQueueQ）//判空队列
{
returnQ.rear==Q.front;
}
voidEnQueue（SeqQueue*Q,DataTypex）//入队列
{
If（（Q->rear+1）%QueueSize==Q->front）
printf（“Queueoverflow”）;
else
{Q->data[Q->rear]=x;
Q->rear=（Q->rear+1）%QueueSize;
}
}
DataTypeDeQueue（SeqQueue*Q）
{
charx;
if（QueueEmpty（*Q））return0;
else{
x=Q->data[Q->front];
Q->front=（Q->front+1）%QueueSize;
Returnx;
}
}
/*栈的相关操作*/
Typedefstruct{
DataTypedata[100];
inttop;
}SeqStack;//栈类型的定义
voidInitStack（SeqStack*S）//初始化栈
{
S->top=-1;
}
voidPush（SeqStack*S,DataTypex）//入栈（进栈）
{
if（s->top==stockSize-1）
printf（“stackoverflow”）;
else{
S->top=S->top+1;
S->data[S->top]=x;
}
}
DataTypePop（SeqStack*S）//退栈（出栈）
{
if（S->top==-1）
{printf（“stackunderflow”）
Return0;
}
else
returnS->data[S->top--]；
}
DataTypeGetTop（SeqStackS）//取栈顶元素
{
if（S.top==-1）
{printf（“stackempty”）;
return0;
}
else
returnS.data[S.top];
}
//求运算符优先级函数
intPriority（DataTypeop）
{
Switch（op）{
case‘（’：
case‘#’：
return0；
case‘-’：
case‘+’：
return1；
case‘*’：
case‘/’：
return2；
}
return-1;
}
voidCTPostExp（SeqQueue*Q）
{
SeqStackS;//运算符栈
charc,t;
InitStack（&S）;//初始化栈
Push（&S,‘#’）；//压入栈底元素‘#’
do//扫描中缀表达式
{c=getchar（）;
Switch（c）
{
case‘’：
bresk；//去除空格符
case‘0’：
case‘1’：
case‘2’：
case‘3’：
case‘4’：
case‘5’：
case‘6’：
case‘7’：
case‘8’：
case‘9’：
EnQueue（Q,c）;break;
case‘（’：
Push（&S,c）;break;
case‘）’：
case‘#’：
do{
t=Pop（&S;）
if（t!
=‘（’&&t!
=‘#’）EnQueue（Q,t）;
}while（t!
=‘（’&&S.top!
=-1）;break;
case‘+’：
case‘-’：
case‘*’：
case‘/’：
while（Priority（c）<=Priority（GetTop（S）））
{
t=Pop（&S）;EnQueue（Q.t）;
}
Push（&S.c）;break;
}//EndSwitch
}while（c!
=‘#’）;//以‘#’号结束表达式扫描
}
//后缀表达式的计算
DataTypeCpostExp（SeqQueueQ）
{SeqStackS;
charch;
intx,,yl
InitStack（&S）;
while（!
QueueEmpty（Q））{
ch=DeQueue（&Q）;
if（ch>=‘0’&&ch=>‘9’）
Push（&S,ch）;
else{
y=Pop（&S）-‘0’;
x=Pop（&S）-‘0’;
switch（ch）{
case‘+’：
Push（&S,（char）（x+y+‘0’））;break;
case‘-’：
Push（&S,（char）（x-y+‘0’））;break;
case‘*’：
Push（&S,（char）（x*y+‘0’））;break;
case‘/’：
Push（&S,（char）（x/y+‘0’））;break;
}
}
}
returnGetIop（S）;
}
voidmain（）
{SeqQueueQ;//定义队列，存放后缀表达式
InitQueue（&Q）;//初始化队列
CTPostExp（&Q）;//调用转换函数将中缀表达式转换成后缀表达式
printf（“表达式的运算结果是：
%c\n”,CPostExp（0））;//输出计算结果
pringt（“表达式的后缀表达式为：
”）；
while（!
QueueEmpty（Q））//输出后缀表达式
printf（“%2c”,DeQueue（&Q））;
printf（“\n”）;
}
7、C程序设计总结
本程序在刚开始调试时有许多错误，但在我的努力及同学的帮助下都被一一克服，现在在操作本程序时可根据提示进行相关操作，能正确输出结果。
在刚开始的几次调试中曾经出现过不能运行、不能产生十以内随机数字、不能随机出现加减、不会正确输出结果、不能进行循环练习等等问题。
经过我的努力及同学的帮助，这些问题得到克服，并且使程序的功能也得到了一定的完善。
现在它能对出错的题目发出报警声，并且给出正确答案。
最后还能分别输出对错的题数及所得分数。
在这次设计过程中，不仅复习课本上所学知识，还通过查资料、问同学学到了课本上没有的知识。
从而启发我，要想写好程序，在写好课本知识的同时还需要多读和专业有关的一些书籍，同时还需要多动脑子，尽量把所学的知识综合起来应用，力争写出完美的程序。
除此之外，我还得到了一些有用的教训：
写程序时必须要细心，不能输错一个字符标点，就连全角半角也得注意。
在修改时要有耐心，编译出错后必须逐个错误去改正，绝不能心急浮躁，否则修改之后还会有新的错误。
8、致谢
能够完成这次课程设计必须感谢C语言课程老师、^^同学（他帮我修改了几处重要错误，同时启发我完善了该程序的功能）。
9、参考文献
[1]郑莉、董渊、何江舟，C语言程序设计（第四版），清华大学计算机系列教材，
[2]苏仕华、魏韦巍、王敬生、刘燕君，数据结构课程设计（第二版），机械工业出版社
[3]
升级会员 