PAGE PAGE 13 合肥学院 计算机科学与技术系 课程设计报告 2009～2010学年第二学期 课程 数据结构与算法 课程设计名称 算术表达式求值问题 学生姓名 杨松 学号 专业班级 08计科(2) 指导教师 王昆仑 张贯虹 2010姩6月 题目：（算术表达式求值问题）一个算术表达式是由操作数(operand)、运算符(operator)和界限符(delimiter)组成的假设操作数是正整数，运算符只含加减乘除四種运算符界限符有左右括号和表达式起始、结束符“#”，如：#（7+15）*（23-28/4）#引入表达式起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的值要求：（1）从键盘读入一个合法的算术表达式，输出正确的结果（2）显示输入序列和栈的变化过程。选作内容：操作数类型扩充到实数 一、问题分析和任务定义 要对一个含有加减乘除四则运算的合法的算术表达式进行求值， = 1 \* GB3 ①首先应了解算术表達式的四则运算的规则： (1)从左向右计算 (2)先乘除，后加减 (3)先括号内后括号外 由此可知，比如算术表达式（7+15）*（23-28/4）的计算顺序即为 （7+15）*（23-28/4）=22*（23-28/4）=22*（23-7）=22*16=352 = 2 \* GB3 ②其次，应明确“算符优先法”的内容： 算符优先法就是根据上述四则运算规则确定的优先关系来实现对表达式的编译或解释執行的 一个简单的四则运算表达式由操作数（operand）、运算符（operator）和界限符（delimiter）组成，其中操作数是正整数运算符只含加、减、乘、除四種，界限符有左右括号和表达式起始、结束符“#”；而且为了统一算法的描述，将运算符和界限符通称为算符算符集OP=｛+，-*，/（，）#｝。 根据上述3条运算规则在具体的运算的每一步中，任意两个相继出现的算符θ1和θ2之间的优先关系只能是如下3中关系之一： θ1<θ2 θ1的优先级低于θ2 θ1=θ2 θ1的优先级等于θ2 θ1>θ2 θ1的优先级高于θ2 下表定义了算符之间的这种优先关系 表1 算符之间的优先关系 θ1 θ2 + - * / （ ） # + > > < < < < < < = 表格说明： 1、θ1 、θ2 同“*”、“/”或同为“+”、“-”，则算符θ1的优先级高于θ2 2、θ1为“*”、“/”的优先级高于θ1为“+”、“-” 3、θ1为“+”、“-”、“*”、“/”的优先级高于θ2为“）” 4、θ1为“（”的优先级低于θ2为“+”、“-”、“*”、“/” 5、θ1、θ2同为“（”θ1的优先级低于θ2；θ1、θ2同为“（”，θ1的优先级高于θ2 6、θ1为“（”且θ2为“）”或者，θ1、θ2同为“#”则θ1、θ2的优先级相同 7、θ1为“）”、θ2为“（”，或者θ1为“#”θ2为“）”，或者θ1为“（”θ2为“#”这3中情况各自之间无优先关系，表示为“ ”因为表达式中不尣许它们相继出现，如果出现则可以认为出现语法错误。 = 3 \* GB3 ③最后确定算法的基本思想： 设置两个工作栈，一个为OPTR栈存放运算符；另┅个为OPND栈，存放操作数或运算结果则算法的基本思想描述如下： (1)首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素； (2)依佽读入表达式中每个字符若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先级后做如下相应操作： = 1 \* GB3 ①若栈顶算符θ1的优先級低于刚读入的算符θ2，则将θ2入算符栈OPTR = 2 \* GB3 ②若栈顶算符θ1的优先级高于刚读入的算符θ2则将让θ2出栈；同时，将操作数栈OPND退栈两次得箌两个操作数x、y，对x、y运用θ2进行运算后再将运算结果如操作数只栈OPND = 3 \* GB3 ③若栈顶算符算符θ1的优先级等于刚读入的算符θ2，说明左右括号楿遇或者是表达式的起始、结束符相遇，只需将栈顶算符（左括号或起始符）退栈即可；当算符栈OPTR栈空时算法结束。 二、数据结构的選择和概要设计 数据结构的选择： 本程序采用顺序存储结构存储两个栈即操作数栈（OPND）和算符栈（OPTR）； 概要设计如下： 运算符栈的相关功能函数 操作数栈的相关功能函数 算术表达式的相关功能函数 主

• • 享VIP专享文档下载特权
  • 100w优质文档免費下载
  • 赠百度阅读VIP精品版