X X X X X大学
《程序设计方法学》实验报告
实验一：算术表达式求值
学院：X X X
专业：计算机科学与技术 姓名：X X X 学号：XXXXX
2010年11 月 18 日
目录
1．前 言................................................................................................................................. 1 2．概要设计................................................................................................................................. 1
2.1 数据结构设计........................................................................................................................................................................ 1 2.2 算法设计 .............................................................................................................................................................................. 1 2.3 ADT描述 ............................................................................................................................................................................. 2 2.4 功能模块分析 ..................................................................................................................................................................... 3
3．详细设计................................................................................................................................. 3
3.1 数据存储结构设计............................................................................................................................................................... 3 3.2主要算法流程图（或算法伪代码）................................................................................................................................. 4
4．测试结果................................................................................................................................. 7 5．参考文献................................................................................................................................. 8 附 录--程序源代码 ...................................................................................................................... 8
1．前 言
在计算机中，算术表达式由常量、变量、运算符和括号组成。由于不同的运算符具有不同的优先级，又要考虑括号，因此，算术表达式的求值不可能严格地从左到右进行。因而在程序设计时，借助栈实现。
算法输入：一个算术表达式，由常量、变量、运算符和括号组成（以字符串形式输入）。为简化，规定操作数只能为正整数，操作符为+、-*、/，用#表示结束。
算法输出：表达式运算结果。
算法要点：设置运算符栈和运算数栈辅助分析算符优先关系。在读入表达式的字符序列的同时，完成运算符和运算数的识别处理，以及相应运算。
2．概要设计
2.1 数据结构设计
任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。
2.2 算法设计
为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR，用以寄存运算符，另一个称做OPND，用以寄存操作数或运算结果。
1.首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素；
2.依次读入表达式，若是操作符即进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为”#”）。
2.3 ADT描述
ADT Stack{
数据对象：D={ai |ai∈ElemSet,i=1,2,…，n, n≧0} 数据对象：R1={|ai?1,ai?D,i=2,…，n}
约定an端为栈顶，ai端为栈底。
基本操作：
InitStack (SqStack &S)
操作结果：构造一个空栈S。
GetTop (SqStack S, SElemType &e) 初始条件：栈S已存在。
操作结果：则用e返回S的栈顶元素。
Push(SqStack &S,SElemType e) 初始条件：栈S已存在。
操作结果：插入元素e为新的栈顶元素。
Pop(SqStack &S,SElemType &e) 初始条件：栈S已存在。
操作结果：删除S的栈顶元素，用e返回其值。
In(char d)
操作结果：判断字符是否是运算符，运算符即返回1。
Precede(char a1 ,char a2) 初始条件：a1,a2为运算符。
操作结果：判断运算符优先权，返回优先权高的。
Operate( SElemType a, SElemType theta, SElemType b ) 初始条件：a,b为整数，theta为运算符。
操作结果：a与b进行运算，op为运算符，返回其值。
EvaluateExpression()
初始条件：输入表达式合法。
操作结果：返回表达式的最终结果。 }ADT Stack
2.4 功能模块分析
1.栈的基本功能。
InitStack(Stack *s) 和InitStack2(Stack2 *s)分别构造运算符栈与构造操作数栈，Push(SqStack &S1,SElemType e) 运算符栈插入e为新的栈顶元素，Push(SqStack &S2,SElemType e) 操作数栈插入e为新的栈顶元素，Pop(SqStack &S1,SElemType &e)删除运算符栈s的栈顶元素，用e返回其值，Pop(SqStack &S2,SElemType &e)删除操作数栈s的栈顶元素，用e返回其值，GetTop (SqStack S1, SElemType &e)用e返回运算符栈s的栈顶元素，GetTop (SqStack S2, SElemType &e) 用e返回操作数栈s的栈顶元素。 2.其它功能分析。
(1)In(char ch) 判断字符是否是运算符功能，运算符即返回1，该功能只需简单的一条语句即可实现，return(ch=='+'||ch=='-'||ch=='*'||ch=='/'||ch=='('||ch==')'||ch=='#')。
(2) Precede(char a1,char a2) 判断运算符优先权功能，该函数判断运算符a1,a2的优先权. (3) Operate( SElemType a, SElemType theta, SElemType b )操作数用对应的运算符进行运算功能。运算结果直接返回。
(4) EvaluateExpression()主要操作函数运算功能。
3．详细设计
3.1 数据存储结构设计
因为表达式是由操作符，运算符和界限符组成的。如果只用一个char类型栈，不能满足2位以
上的整数，所以还需要定义一个int类型的栈用来寄存操作数。
/* 定义字符类型栈 */ typedef struct{
char *base; char *top; int stacksize;
} Stack;
/* 定义整型栈 */ typedef struct{ int *base; int *top;