没有合适的资源?快使用搜索试试~ 我知道了~
数据结构算术表达式求值实验报告.docx
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
5星 · 超过95%的资源 1 下载量 130 浏览量
2023-02-20
17:33:34
上传
评论
收藏 340KB DOCX 举报
温馨提示
试读
20页
。。。
资源推荐
资源详情
资源评论
北京理工大学珠海学院
《数据结构》课程设计报告
题目:____________
算术表达式求值
_________________
所在学院:
专业班级:
学生姓名:
指导教师:
2010 年 05 月 26 日
目录
1.前
言································································································· 1
2.概要设计································································································· 1
2.1 数据结构设计 ··············································································································· 1
2.2 算法设计···················································································································· 1
2.3 ADT 描述··················································································································· 2
2.4 功能模块分析·············································································································· 2
3.详细设计································································································· 3
3.1 数据存储结构设计 ········································································································· 3
3.2 主要算法流程图(或算法伪代码) ····················································································· 3
4.软件测试································································································· 6
5.心得体会································································································· 8
参考文献 ····································································································· 8
附 录 ·········································································································· 8
北京理工大学珠海学院计算机科学技术学院
1.前 言
在计算机中,算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级,
又要考虑括号,因此,算术表达式的求值不可能严格地从左到右进行。因而在程序设计时,借助栈实现。
算法输入:一个算术表达式,由常量、变量、运算符和括号组成(以字符串形式输入)。为简化,规
定操作数只能为正整数,操作符为+、-*、/,用#表示结束。
算法输出:表达式运算结果。
算法要点:设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时,完成
运算符和运算数的识别处理,以及相应运算。
2.概要设计
2.1 数据结构设计
任何一个表达式都是由操作符,运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作
数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连
续的存储单元依次存放自栈底到栈顶的数据元素,同时附设指针 top 指示栈顶元素在顺序栈中的位置,
base 为栈底指针,在顺序栈中,它始终指向栈底,即top=base 可作为栈空的标记,每当插入新的栈
顶元素时,指针 top 增 1,删除栈顶元素时,指针 top 减 1。
2.2 算法设计
为了实现算符优先算法。可以使用两个工作栈。一个称为 OPTR,用以寄存运算符,另一个称做
OPND,用以寄存操作数或运算结果。
1.首先置操作数栈为空栈,表达式起始符”#”为运算符栈的栈底元素;
2.依次读入表达式,若是操作符即进OPND 栈,若是运算符则和 OPTR 栈的栈顶运算符比较优先
权后作相应的操作,直至整个表达式求值完毕(即OPTR 栈的栈顶元素和当前读入的字符均为”#”)。
第 1 页
数据结构课程设计
2.3 ADT 描述
ADT Stack{
数据对象:D={ a | a ∈ElemSet,i=1,2,…,n, n≧0}
i
i
,a
a a D
, ,i=2,…,n}
数据对象:R1={<a
>|
i
i1
i1
i
约定a 端为栈顶,a 端为栈底。
i
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()
初始条件:输入表达式合法。
操作结果:返回表达式的最终结果。
}ADT Stack
2.4 功能模块分析
1.栈的基本功能。
InitStack(Stack *s) 和 InitStack2(Stack2 *s)分别构造运算符栈与构造操作数栈,Push(Stack *s,char
ch) 运算符栈插入 ch 为新的栈顶元素,Push2(Stack2 *s,int ch) 操作数栈插入 ch 为新的栈顶元素,
Pop(Stack *s) 删除运算符栈s 的栈顶元素,用p 返回其值,Pop2(Stack2 *s)删除操作数栈s 的栈顶元素,
第 2 页
剩余19页未读,继续阅读
资源评论
- 拾忆-Eternal゛2023-12-21资源使用价值高,内容详实,给了我很多新想法,感谢大佬分享~
xxpr_ybgg
- 粉丝: 6513
- 资源: 3万+
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功