数据结构实习报告：设计一个演示用运算优先法对算数表达式求值过程的程序

1、.实习报告题目：设计一个演示用运算优先法对算数表达式求值过程的程序。班级：姓名：学号：完成日期：一、需求分析1 建立运算数栈 SqStack1 和运算符栈 SqStack2辅助分析算符有限关系.2 用户输入以“ #”结尾的算数表达式， 本程序需要用户自行输入表达式（运算符可以是加 （+）；减（- ）；乘（* ）；除（/ ）；括号（），以字符形式读入，在读入的同时，完成运算符和运算数的识别处理，在识别出运算数的同时，要将其字符序列形式转换成整数形式。3 在程序的适当位置输出运算符栈、运算数栈、输入字符和主要操作的内容，即演示运算操作。4 测试数据见原题。5 程序执行的命令包括：（1）建立算数表达

2、式；（2）得到运算表达式的值；（3）演示运算过程。二、概要设计1. 设定栈的抽象数据类型定义：ADT Stack数据对象D ai | ai charSet, i=1,2,.,n,n0 ;.数据关系：R1 <ai-1, ai >| ai-1, aiD, i=2,.,n （约定 an 端为栈顶， a1 端为栈底）基本操作：InitStack（&S）操作结果：构造一个空栈S。Gettop(S,&e)初始条件：栈 S 已存在。操作结果：若栈S 不空，则以 e 返回栈顶元素。Push(&S,e)初始条件：栈S 已存在。操作结果：插入元素e 为新的栈顶元素。Pop(&a

3、mp;S,&e)初始条件：栈S 已存在且非空。操作结果：删除S 的栈顶元素，并用e 返回其值。ADT Stack2. 本程序包括三个模块（1）主程序模块：Void main( )初始化；函数；;.（ 2）栈模块实现栈抽象数据类型（ 3）运算模块实现运算并演示其过程模块各模块之间调用关系如下：主程序模块运算模块栈模块三、详细设计1、元素类型、结点类型typedef structint *base;int *top;int stacksize;SqStack1;/操作数栈typedef structchar *base;char *top;int stacksize;SqStack2;/操

4、作符栈2、 栈类型typedef structchar *base;char *top;int stacksize;Stack;/栈类型栈的基本操作设置如下：void InitStack(Stack &S)/初始化，设 S 为空栈（ S.top=NULL ）;.Status GetTop(Stack S,ElemType e)/若栈 S 不空，则以 e 带回栈顶元素并返回 TRUE，否则返回 FALSE Status Push(Stack&S,ElemType e)/若分配空间成功，则在S 的栈顶插入新的栈顶元素e，并返回 TRUE ，/否则返回 FALSE 其中部分操作的算法

5、：Status Push(Stack &S,ElemType e)/若分配空间成功，则在S 的栈顶插入新的栈顶元素e，并返回 TRUE ；/否则栈不变，并返回FALSEif(MakeNode(p,e)P.next=S.top;S.top=p;S.size+;Return TRUE;else return FALSE;Status Pop(Stack &S,ElemType &e)/若栈不空，则删除S 的栈顶元素并以e 带回其值，且返回TRUE ，/否则返回 FALSE，且 e 无意义if(StackEmpty(S) return FALSE;elsep=S.top;S.

6、top=S.top->next;e=p->:data;S.size-;return TRUE;3、运算代码int Operate(int a,char theta,int b) /计算表达式值：主要是将大的表达式转化成小的表达式进行逐步求值int c;if(theta='+') c=a+b;else if(theta='-') c=a-b;else if(theta='*') c=a*b;else c=a/b;return c;/Operateint result(SqStack1 *OPND,SqStack2 *OPTR) /求值c

7、har a=0;char theta;int b,c,number=0;.IntInitStack(OPND);CharInitStack(OPTR);CharPush(OPTR,'#');a=getchar();while(a!='#' | CharGetTop(OPTR)!='#')printf("输入字符： %c",a);if(!In(a)/ 不是运算符则进栈number=0;while(!In(a)number = number*10 +(a-48);/处理多位整数z=10*x+ya = getchar();IntPu

8、sh(OPND,number);printf("主要操作： Push(OPND,%d)",number);elseswitch(Precede(a,CharGetTop(OPTR)case '<':CharPush(OPTR,a);a=getchar();printf("主要操作： Push(OPTR,%c)",a);break;case '=':CharPop(OPTR);a=getchar();printf("主要操作： Pop(OPTR,%c)",a);break;case '>

9、;':theta=CharPop(OPTR);c=IntPop(OPND);b=IntPop(OPND);IntPush(OPND,Operate(b,theta,c);printf("主要操作：Operate(%d,%c,%d)",b,theta,c);break;printf("OPND栈：%dOPTR栈： %cn",IntGetTop(OPND),CharGetTop(OPTR);.printf("The result is %d.n",IntGetTop(OPND); /打印输出表达式值return OK;4. 主函数

10、和其他函数的代码void main() /主函数，使用自定义函数完成功能SqStack1 s1,*OPND;SqStack2 s2,*OPTR;OPND=&s1;OPTR=&s2;printf("Please enter an expression with a end of '#'.n");printf("The Expression:");result(OPND,OPTR);char Precede(char a,char b)/运算优先级判断int i,j;char Table88=' ','

11、+','-','*','/','(',')','#', '+','>','>','<','<','<','>','>', '-','>','>','<','<','<','>',

12、'>', '*','>','>','>','>','<','>','>', '/','>','>','>','>','<','>','>', '(','<','<','&

13、lt;','<','<','=',' ', ')','>','>','>','>',' ','>','>','#','<','<','<','<','<',' ','=',; /优先级表格for

14、(i=0;i<8;i+)if(Table0i=a) /纵坐标寻找break;for(j=0;j<8;j+) /横坐标寻找if(Tablej0=b)break;return Tableji;int In(char c)/ 判断 c 是否为操作符if ( c='(' | c='+' | c='-' | c = '*' | c='/' | c=')' | c='#' | c='')return 1;/ 如果是操作符返回1elsereturn 0;/ 不是，返回

15、0;.5函数的调用关系图反映了演示程序的层次结构：mainresultInitStackPushGetTopInPrecedePop四、调试分析算术表达式求值程序较为庞大，调试花费时间较多，主要是在for循环和 while 循环时容易出错，对于涉及的循环的操作开始和结束条件设置很关键。五、用户手册1. 本程序开发环境为 VC 6.0，运行环境为 dos 操作系统，执行文件为：1.exe2. 运行该程序后 ,产生如下图所示的界面：;.3. 按照提示输入一组表达式。4. 输入完成后，按回车键。5. 屏幕上打印出对应于该表达式的后缀表达式。6. 打印表达式计算结果。六、测试结果1.2.3;.4.七、

16、附录源程序文件名清单：1.cpp/主程序1.exe/可执行文件stdio.h/ 程序中用到的头文件stdlib.h/程序中用到的头文件string.h/程序中用到的头文件math.h/程序中用到的头文件程序代码：#include<stdio.h>#include<stdlib.h>#include<string.h>.#include<math.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define ERROR 0#define OK 1/*栈模块typedef struct S

17、qStack1/运算数栈int *base;int *top;int stacksize;SqStack1;typedef struct SqStack2/运算符栈char *base;char *top;int stacksize;SqStack2;void IntInitStack(SqStack1 *S)S->base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!S->base) exit(ERROR);.S->top=S->base;S->stacksize=STACK_INIT_SIZE;void Cha

18、rInitStack(SqStack2 *S)S->base=(char *)malloc(STACK_INIT_SIZE*sizeof(char);if(!S->base) exit(ERROR);S->top=S->base;S->stacksize=STACK_INIT_SIZE;int IntGetTop(SqStack1 *S) /取栈顶元素int e;if(*S).top=(*S).base)return 0;e=*(*S).top-1);return e;char CharGetTop(SqStack2 *S) /取栈顶元素char e;if(*S)

19、.top=(*S).base) return 0;.e=*(*S).top-1);return e;int IntPush(SqStack1 *S,int e)*(*S).top+=e;return OK;int CharPush(SqStack2 *S,char e)*(*S).top+=e;return OK;int IntPop(SqStack1 *S)int e;if(*S).top=(*S).base) return 0;e=*-(*S).top;return e;int CharPop(SqStack2 *S);.char e;if(*S).top=(*S).base) retur

20、n 0;e=*-(*S).top;return e;/*运算模块char Precede(char a,char b)/运算优先级判断int i,j;char Table88=' ','+','-','*','/','(',')','#', '+','>','>','<','<','<','>','>'

21、;, '-','>','>','<','<','<','>','>', '*','>','>','>','>','<','>','>', '/','>','>','>','

22、;>','<','>','>', '(','<','<','<','<','<','=',' ', ')','>','>','>','>',' ','>','>', '#','

23、;<','<','<','<','<',' ','=', ; /优先级表格for(i=0;i<8;i+);.if(Table0i=a) / 纵坐标寻找break;for(j=0;j<8;j+) / 横坐标寻找if(Tablej0=b)break;return Tableji;int Operate(int a,char theta,int b) / 计算表达式值：主要是将大的表达式转化成小的表达式进行逐步求值int c;if(theta='+

24、') c=a+b;else if(theta='-') c=a-b;else if(theta='*') c=a*b;else c=a/b;return c;/Operateint In(char c)/判断 c 是否为操作符if ( c='(' | c='+' | c='-' | c = '*' | c='/' | c=')' | c='#' | c='')return 1;/如果是操作符返回1;.elsereturn 0;/

25、不是，返回 0int result(SqStack1 *OPND,SqStack2 *OPTR) /求值char a=0;char theta;int b,c,number=0;IntInitStack(OPND);CharInitStack(OPTR);CharPush(OPTR,'#');a=getchar();while(a!='#' | CharGetTop(OPTR)!='#')printf(" 输入字符： %c",a);if(!In(a)/不是运算符则进栈number=0;while(!In(a)number = number*10