数据结构课程设计北京理工大学珠海学院计算机科学技术学院第页第页北京理工大学珠海学院《数据结构》课程设计报告题目：____________算术表达式求值_________________所在学院：专业班级：学生姓名：指导教师：2010年05月26日目录TOC\o"1-3"\h\z\uHYPERLINK\l"_Toc263024560"1．前言PAGEREF_Toc263024560\h1HYPERLINK\l"_Toc263024561"2．概要设计PAGEREF_Toc263024561\h1HYPERLINK\l"_Toc263024562"2.1数据结构设计PAGEREF_Toc263024562\h1HYPERLINK\l"_Toc263024563"2.2算法设计PAGEREF_Toc263024563\h1HYPERLINK\l"_Toc263024564"2.3ADT描述PAGEREF_Toc263024564\h2HYPERLINK\l"_Toc263024565"2.4功能模块分析PAGEREF_Toc263024565\h2HYPERLINK\l"_Toc263024566"3．详细设计PAGEREF_Toc263024566\h3HYPERLINK\l"_Toc263024567"3.1数据存储结构设计PAGEREF_Toc263024567\h3HYPERLINK\l"_Toc263024568"3.2主要算法流程图（或算法伪代码）PAGEREF_Toc263024568\h3HYPERLINK\l"_Toc263024569"4．软件测试PAGEREF_Toc263024569\h6HYPERLINK\l"_Toc263024570"5．心得体会PAGEREF_Toc263024570\h8HYPERLINK\l"_Toc263024571"参考文献PAGEREF_Toc263024571\h8HYPERLINK\l"_Toc263024572"附录PAGEREF_Toc263024572\h81．前言在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示结束。算法输出：表达式运算结果。算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。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)初始条件：c