软件技术基础小论文

《软件技术基础小论文》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、《数据结构》课程论文报告书题目：表达式求值系另0:学号：学生姓名：目录—1=4A2.概要设计2.1数据结构设计2.2算法设计2.3ADT描述2.4功能模块分析A3.详细设计3.1数据存储结构设计3.2主要算法流程图（或算法代码）A4.软件测试A5.总结1.前在计算机中，算术表达式山常量、变量、运算符和括号组成。山于不同的运算符具有不同的优先级，又耍考虑括号，因此，算术表达式的求值不对能严格地从左到右进行。因而在程序设计时，借助栈实现。算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化

2、，规定操作数只能为正整数，操作符为+、-*、/,用#表示结朿。算法输出：表达式运算结果。算法耍点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。2.概要设计2.1数据结构设计任何一个表达式都是山操作符，运算符和界限符组成的。我们分別用顺序栈來寄存衣达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一•纽连续的存储单元依次存放自栈底到栈顶的数据元索，同时附设指针top指示栈顶元素在顺序栈中的位置，base为

3、栈底指针，在顺序栈中，它始终指向栈底，即top二base可作为栈空的标记，每当插入新的栈顶元索时，指针top增1,删除栈顶元索时，指针top减1。2.2算法设计为了实现算符优先算法。可以使用两个工作栈。一个称为0PTR,用以寄存运算符，另一个称做0PND,用以寄存操作数或运算结果。1•首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素；2.依次读入表达式，若是操作符即进0PND栈，若是运算符则和0PTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即0PTR栈的栈顶元素和当前读入的字符均为

4、”#”)。2.3ADT描述ADTStack{数据对象：D={a-IEElemSet,i=l,2,•••,n,nMO}数据对象：R1二{<%,%_]>

5、勺_],勺w£),i=2,…，n}约定a”端为栈顶，曾端为栈底。基木操作：InitStack(&S)操作结果：构造一个空栈S。GetTop(S)初始条件：栈S己存在。操作结果：用P返回S的栈顶元素。Push(&S,ch)初始条件：栈S已存在。操作结果：插入元素ch为新的栈顶元素。Pop(&S)初始条件：栈S已存在。操作结果：删除S的栈顶元素。In(ch)操作结果：判断字

6、符是否是运算符，运算符即返冋1。Precede(cl,c2)初始条件:cl,c2为运算符。操作结果：判断运算符优先权，返回优先权窩的。Operate(a,op,b)初始条件：a,b为整数,op为运算符。操作结果：a与b进行运算，op为运算符，返冋其值。num(n)操作结杲：返回操作数的长度。EvalExpr()初始条件：输入表达式合法。操作结果：返回表达式的最终结果。}ADTStack2.4功能模块分析1.栈的棊本功能。InitStack(Stack*s)和InitStack2(Stack2*s)分别构造运算符栈与构

7、造操作数栈,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的栈顶元素。1.其它功能分析。(l)Tn(charch)判断字符是否是运算符功能,运算符即返回1,该功能只需简单的一条语句即

8、可实现return（ch二二'+'

9、

10、ch二二'-'

11、

12、ch二二'*'

13、

14、ch二二'/'

15、

16、ch二二'（'

17、

18、ch二二'）'

19、

20、ch二二'#'）。(2)Precede(charcl,charc2)判断运算符优先权功能,该函数判断运算符cl,c2的优先权，具休优先关系参照表1。(3)Operate(inta,charop,intb)操作数用对应的运算符进行运算功能。运算结果直接返冋。(4)nn)求操作数的长度功能，需要用itoa函数把int型转换成字符串型，strlen函数可求字符长度。(5)EvalExpr()主要操

21、作函数运算功能。分析详细见“3•详细设计…3.2”。2.1数据存储结构设计因为表达式是由操作符，运算符和界限符组成的。如果只用一个char类型栈，不能满足2位以上的整数，所以还需要定义一个int类型的栈川来寄存操作数。/*定义字符类型栈*/typedefstruct{intstacksize;char*base;char*top;}Stack;