北理工数据结构实验二

1、数据结构与算法设计实验报告实验二学院： 班级： 学号： 姓名： 一、实验目的 1. 通过实验实践、巩固栈的相关操作；2. 熟悉VC环境，加强编程、调试的练习；3. 用C语言实现栈的抽象数据类型，实现栈的建立、进栈、出栈、取数据等基本操作；4. 用C语言实现判断运算符优先级、表达式求值等基本操作；5. 理论知识与实际问题相结合，利用上述基本操作实现简单计算器。二、实验内容 1、简单计算器。请按照四则运算加、减、乘、除、幂（）和括号的优先关系和惯例，编写计算器程序。要求： 从键盘输入一个完整的表达式，以回车作为表达式输入结束的标志。 输入表达式中的数值均为大于等于零的整数。中间的计算过程如果出现小

2、数也只取整。例如，输入：4+2*5=输出：14 输入：(4+2)*(2-10)=输出：-48三、程序设计 1、概要设计为实现上述程序功能，应用栈存储运算符和操作数，为此需要建立一个抽象数据类型：栈。（1）、栈的抽象数据类型定义为：ADT Stack 数据对象：D=ai|aiElemSet,i=1,2,3,n,n0数据关系：R1= |aiD,i=1,2,n基本操作：InitStack(&S)操作结果：创建一个空栈S。Push(&S, e)初始条件：栈S已存在操作结果：插入运算符e作为新的栈顶元素GetTop(&S)初始条件：栈S已存在且非空操作结果：用e返回寄存运算符栈S的栈顶元素Pop(&S,

3、&e)初始条件：栈S已存在且非空操作结果：删除寄存运算符栈S的栈顶元素Operate(a,theta,b)初始条件：a，b为整数，theta为运算符操作结果：返回a与b运算的结果 Precede(d,c)初始条件：d，c为运算符 操作结果：若d优先级大于c,返回；若d优先级小于c,返回；若d优先级等于c,返回=； EvaluateExpression()初始条件：输入合法的表达式操作结果：返回表达式的值ADT Stack主程序流程调用EvaluateExpression()函数计算表达式的值，并将结果输出在屏幕上。各函数模块的调用关系先由主函数调用计算求值函数；再由求值模块调用栈构造函数，构造

4、两个栈分别用来保存操作数和运算符，然后根据情况多次调用进栈、出栈、取栈顶元素、判断运算符优先级、计算表达式的值等多个函数，计算并返回表达式的值；最后由主函数在屏幕上输出表达式的结果。流程图开始=作为运算符栈的栈底元素字符c!=|GetTop1(OPTR)!=?c=+|c=-|c=*|c=/|c=|c=(|c=)|c=?case:操作数栈栈顶2个数运算输入c结束c进入操作数栈返回运算结果输出运算结果YYN 2、详细设计 (1)、宏定义#define STACK_INIT_SIZE 10 / 栈存储空间的初始分配量#define STACKINCREMENT 10 / 空间的分配增量#define

5、 OK 1 / 正确时返回值为真#define ERROR 0 / 出错时返回值为假（2）、抽象数据类型定义typedef char ElemType1;/定义元素类型1为chartypedef int ElemType2;/定义元素类型2为inttypedef struct/栈SqStack1存储元素为char ElemType1 *base; /栈空间基址 ElemType1 *top; /栈顶指针 int stacksize; /当前分配的栈空间大小SqStack1;typedef struct/栈SqStack2存储元素为int ElemType2 *base; /栈空间基址 Elem

6、Type2 *top; /栈顶指针 int stacksize; /当前分配的栈空间大小SqStack2;（3）、操作算法程序实现：int InitStack1( SqStack1 &S ) /构造一个空栈S S.base = ( ElemType1 *)malloc( STACK_INIT_SIZE * sizeof(ElemType1) ); /为顺序栈动态分配存储空间 if ( ! S. base) exit(OVERFLOW); /分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; / InitStack1int

7、 Push1( SqStack1 &S, ElemType1 e ) /将元素e插入栈中，使其成为新的栈顶元素 if ( S.top-S.base=S.stacksize ) / 若栈满则追加存储空间 S.base = (ElemType1 * ) realloc ( S.base,(S.stacksize +STACKINCREMENT) * sizeof(ElemType1); if ( ! S. base ) exit(OVERFLOW); /存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; * S.t

8、op + = e; /元素e 插入栈顶，后修改栈顶指针 return OK; / *S.top=e; S.top +; /Push1char GetTop1( SqStack1 S)/取栈顶元素并返回其值ElemType1 e; if ( S.top=S.base ) return ERROR; /栈空 e = *(S.top-1); return e; /GetTop1int Pop1 ( SqStack1 &S, ElemType1 &e )/删除栈顶元素，并用e返回其值if ( S.top=S.base ) return ERROR; / 栈空 e = * - S.top; / -S.t

9、op; e=*S.top; return OK; /Pop1int InitStack2( SqStack2 &S ) /构造一个空栈S S.base = ( ElemType2 *)malloc( STACK_INIT_SIZE * sizeof(ElemType2) ); /为顺序栈动态分配存储空间 if ( ! S. base) exit(OVERFLOW); /分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; / InitStack2int Push2( SqStack2 &S, ElemType2 e ) /

10、将元素e插入栈中，使其成为新的栈顶元素 if ( S.top-S.base=S.stacksize ) / 若栈满则追加存储空间 S.base = (ElemType2 * ) realloc ( S.base,(S.stacksize +STACKINCREMENT) * sizeof(ElemType2); if ( ! S. base ) exit(OVERFLOW); /存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; * S.top + = e; /元素e 插入栈顶，后修改栈顶指针 return O

11、K; / *S.top=e; S.top +; /Push2int GetTop2( SqStack2 S)/取栈顶元素并返回其值ElemType2 e;if ( S.top=S.base ) return ERROR; /栈空 e = *(S.top-1); return e; /GetTop2int Pop2 ( SqStack2 &S, ElemType2 &e )/删除栈顶元素，并用e返回其值if ( S.top=S.base ) return ERROR; / 栈空 e = * - S.top; / -S.top; e=*S.top; return OK; /Pop2int In (

12、char c)/判断c是否为运算符，是则返回1，否则返回0。if(c=+|c=-|c=*|c=/|c=|c=(|c=)|c=)return 1;elsereturn 0; /Inchar Precede(char d,char c)/判断运算符d与运算符c的优先级switch(c)case+:switch(d)case+:return ;break;case-:return ;break;case*:return ;break;case/:return ;break;case:return ;break;case(:return ;break;case=:return ;break;case-

13、:return ;break;case*:return ;break;case/:return ;break;case:return ;break;case(:return ;break;case=:return ;break;case*:switch(d)case+:return ;break;case-:return ;break;case/:return ;break;case:return ;break;case(:return ;break;case=:return ;break;case/:switch(d)case+:return ;break;case-:return ;bre

14、ak;case/:return ;break;case:return ;break;case(:return ;break;case=:return ;break;case:switch(d)case+:return ;break;case-:return ;break;case*:return ;break;case/:return ;break;case(:return ;break;case=:return ;break;case(:switch(d)case+:return ;break;case-:return ;break;case*:return ;break;case/:ret

15、urn ;break;case:return ;break;case(:return ;break;case=:return ;break;case-:return ;break;case*:return ;break;case/:return ;break;case:return ;break;case(:return =;break;case):return ;break;case=:switch(d)case+:return ;break;case-:return ;break;case*:return ;break;case/:return ;break;case:return ;br

16、eak;case):return ;break;case=:return =;break; /Precedeint Operate(int a,char theta,int b)/运算函数switch(theta)case+:return (a+b);case-:return (a-b);case*:return (a*b);case/:return (a/b);case:return (pow(a,b);/Operateint EvaluateExpression( ) /算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和操作数栈，OP为运算符、界限符集合。char c,th

17、eta;int num,a,b;SqStack1 OPTR;SqStack2 OPND;InitStack1(OPTR);InitStack2(OPND);Push1(OPTR,=);c=getchar( );while (c!=|GetTop1(OPTR)!=) num = 0;if (! In(c) / In(c)判断c是否为运算符 while(!In(c)num*=10;num+=(c-48);c=getchar();Push2(OPND, num); /不是运算符则进栈elseswitch (Precede(GetTop1(OPTR),c) /判定OPTR的栈顶运算符1与读入的运算符2

18、间的优先关系case : /新输入的算符c优先级低，即栈顶算符优先权高/出栈并将运算结果入栈OPNDPop1( OPTR, theta);Pop2( OPND, b);Pop2( OPND, a);Push2( OPND, Operate(a, theta, b) ); /进行二元运算a theta bbreak; /switch /whilereturn GetTop2(OPND); /EvaluateExpression（4）、主程序的代码实现：int main()int x; /定义整形变量x用以接受表达式的值x=EvaluateExpression(); /返回表达式的值printf(

19、%dn,x);/输出表达式的值return 0;四、程序调试分析 1. 引用标识符&不符合C语言语法，应使用C+;2. 存操作数和运算符的栈元素类型不一样，所以要定义两种元素类型、两种栈以及分别对应的基本操作；3. 操作数进栈时要注意连续读完所有非运算符的字符并且把字符型转换为整型；4. pow()函数返回值为double，直接取整会丢失数据，组建时会有警告提示。五、 用户使用说明 1. 本程序的运行环境为DOS操作系统，执行文件为：实验二.exe，双击打开文件。2. 进入程序后，输入要计算的表达式，按Enter键结束。3. 屏幕输出上述表达式的结果，按任意键退出程序。六、程序运行结果测试一：

20、 测试二：测试三：七、程序清单#include #include #include typedef char ElemType1;/定义元素类型1为chartypedef int ElemType2;/定义元素类型2为int#define STACK_INIT_SIZE 10 / 栈存储空间的初始分配量#define STACKINCREMENT 10 / 空间的分配增量#define OK 1 / 正确时返回值为真#define ERROR 0 / 出错时返回值为假typedef struct/栈SqStack1存储元素为charElemType1 *base; /栈空间基址ElemType

21、1 *top; /栈顶指针int stacksize; /当前分配的栈空间大小SqStack1;typedef struct/栈SqStack2存储元素为intElemType2 *base; /栈空间基址ElemType2 *top; /栈顶指针int stacksize; /当前分配的栈空间大小SqStack2;int InitStack1( SqStack1 &S ) /构造一个空栈S S.base = ( ElemType1 *)malloc( STACK_INIT_SIZE * sizeof(ElemType1) ); /为顺序栈动态分配存储空间 if ( ! S. base) ex

22、it(OVERFLOW); /分配失败 S.top = S.base; S.stacksize = STACK_INIT_SIZE; return OK; / InitStack1int Push1( SqStack1 &S, ElemType1 e ) /将元素e插入栈中，使其成为新的栈顶元素 if ( S.top-S.base=S.stacksize ) / 若栈满则追加存储空间 S.base = (ElemType1 * ) realloc ( S.base,(S.stacksize +STACKINCREMENT) * sizeof(ElemType1); if ( ! S. base

23、 ) exit(OVERFLOW); /存储分配失败 S.top = S.base + S.stacksize; S.stacksize += STACKINCREMENT; * S.top + = e; /元素e 插入栈顶，后修改栈顶指针 return OK; / *S.top=e; S.top +; /Push1char GetTop1( SqStack1 S)/取栈顶元素并返回其值ElemType1 e; if ( S.top=S.base ) return ERROR; /栈空 e = *(S.top-1); return e; /GetTop1int Pop1 ( SqStack1

24、&S, ElemType1 &e )/删除栈顶元素，并用e返回其值if ( S.top=S.base ) return ERROR; / 栈空 e = * - S.top; / -S.top; e=*S.top; return OK; /Pop1int InitStack2( SqStack2 &S ) /构造一个空栈S S.base = ( ElemType2 *)malloc( STACK_INIT_SIZE * sizeof(ElemType2) ); /为顺序栈动态分配存储空间 if ( ! S. base) exit(OVERFLOW); /分配失败 S.top = S.base;

25、S.stacksize = STACK_INIT_SIZE; return OK; / InitStack2int Push2( SqStack2 &S, ElemType2 e ) /将元素e插入栈中，使其成为新的栈顶元素 if ( S.top-S.base=S.stacksize ) / 若栈满则追加存储空间 S.base = (ElemType2 * ) realloc ( S.base,(S.stacksize +STACKINCREMENT) * sizeof(ElemType2); if ( ! S. base ) exit(OVERFLOW); /存储分配失败 S.top = S

26、.base + S.stacksize; S.stacksize += STACKINCREMENT; * S.top + = e; /元素e 插入栈顶，后修改栈顶指针 return OK; / *S.top=e; S.top +; /Push2int GetTop2( SqStack2 S)/取栈顶元素并返回其值ElemType2 e;if ( S.top=S.base ) return ERROR; /栈空 e = *(S.top-1); return e; /GetTop2int Pop2 ( SqStack2 &S, ElemType2 &e )/删除栈顶元素，并用e返回其值if (

27、S.top=S.base ) return ERROR; / 栈空 e = * - S.top; / -S.top; e=*S.top; return OK; /Pop2int In (char c)/判断c是否为运算符，是则返回1，否则返回0。if(c=+|c=-|c=*|c=/|c=|c=(|c=)|c=)return 1;elsereturn 0;/In char Precede(char d,char c)/判断运算符d与运算符c的优先级switch(c)case+:switch(d)case+:return ;break;case-:return ;break;case*:retur

28、n ;break;case/:return ;break;case:return ;break;case(:return ;break;case=:return ;break;case-:return ;break;case*:return ;break;case/:return ;break;case:return ;break;case(:return ;break;case=:return ;break;case*:switch(d)case+:return ;break;case-:return ;break;case/:return ;break;case:return ;break

29、;case(:return ;break;case=:return ;break;case/:switch(d)case+:return ;break;case-:return ;break;case/:return ;break;case:return ;break;case(:return ;break;case=:return ;break;case:switch(d)case+:return ;break;case-:return ;break;case*:return ;break;case/:return ;break;case(:return ;break;case=:retur

30、n ;break;case(:switch(d)case+:return ;break;case-:return ;break;case*:return ;break;case/:return ;break;case:return ;break;case(:return ;break;case=:return ;break;case-:return ;break;case*:return ;break;case/:return ;break;case:return ;break;case(:return =;break;case):return ;break;case=:switch(d)case+