数据结构中栈和队列的应用数据结构程序设计实验报告1

1、实验报告课程名称 数据结构程序设计实验项目数据结构中栈和队列的应用系 别 计算机学院专 业网络工程班级/学号_网工1202/2012011411_学生姓名王宇涵实验日期_2014年6月2日成 绩指导教师黄改娟 田英爱实验题目 : 表达式的运算一、程序功能分析 （1）程序整体功能流程分析如下。 第一步，用户输入表达式。第二步，对用户输入的表达式进行过滤， 如果有错， 请用户重新输入正确表达式； 否则， 返回正确的表达式。第三步，对表达式进行处理，将运算数和运算符按照“计算器算法”分别压入栈中，并 在此过程中记录顶元素的变化情况。第四步，最后，返回结果，打印输出。.、rt 、【 一二、设计方案（

2、1）数据结构设计 任何一个表达式都是由操作符， 运算符和界限符组成的。 我们分别用顺序栈来寄存表达 式的操作数和运算符。 栈是限定于紧仅在表尾进行插入或删除操作的线性表。 顺序栈的存储 结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素， 同时附设指针 top 指示 栈顶元素在顺序栈中的位置， base 为栈底指针， 在顺序栈中， 它始终指向栈底， 即 top=base 可作为栈空的标记，每当插入新的栈顶元素时，指针 top 增 1，删除栈顶元素时，指针 top 减 1。为了实现算符优先算法。可以使用两个工作栈。一个称为OPTR用以寄存运算符，另一个称做OPND用以寄存操作数或运算结果

3、。1. 首先置操作数栈为空栈，表达式起始符”#”为运算符栈的栈底元素；2. 依次读入表达式，若是操作符即进 OPN戯，若是运算符则和 OPTR栈的栈顶运算符比较优先权后作相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为” #”）。（ 2）数据存储结构 因为表达式是由操作符，运算符和界限符组成的。如果只用一个char 类型栈，不能满足 2 位以上的整数，所以还需要定义一个 int 类型的栈用来寄存操作数。定义两个栈的类型如下：/* 定义字符类型栈 */typedef structint stacksize;char *base;char *top; Stack;ty

4、pedef structint stacksize;int *base;int *top; Stack2;1. Precede(char c1,char c2)判断运算符优先权，返回优先权高的。算符间的优先关系如下：+-*/()#+><<<<>>->><<<>>*>>>><>>/>>>><>>(<<<<<=)>>>>>>#<<<<<=

5、算法步骤：第一步，如果输入符号位“ +”或“减”。如果栈顶元素为“(”，“#”，此时栈顶符号优先级高，返回“ <”；否则，栈顶符号优先级高，返回“ >”。第二步，如果输入符号为“* ”或“ / ”。如果栈顶元素为“)”“* ”此时栈顶元素符号优先级高，返回“>”，否则，栈顶符号优先级低，返回“ <”。第三步，如果输入符号为“(”，则直接返回“ <”。第四步，如果输入符号为“)”.如果栈顶原素为“(”，此时优先级同，返回“=”否则栈顶符号优先级高，返回“>”。第五步，输入符号为其他。栈顶元素为“ #”，此时优先级同，返回“=”；否则，栈顶元素符号优先级高，返回

6、“ >” <算法代码char Precede(char c1,char c2)>',J'>',J'<',J'<',J'<',5'>',l 5'>',l J>',J'>',J'<',J'<',J'<',5'>',l 5'>',l J>',J'>',J'&

7、gt;',J'>',J'<',5'>',l 5'>',l J>',J'>',J'>',J'>',J'<',5'>',l 5'>',l J<',J'<',J'<',J'<',J'<',51 1l1'!',l J>',J'

8、>',J'>',J'>',J'!',J'>',J'>',J<',J'<',J'<',J'<',J'<',5'!',l J'=' /static char array49=用一维数组存储49 种情况switch(c1)/* i 为下面 array 的横标 */ case '+' : i=0;break;case '-'

9、; : i=1;break;case '*' : i=2;break;case '/' : i=3;break;case '(' : i=4;break;case ')' : i=5;break;case '#' : i=6;break;switch(c2)/* j 为下面 array 的纵标 */ case '+' : j=0;break;case '-' : j=1;break;case '*' : j=2;break;case '/' : j=3

10、;break;case '(' : j=4;break;case ')' : j=5;break;case '#' : j=6;break;返回运算符 array7*i+j 为对应的 c1,c2 优先关系return (array7*i+j); /2. i nt EvalExpr()主要操作函数。算法概要流程图:char c=ft达式首字符操作数橈头2个数进行r etumG etTop 2 (C P N E1)运算 #利用该算法对算术表达式3*(7-2)求值操作过程如下:步骤OPTR栈OPND栈输入字符主要操作1#3*(7-2)#PushQPND

11、,' 3')2#3*(7-2)#PushQPTR,' *')3#*3(7-2)#PushQPNR,'(')4#*(37-2)#PushQPND,' 7')5#*(3 7-2)#PushQPNR,'-')6#*(-3 72)#PushQPND,' 2')7#*(-3 7 2)#Operate( ' 7' , ' -' , ' 2')8#*(3 5)#Pop(OPTR)9#*3 5#Operate( ' 3' , ' *'

12、,5 ')10#15#Return(GetTop2(OPND)算法代码如下:int EvalExpr()主要操作函数 c = *ptr+;while(c!='#'|GetTop(OPTR)!='#')if(!In(c) /不是运算符即进栈 if(!In(*(ptr-1) ptr=ptr-1;m=atoi(ptr);/ 取字符串前面的数字段m=atoi(ptr);/ 取字符串前面的数字段 n=num(m);Push2(&OPND,m);ptr=ptr+n;c=*ptr+;elseswitch(Precede(GetTop(OPTR),c)case

13、'<': / 栈顶元素优先权底Push(&OPTR,c);c = *ptr+;break;case '=': / 脱括号并接收下一字符x=Pop(&OPTR);c = *ptr+;break;case '>':/ 退栈并将运算结果入栈theta=Pop(&OPTR); b=Pop2(&OPND); a=Pop2(&OPND);Push2(&OPND,Operate(a,theta,b); break;程序代码#include <stdio.h>#include <std

14、lib.h>#include <string.h>#define NULL 0 #define OK 1#define ERROR -1 #define STACK_INIT_SIZE 100#define STACKINCREMENT 20 /* 定义字符类型栈 */ typedef structint stacksize;char *base;char *top; Stack; / 栈的类型/* 定义整型栈 */typedef structint stacksize; / 栈类型个数int *base;int *top; Stack2;/* 全局变量 */Stack OP

15、TR;/* 定义运算符栈 */存放表达式串 */构造运算符栈Stack2 OPND; /* 定义操作数栈 */ char expr255 = "" /* char *ptr = expr;int InitStack(Stack *s) /建立新结点s->base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); / if(!s->base) return ERROR;s->top=s->base; s->stacksize=STACK_INIT_SIZE; return OK;int InitStack2

16、(Stack2 *s) / 构造操作数栈 s->base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!s->base) return ERROR;s->stacksize=STACK_INIT_SIZE;s->top=s->base;return OK;int In(char ch) / 判断字符是否是运算符，运算符即返回 1 return(ch='+'|ch='-'|ch='*'|ch='/'|ch='('|ch=')'

17、;|ch='#');int Push(Stack *s,char ch) /运算符栈插入 ch 为新的栈顶元素*s->top=ch;s->top+;return 0;int Push2(Stack2 *s,int ch)/操作数栈插入 ch 为新的栈顶元素 *s->top=ch;s->top+;return 0;char Pop(Stack *s) / 删除运算符栈 s 的栈顶元素，用 p 返回其值 char p;s->top-;p=*s->top;return p;int Pop2(Stack2 *s)/ 删除操作数栈 s 的栈顶元素，用

18、p 返回其值int p; s->top-; p=*s->top; return p;char GetTop(Stack s)/用 p 返回运算符栈 s 的栈顶元素char p=*(s.top-1); return p;int GetTop2(Stack2 s) / 用 p 返回操作数栈 s 的栈顶元素 int p=*(s.top-1);return p;/* 判断运算符优先权，返回优先权高的 */char Precede(char c1,char c2)是数组int i=0,j=0;static char array49= /array'>', '&g

19、t;', '<', '<', '<', '>', '>', '>', '>', '<', '<', '<', '>', '>', '>', '>', '>', '>', '<', '>', 

20、9;>', '>', '>', '>', '>', '<', '>', '>', '<', '<', '<', '<', '<', '=', '!', '>', '>', '>', '>', '

21、!', '>', '>', '<', '<', '<', '<', '<', '!', '=' switch(c1) /* i 为下面 array 的横标 */case '+' : i=0;break;case '-' : i=1;break;case '*' : i=2;break;case '/' : i=3;break;case &#

22、39;(' : i=4;break;case ')' : i=5;break;case '#' : i=6;break;switch(c2)/* j 为下面 array 的纵标 */case '+' : j=0;break;case '-' : j=1;break;case '*' : j=2;break;case '/' : j=3;break;case '(' : j=4;break;case ')' : j=5;break;case '#'

23、; : j=6;break;返回运算符 */return (array7*i+j); /*/* 操作函数 */int Operate(int a,char op,int b) switch(op) case '+' : return (a+b);case '-' : return (a-b);case '*' : return (a*b);case '/' : return (a/b);return 0;int num(int n)/返回操作数的长度char p10;itoa(n,p,10);/ 把整型转换成字符串型 n=strl

24、en(p);return n;int EvalExpr()/ 主要操作函数char c,theta,x; int n,m;int a,b;c = *ptr+; while(c!='#'|GetTop(OPTR)!='#') if(!In(c) if(!In(*(ptr-1) ptr=ptr-1;m=atoi(ptr);/ 取字符串前面的数字段 n=num(m);Push2(&OPND,m);ptr=ptr+n;c=*ptr+;elseswitch(Precede(GetTop(OPTR),c)case '<': /栈顶元素优先权低Push(&OPTR,c);c = *ptr+;break;case '=': /脱括号并接收下一字符x=Pop(&OPTR);c = *ptr+;break;case '>': /退栈并将运算结果入栈theta=Pop(&OPTR);