到实数。 一、问题分析和任务定义 要对一个含有加减乘除四则运算的合法的算术表达式进行求值， ①首先，应了解算术表达式的四则运算的规则： (1)从左向右计算 (2)先乘除，后加减 (3)先括号内，后括号外 由此可知，比如算术表达式（7+15）*（23-28/4）的计算顺序，即 为 （7+15）*（23-28/4）=22*（23-28/4）=22*（23-7） =22*1法就是根据上述四则运算规则确定的优先关系来实现对表 达式的编译或解释执行的。 一个简单的四则运算表达式由操作数（operand）、运算符 （operator）和界限符（delimiter）组成，其中操作数是正整数，运算符 只含加、减、乘、除四种，界限符有左右括号和表达式起始、结束 符“#”；而且，为了统一算法的描述，将运算符和界限符通称为算 符。算符集OP=｛+，-，*，/，（，），#｝。 根据上述3条运算规则，在具体的运算的每一步中，任意两个相继 出现的算符θ1和θ2之间的优先关系只能是如下3中关系之一： θ1<θ2 θ1的优先级低于θ2 θ1=θ2 θ1的优先级等于θ2 θ1>θ2 θ1的优先级高于θ2 下表定义了算符之间的这种优先关系。
算符栈的初始化 获取算符栈的栈顶元素 算符栈的栈顶插入新的数据元素 算符栈的栈顶元素出栈
表3 操作数栈的功能函数
OPND栈
int OPND_InitStack(OPND _STACK &s) double OPND_GetTop(OPND _STACK &s) int OPND_Push(OPND_STACK &s, double e) int OPND_Pop(OPND_STACK &s, double &e)
合肥学院 计算机科学与技术系
课程设计报告
2009～2010学年第二学期
课程 课程设计名 称 学生姓名 学号 专业班级 指导教师 数据结构与算法 算术表达式求值问题 杨松 0804012031 08计科(2) 王昆仑 张贯虹 2010年6月
题目：（算术表达式求值问题）一个算术表达式是由操作数 (operand)、运算符(operator)和界限符(delimiter)组成的。假设操作 数是正整数，运算符只含加减乘除四种运算符，界限符有左右括号和表 达式起始、结束符“#”，如：#（7+15）*（23-28/4）#。引入表达式 起始、结束符是为了方便。编程利用“算符优先法”求算术表达式的 值。要求：（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中情况各自之间无优先关系，表示为“ ”，因为 表达式中不允许它们相继出现，如果出现，则可以认为出现语法错误。 ③最后，确定算法的基本思想： 设置两个工作栈，一个为OPTR栈，存放运算符；另一个为OPND 栈，存放操作数或运算结果。则算法的基本思想描述如下： (1)首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元 素； (2)依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算 符则和OPTR栈的栈顶运算符比较优先级后，做如下相应操作： ①若栈顶算符θ1的优先级低于刚读入的算符θ2，则将θ2入算符栈 OPTR ②若栈顶算符θ1的优先级高于刚读入的算符θ2，则将让θ2出栈；同 时，将操作数栈OPND退栈两次，得到两个操作数x、y，对x、y运用θ2 进行运算后，再将运算结果如操作数只栈OPND ③若栈顶算符算符θ1的优先级等于刚读入的算符θ2，说明左右括号 相遇，或者是表达式的起始、结束符相遇，只需将栈顶算符（左括号或 起始符）退栈即可；当算符栈OPTR栈空时，算法结束。 二、数据结构的选择和概要设计 数据结构的选择： 本程序采用顺序存储结构存储两个栈，即操作数栈（OPND）和算符 栈（OPTR）；
1、int OPND_InitStack(OPND_STACK &s) 为OPTR栈申请double类型的初始空间STACK_INITSIZE=100个 操作结果：构造一个空栈S，最大长度s.stacksize为100； 2、double OPND_GetTop(OPND_STACK &s) 初始条件：OPND栈S已存在且非空（s.top!=s.base） 操作结果：用e= *(s.top-1)返回S的栈顶元素 3、int OPND_Push(OPND_STACK &s,double e) 初始条件：OPND栈S已存在 因为考虑到原先申请的空间可能不够，即当OPND栈的长度已经大 于s.stacksize=100，这是需要申请额外的存储空间；每次均用realloc函数 申请double类型的额外的STACKINCREMENT=10个存储单元，申请额 外空间后的OPND栈的最大长度s.stacksize增加10； 操作结果：插入元素ｅ为新的OPND栈顶元素，即*s.top++=e； 4、int OPND_Pop(OPND_STACK &s,double &e) 初始条件：OPND栈S已存在且非空； 操作结果：OPND栈顶元素出栈，同时用e保存该栈顶元素，即e=*-s.top； （3）下面实现本课程设计目标的算术表达式的相关功能函数的详细设 计过程： 首先应定义7种算符的字符数组char OPSET[OPSETSIZE]={'+' , '-' , '*' , '/' ,'(' , ')' , '#'}; 然后是7算符的的优先级的定义： char Prior[7][7] = { '>' , '>' , '<' , '<' , '<' , '>' , '>', '>' , '>' , '<' , '<' , '<' , '>' , '>', '>' , '>' , '>' , '>' , '<' , '>' , '>', '>' , '>' , '>' , '>' , '<' , '>' , '>', '<' , '<' , '<' , '<' , '<' , '=' , ' ', '>' , '>' , '>' , '>' , ' ' , '>' , '>', '<' , '<' , '<' , '<' , '<' , ' ' , '=' }; 因为算术表达式涉及到两个数的四则运算，所以要设计一个两个数 四则运算的函数，即函数double Operate( double a, char theta, double b)，定义了两个数的(加)+、(减)-、(乘)*、(除)/ 四种运算，并返回两个 数的运算结果。 然后，当依次读入算术表达式的各个字符时，要同时判断字符的合法
操作数栈的初始化 获取操作数栈的栈顶元素 操作数栈的栈顶插入新的数据元 素 操作数栈的栈顶元素出栈
表4 算术表达式的相关功能函数 double Operate( double a, char theta, 两个操作数之间的四则运算函数 double b) int In(char Test, char * TestOp) int ReturnOpOrd(char op, char* TestOp)
概要设计如下： 运算符栈的相关功能函数 操作数栈的相关功能函数 算术表达式的相关功能函数 主函数
表2 运算符栈的功能函数
OPTR栈
int OPTR_InitStack(OPTR_STACK &s) char OPTR_GetTop(OPTR_STACK &s) int OPTR_Push(OPTR_STACK &s, char e) int OPTR_Pop(OPTR_STACK &s, char &e)