算术表达式求值Word格式.doc
《算术表达式求值Word格式.doc》由会员分享，可在线阅读，更多相关《算术表达式求值Word格式.doc（31页珍藏版）》请在冰点文库上搜索。
D={|ai|ai∈elemset,i=1,2,…,n，n≥0}
数据关系：
R1={<
ai-1，ai
>
|ai-1，ai∈D,i=2，…，n}
基本操作：
InitStack（）
操作结果：
构造一个空栈。
GetTop（S，&
e）
初始条件：
栈S已存在且非空。
用e返回S的栈顶元素。
Push（&
S，e）
栈S已存在。
插入元素e为新的栈顶元素。
Pop（&
S,&
删除S的栈顶元素，并且用e返回其值。
}ADTStack
2）系统中子程序及功能要求：
Precede（charc1,charc2）:
比较两个字符的优先级，并返回比较结果。
Operate（SElemTypea,charop,SElemTypeb）:
函数进行四则运算，并返回运算结果。
judge（charop）:
判断是否为运算符。
EvaluateExpression（）：
进行四则混合运算，并返回运算结果。
（2）本次程序设计中一共有三个模块，一个是由主函数构成的模块，一个是由各个子功能函数构成的栈模块,第三个是由运算等函数构成的运算模块。
（3）主模块可以对子模块中的函数进行调用，但子模块不能对主模块中的内容进行调用；
子模块中的函数可相互调用。
具体函数调用关系如下：
main
调用EvaluateExpression（）
EvaluateExpression（）
调用Precede、Operate、judge、InitStack（）、
GetTop、Push、Pop。
三、详细设计
（1）程序流程图：
（2）元素类型、结点类型和指针类型
typedef
int
Status;
SElemType;
//元素类型
typedefstruct
{
SElemType
*base;
*top;
int
stacksize;
}SqStack;
//结点类型和指针类型
（3）栈的基本操作定义如下：
StatusInitStack（SqStack*S）;
//构造一个空栈S
StatusGetTop（SqStackS）
//若栈不空，则返回栈顶元素，否则返回ERROR
StatusPush（SqStack*S,SElemTypee）;
//插入e为新的栈顶元素
StatusPop（SqStack*S,SElemType*e）;
//若栈不空，则删除S的栈顶元素，用e返回其值，返回OK，否则返回ERROR
（4）系统中子程序的基本操作定义：
CharPrecede（charc1,charc2）;
//进行运算符的优先级比较，并返回比较结果。
SElemTypeOperate（SElemTypea,charop,SElemTypeb）;
//进行两个整数数的四则运算，并返回运算结果。
Statusjudge（charop）
//判断是否为运算符。
SElemTypeEvaluateExpression（）
//进行四则混合运算，并返回运算结果。
（5）部分基本操作的源程序如下：
StatusPush（SqStack*S,SElemTypee）
*（S->
top）++=e;
returnOK;
//插入元素e为新的栈顶元素
}
StatusPop（SqStack*S,SElemType*e）
if（S->
top==S->
base）
returnERROR;
//若栈为空，返回ERROR
*e=*（--（S->
top））;
//栈不为空，删除S的栈顶元素，用e返回其值，并返回OK
charPrecede（chara,charb）
{//根据课本P53,表3-1算符间优先关系编写程序实现算符间的优先级比较
SElemTyper;
switch（a）
case'
+'
:
-'
//’+’,’-’运算符优先级相同，故放在一起进行比较
if（b=='
*'
||b=='
/'
（'
）r='
<
'
;
elser='
break;
//’*’,’/’运算符优先级相同，故放在一起进行比较
）r='
#'
）
{
printf（"
\nLogicexpressionerror！
Thereisnoright
bracket！
"
）;
return（‘0’）;
//逻辑错误，只有左括号，缺少右括号
else{
）'
='
\nMatchingerrorsinbrackets!
"
//括号匹配错误
\nLogicexpressionerror!
Thereisnoleft
bracket!
//逻辑错误，只有右括号，缺少左括号
else
return（r）;
SElemTypeOperate（SElemTypea,charop,SElemTypeb）
{
//进行算数运算op为运算符
switch（op）
return（a+b）;
return（a-b）;
return（a*b）;
if（b!
=0）return（a/b）;
else
\n0cannotdoDivisor"
}
SqStackOPTR,OPND;
a,b,e,sum,theta,x;
charc;
//声明各个变量
sum=0;
//初始化
InitStack（&
OPTR）;
//创建运算符栈
OPTR,（'
0'
））;
//’#’所对的整型量进运算符栈
OPND）;
//创建操作数栈
c=getchar（）;
while（c!
||GetTop（OPTR）!
=（'
））
if（!
judge（c））
while（c>
&
c<
9'
sum=（sum*10+（c-'
OPND,sum）;
//不是运算符进栈
switch（Precede（（GetTop（OPTR）+'
）,c））
//栈顶元素优先级低
OPTR,（c-'
//托括号并接受下一个字符
OPTR,&
x）;
//栈顶元素优先级高，退栈并将运算结果进栈
theta）;
OPND,&
b）;
a）;
e=Operate（a,（theta+'
）,b）;
OPND,e）;
OPND,0）;
c='
//逻辑错误，0进栈，并结束运算
return（GetTop（OPND））;
}
四、调试分析
（1）在调试过程中遇到的两大问题：
1）如何进行超过一位的数的存储
原因分析：
按照预想的想法，对表达式进行实际操作时发现，当输入超过一位的数时，在程序的运行过程中，只进行了数的最低位的运算：
例如1+15#，由于系统将15进行两个字符处理后仍按两个字符进行进栈存储，使得实际运行结果为6，显然是错误的
解决方案：
对操作数的进栈存储程序进行优化，使其能将多位数视为单个字
符进行进栈存储
具体程序由原来的if（!
judge（c））
优化如下：
当然，在声明变量时已经对sum进行了初始化：
sum=0。
2）如何进行数的转换
最初对站内元素类型的定义为char，但进行运算时发现其运算
或则是运算的结果均不能超过128，这是由char类型本身的性
决定的
将栈内元素的类型定义为int，无论是运算符，还是数字字符，在进栈之前都进行（-‘0’）操作，对于已经整型化的数字字符在进行其后的运算或进栈时不用在进行数的转换，但是由于个人程序的编制要求，运算符在出栈时仍需要进行相关的操作（+‘0’），即将运算符重新字符化
（2）实验总结：
经过本次课程设计，我深刻地感受到数据结构的重要性，《数据结构》是计算机专业很重要的一门课程，也是必须要熟练掌握的课程。
本次课程设计，我选择的项目是算术表达式的求值,它的实现主要是栈的应用，所以，通过这次的实习，特别加深了我对栈这一数据类型的理解，在实际应用中也比以前更加得心应手。
另外，在本次的程序设计中，我还切身的体会到不同的类型的数据的实际意义，一个程序可能会因为元素类型定义不当而永远得不到预期得结果。
在本次课程设计当中，在做完需求分析和概要设计后，我又进行了详细设计，经过一番分析之后，我首先对自己需要的模块进行了详细的编写，在确保各个功能模块的可行性以及正确性后，进行了与主函数、函数与函数之间的连接，调试后又进行了数据测试，并对结果进行分析，并做了多次改进和调试。
在调试的过程中，我深刻的认识到，对于计算机专业的学生来说，应更好的掌握应用软件的分析方法和调试方法，应该能够熟练运用高级语言的程序调试器DEBUG调试程序。
经过这次课程设计，我真的学到了很多东西，一方面巩固和加深了我对数据结构这门课程的理解，在实际应用方面也较以前有了很大的进步。
在设计的过程难免会遇到很多问题，此时千万不要气馁，解决问题的方法可以有很多，可以通过网络、书籍等方法进行需求信息的查找，寻求他人帮助自然也是一个好办法，但我个人觉得更多的应该是自己独立思考，才能达到提升自己分析问题、解决问题的能力作用。
此次课程设计将我们所学的理论知识和实际运用进行了一次很好的连接，有利于加强我们用理论知识来分析实际问题的能力，进而加强了我们对知识认识的实践度，巩固了我们的理论知识，深化了对知识的认识，并为走向社会打下一个良好的基础。
当然在这次课程设计中除了程序本身的问题外，我也发现了很多别的问题，发现自己的数据结构基础还不是很扎实，还有很多需要改进和努力的地方，在今后的学习中，我一定会努力地去巩固我的基础知识，并在实践中加强应用。
在这次课程设计中我遇到不少问题和麻烦，在老师们和同学们的帮助和提示下，才能够如此顺利地完成了设计，在次对老师们表示真诚的感谢！
五、用户使用说明
（1）进入程序运行界面后，出现欢迎语并显示执行命令项
（2）用户按程序提示进行命令项的选择
（3）按提示要求输入待运算的表达式（必须输入合法的，不含变量并且以#结束的表达式）
（4）系统输出运算结果，并重复
（1）～（3）的操作，需要退出时，可在
（2）中进行选择
六、测试结果
（1）输入：
8#
输出:
Thevalueofexpression：
8
运行结果截图为
（2）输入：
2-2-2-3#
输出：
Thevalueofexpression：
-5
运行结果截图为
（3）输入：
4+26/12-2*7#
-8
（4）输入：
18-3*7-15/6#
（5）输入：
2*（6+2*（3+6*（6+6）））#
312
七、附录
源代码
#include<
stdio.h>
stdlib.h>
#define
STACK_INIT_SIZE100
/*栈的存储空间初始分配量*/
MAX
100
/*字符存储空间分配量*/
TURE
1
ERROR0
OK
FALSE0
OVERFLOW
-2
/*元素类型*/
intStatus;
typedefstruct{
SElemType*base;
/*在构造之前和销毁之后，base的值为NULL*/
SElemType*top;
/*栈顶指针*/
intstacksize;
/*当前已分配的存储空间，以元素为单位*/
/*结点类型和指针类型*/
StatusInitStack（SqStack*S）
/*构造一个空栈S*/
S->
base=（SElemType*）malloc（STACK_INIT_SIZE*sizeof（SElemType））;
（S->
base））exit（OVERFLOW）;
/*存储空间分配失败*/
top=S->
base;
stacksize=STACK_INIT_SIZE;
if（S.top>
S.base）
return（*（S.top-1））;
/*栈不为空，返回栈顶元素*/
/*栈为空，返回ERROR*/
StatusPush（SqStack*S,SElemTypee）
/*插入元素e*/
/*插入成功，返回OK*/
StatusPop（SqStack*S,SElemType*e）
/*删除栈顶元素，并用e返回*/
/*栈不为空，删除栈顶元素，返回OK*/
/*判断是否为运算符*/
returnTURE;
/*是运算符，返回TURE*/
default:
returnFALSE;
/*不是运算符，返回ERROR*/
/*对两个整型数进行算术运算
op为运算符*/
/*若为’+’,返回进行加法运算的运算结果*/
/*若为’-’,返回进行减法运算的运算结果*/
/*若为’*’,返回进行乘法运算的运算结果*/
=0）return（a/b）;
/*若为’/’,且除数不为0返回进行除法运算的运算结果*/
else
/*除数为0，提示错误*/
exit（0）;
/*比较运算符的优先级*/
/*’+’,’-’运算符的优先级相同，故放在一起进行比较*/
）
r='
/*’*’,’/’运算符的优先级相同，故放在一起进行比较*/
Thereisnorightbracket！
/*逻辑错误，只有左括号，缺少右括号*/
return（'
/*括号不匹配*/
Thereisnoleftbracket!
/*逻辑错误，只有右括号，缺少左括号*/
/*运算结束标志*/
/*返回比较结果*/
/*算术表达式求值的算符优先级运算*/
升级会员 