[理学]表达式求解迷宫求解.doc

课 程 设 计 报 告课程名称 数据结构 课题名称 表达式求解 迷宫求解 专 业 信息与计算科学 班 级 学 号 姓 名 指导教师 年 月 日湖南工程学院课 程 设 计 任 务 书课程名称 数据结构 课 题 表达式求值 迷宫求解 专业班级 学生姓名 学 号 指导老师 审 批 任务书下达日期 2009 年 5 月 15 日任务完成日期 年 月 日一、设计内容与设计要求课题1表达式求值问题描述：设计一编译器，对读入的表达式能根据人们的约定予以正确解释，并计算结果。设计要求：（1）表达式中应包含数值常量、四则运算符、括号等。 （2）对不合理的解释应有反应。设计提示：（1）可用两个栈（操作数栈及运算符栈）来存储原始数据及中间结果。（2）对表达式进行语法检查。（3）用一一维数组约定运算符的位置，用一二维数组存放运算符间的优先关系。测试数据：3+a*9 2+(1*(7-8)*5 7*(5+6-4*2/(2*7)+9/4-5课题4 迷宫问题问题描述：用计算机模拟解决“迷宫问题”，求出其中一条通道。用数组MAZE1.M,1.N表示迷宫，有的可以通行（0表示），有的是路障（1表示），MAZE11为迷宫入口,MAZEMN为迷宫出口,用非递归算法求出一条通路。设计要求：用“”标示所输出的路径(见运行示例)否则说明没有通路,继续生成迷宫,直到有通路。 算法提示：实现这一算法的具体方法很多（如堆栈,队列等）,但基本思想一般是回溯法使用MAZEMN表示迷宫（如图），为判定过程中是否越界，在其外围加一圈作为路障，markMN作为标志数组，move82是行列增量数组（见图）；建堆栈约定（i,j）表示I行j列,direction 表示方向, 从入囗开始探索路径：沿八个方向依次试探，若某方向可通（为），则该点连同方向入堆栈，从该点继续试探；若八个方向都不通，则取出堆栈顶点，从其标记的方向开始试探其余方向；直至找到出口（有通路）或堆栈为空(没有通路). 下面是利用一随机函数生成的0/1方阵及运行示例:二、进度安排日 期上午下午15周星期一课题讲解 明确任务查资料15周星期二上机调试上机调试15周星期三上机调试上机调试16周星期二上机调试上机调试16周星期五上机调试及答辩答辩目录1 表达式求值 1.1问题分析1.2算法描述1.3运行结果1.4设计体会2 迷宫求解 2.1问题分析 2.2算法描述 2.3运行结果 2.4设计体会 1表达式求值1.1问题分析 设计一个编译器，能对一个含有数值常量，四则运算符，括号的表达式根据人们给予约定计算正确的结果，并且对于不合理的表达式有所反应。关于表达式求值，输入的数据用栈这一数据结构储存，建立一个数据栈（OPND），用来存储表达式中的数据；一个运算符栈（OPTR），用来存储表达式中的四则运算符；用一个二维数组约定运算符之间的优先级别。通过对两个栈进行元素的进栈与出栈以及中间结果的计算，得到输入表达式的值。1.2算法描述表达式求值是栈应用的一个典型列子，我采用的是一种简单直观、广为使用的算法，通常称为“算符优先法”。任何一个表达式都是由操作数、运算符和界限符组成的，其中操作数是是用户从键盘终端输入的整型变量，运算符为+、-，*，/，界限符有左右括号和表达式结束符。在本程序中，我把运算符和界限符统称为算符，他们构成的集合命名为OP。根据三条运算法则：（1）先乘除，后加减；（2）从左算到右；（3）先括号内，后括号外；在运算的每一步，任意两个相继出现的算符1和2之间的优先关系至多是下面三种关系之一： 1<2 1的优先权低于2 1>2 2的优先权高于2 1=2 1的优先权等于2表A定义了算符之间的这种优先关系： （表A）12+ - * / （ ） # + > > < < < > > - > > < <<  > > * > > > > < < < / > > > > < < < （ < < < < < = ） > > > >  > > # < < < <<  =为了实现算符优先算法，可以使用两个工作栈。一个称做OPTR，用以寄存运算符；另一个称做OPND，用以寄存 操作数和运算结果。算法的基本思想是：（1）    首先置操作数栈为空栈，表达式起始符“#”为运算符栈的栈底元素；（2）    一次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符比较优先权后作相应操作，直至整个表达式求值完毕（即OPTR 栈为空）以下的这个算法描述了这个过程： OperandType EvaluateExpression() /算术表达式求值的算符优先算法。设OPTR和OPND分别为运算符栈和运算数栈/ OP为运算符集合InitStack(OPTR); Push(OPTR,#)；InitStack(OPND);c=getchar():do if(!In(c,OP) Push(OPND,c);c=getchar;/不是运算符则进栈else switch(Precede（GetTop(OPTR),c） case<:/栈顶元素优先权低 Push(OPTR,c);c=getchar(); Break; Case=:/脱括号并接收下一字符 Pop(OPTR,x); c=getchar(); Break; Case>:/退栈并将运算结果入栈 Pop(OPTR,theta); Pop(OPND,b);Pop(OPND,a); Push(OPND,Operate(a,theta,b); Break;/switchwhile(!OPTR);Return GetTop(OPND);/EvaluateExpression  算法中调用了两个函数，其中Precede是判定运算符栈栈顶的元素1与读入的2之间优先关系的函数；Operate为进行二元运算a b的函数，如果是编译表达式，则产生这个运算的一组相应指令并返回存放结果的中间变量名；如果是解释执行表达式，则直接进行运算，并返回运算的结果。流程图 Main函数流程图： 开始NY YNY输入一个表达式，存在数组cN中建立数据栈（OPND）运算符栈（OPTR）将字符压入栈OPTR中ci为或者OPTR的栈顶元素为i0ci为运算符Ci入栈i+OPTR的栈顶元素与ci优先级比较<：ci入栈 i+,break=：脱括号 i+;break>：计算中间结果 break输出结果判断OPTR是否为空Ni+结束子函数 Operate(char a,char b,char c)int a1=a-0int c1=c-0将字符型的数字转化为整型Switch(b)case +:result=a1+c1case -: result=a1-c1case *: result=a1*c1case /: result=a1/c1将计算结果转化为字符型，作为返回值开始结束取两个运算数a,c;取一个四则运算符b子函数 Precede(char a,char b)开始结束用变量i，j 分别找到字符a，b的下标用一维数aa7组约定字符的位置用二维数组bb77约定两字符的优先级别把bbij作为字符型的返回值得到需要优先级比较的字符a,b1.3运行结果在tc中输入代码中，不断的编译调试，不断的发现问题，然后再找解决的办法。我在调试中主要遇到的问题如下：1) 在刚看到课题的时候，不知道应该如何用一个二维数组约定运算符间的优先级别，于是，翻阅了教科书，也试图从图书馆中找到相应的资料，但是，失败了，后来，在看书的时候，教科书中的表格，让我突然的明白过来，于是，在上机的时候，用一维数组约定非运算数的位置，利用相应的下标在二维数组中得到优先级别，并把它作为子函数Precede（char a,char b）的返回值。调试的时候，当我输入+，*时，得到了预期中的结果<。2) 在一个一个子函数的代码编写中，当我遇到要计算中间结果的时候，不知道怎样把从字符型栈中出栈的字符型的运算数，转换为相应的整型，进而进行四则运算。向老师请教，老师说是字符型的字符减去一个0，就可以转换成数字了，比如说 char a=3,做相应的处理：a1=a-0；就得到了数字3。还有，怎样把字符型的运算能，能进行运算呢，通过和同学的讨论，可以选用switch 语句，根据运算的类型，做相应的代数运算，并把得到的结果返回。比如说，我要计算的是 3+2；先a1=3-0=3;c1=2-0=2；b=+；result=3+2=5。又解决了一个问题。后来在与同学互相交流的时候，他们还告诉我一个方法，强制转换成int 型再加上48就可以得到相应的整型值了。3) 经过一段时间的努力后，程序代码总算是完成了，编译后没有错误，没有警告，但是就是得不到正确的计算结果，可以运行，但是进入了死循环，经过一步步的调试，发现了问题是出在元素进栈的时候，运行结果总是打印“”The stack is full”,后来，知道了在main函数中的一个循环中应该把break该成continue，该了之后，再运行，可以得到一个结果了，但是不是正确的结果，而且无论我输入的表达式是怎样的，都得到结果49。后来，还是找了同学帮忙，他发现了我逻辑上的一个错误，在我的while循环中，我的第一个运算符不会入栈，所以中间结果没有计算，直接就结束了，而把while语句改成dowhile的时候，就可以把第一个运算符入栈了。4) 问题是一个接一个的解决了，但是，我的编译器还是没成功，后来，意识到了一个问题，那就是，我原先是用一个一维数组接收的求值表达式，如果我输入的是一个2位数的数字，它就会成为2个字符储存，出栈的时候，就会发生错误，导致得不到正确的结果。可，我输入的是一位数的表达式时，很遗憾，还是出错了。已经自己发现不了错误，于是，去找老师请教，老师很耐心的给我的程序一步步的测试，一会之后，就发现了问题的所在，我的Operate的函数的返回值是int型的，然而，入栈的时候我直接用了Push（OPND，Operate（m，theta，n），把一个int型的数据放进了一个字符型的栈，从而导致了其他的逻辑错误，应改成Push（OPND，Operate（m，theta，n）+0）；同时，在最后得到的表达式的计算结果时，也应将字符型的改回int型，即:printf(“nthe result is:%d”,GetTop(OPND)-0)。做了这样了修改之后，程序终于能成功运行出正确的结果了。测试了一下8-2*（7-6）, 运行结果是 the result is:6 。1.4设计体会通过一星期的努力，终于把课题“表达式求值”完成了，虽然做出来的编译器之能进行一位数的四则运算，但是，我自己已经很高兴了。这一星期的学习，我颇有感触体会：(一) 因为知识的需要，报课本细致的看了一些，重新温习了书本，对于之前的学习起了很大的补充作用，也对原有的知识进行了巩固。(二) 一个大的收获应该是学以致用吧。把所学的知识用到了实处，不再是停留在理论的程度上，把所学进行组合，然后实实在在的做出了一点东西，有了信心，也有了小小的成就感，同时也产生了学习的兴趣与乐趣。(三) 在和同学老师的交流中学会了很多，认识到了自己的差距与不足，从优秀的同学那里学到了很多的知识，也看了他们学习的认真和效果，从老师那里再一次深刻的体会到了学海无涯，我们还有很多的东西尚需虚心学习。我要继续努力，好好学习，天天向上。(四) 一段时间的学习，发现了学好一样东西并不难，只要有恒心，有坚持，有学习的情绪，或许，这并不是我最新的体会，可是，这次的学习，有体会到了它的真实性，好好的学，即便是理论上的东西，现在可能我们用不上，但，对于以后，谁能够下定论呢，时间摆在我的眼前，与其虚度光影不如好好的学，不至于以后落得个数到用时方恨少。(五) 做表达式求值这个课题，应该就算是做一个简单的计算器吧，以前用计算器的时候，总觉得很神奇，轻轻一按，就可以得到计算结果，现在明白了一些原理，也对当前的科技对了几分的敬佩。同时，也知道了有些东西，其实我们自己也可以做到，只是我们目前的知识有限。应该说，这次的程序设计，激发了我对学习的部分热情吧，对我所不知的世界、领域产生了想去探究的想法。(六) 通过这段时间的共同学习，和同学们之间的友情加深了。一起谈论学习，共同探讨问题的答案，互相帮助，欢声笑语也夹杂其中，很高兴，能有愉快的学习氛围。 完成了课程设计表达式求值，我觉得我的收获真的很大，总结之后，更是发现了自己学会了很多，得到了很多，无论是学习还是思想上的一些东西。 2迷宫求解2.1问题分析三、报告要求1 课程设计说明书装订顺序：封面、任务书、目录、正文、评分、附件（A4大小的图纸及程序清单）。 2 每课题应包含：问题分析、算法描述、运行结果、设计体会等。正文 宋体5号 一附录1 表达式求值# include<stdio.h># include<malloc.h># define N 100# define TRUE 1# define FALSE 0typedef structchar stackN;int top; SeqStack;SeqStack *InitStack()SeqStack *s;s=malloc(sizeof(SeqStack);if(!s)printf("do not have enoughf space");return NULL; else s->top=-1;return s;char GetTop(SeqStack *s)if(s->top=-1)printf("nthis is a empty stack!");return FALSE;else return (s->stacks->top);SeqStack *Push(SeqStack *s,char x)if(s->top=N-1)printf("n the stack is full!");return NULL;else s->top+;s->stacks->top=x;return s;char Pop(SeqStack *s)if(s->top=-1)printf("nThe sequence stack is empty!");return FALSE; (s->top)-;return (s->stacks->top+1);int StackEmpty(SeqStack *s)if(s->top=-1) return TRUE;else return FALSE;int match(char *c)int i=0;SeqStack *s;s=InitStack();while(ci!='#')switch(ci)case '(':Push(s,ci);break;case ')':if(!StackEmpty(s)&&GetTop(s)='(') Pop(s);break; /* end if */ else return FALSE; /* end switch */i+; /* end while */return (StackEmpty(s);char Precede(char a,char b)int i,j;char aa7='+','-','*','/','(',')','#'char bb77='>','>','<','<','<','>','>','>','>','<','<','<','>','>', '>','>','>','>','<','>','>','>','>','>','>','<','>','>', '<','<','<','<','<','=','','>','>','>','>','','>','>', '<','<','<','<','<','','='for(i=0;i<7;i+)if(a=aai) break;for(j=0;j<7;j+)if(b=aaj) break;return bbij;int YSF(char y)if(y='+'|y='-'|y='*'|y='/'|y='('|y=')')return TRUE;else return FALSE;int Operate(char a,char b,char c)int a1,c1,result;a1=a-'0'c1=c-'0'switch(b)case '+':result=a1+c1;break;case '-':result=a1-c1;break;case '*':result=a1*c1;break;case '/':result=a1/c1;break;return result;void main()char cN;int i,j;char m,n,theta;SeqStack *OPTR; /* yunsanfu */SeqStack *OPND; /* yunsanshu */OPTR=InitStack();Push(OPTR,'#');OPND=InitStack();i=0;do ci=getchar();i+;while(ci-1!='#');printf("nthe equation you input is below:n");for(j=0;j<i;j+)printf("%c",cj);printf("n");getchar();printf("the equation is:n") ;for(j=0;j<i-1;j+)printf("%c",cj);printf("n");getchar();i=0;do if(!YSF(ci)&&ci!='#') Push(OPND,ci); i+; else switch(Precede(GetTop(OPTR),ci) case '<':Push(OPTR,ci);i+;break; case '=':Pop(OPTR);i+;break; case '>': theta=Pop(OPTR); n=Pop(OPND); m=Pop(OPND); Push(OPND,Operate(m,theta,n)+'0'); break; /* end swtich */ while(ci!='#'|GetTop(OPTR)!='#'); /*end while */printf("the result of the equation is: %d", GetTop(OPND)-'0'); getchar(); /* end main() */2迷宫求解：#include<stdio.h>#include<stdlib.h>/* 数据定义*/typedef enum ERROR, OK Status;typedef struct int row; /row表示“行”号int line; /line表示“列”号PosType; /位置的元素类型typedef struct int ord; /该通道在路径上的“序号” PosType seat; /通道块在迷宫中的“坐标位置”int di; /从此通道走向下以通道块的“方向”SElemType; /栈的元素类型typedef structSElemType * base;SElemType * top;int stacksize;SqStack;/* 函数原型说明*/Status InitStack(SqStack &S); /创建一个空栈SStatus Push(SqStack &S,SElemType &a); /插入新元素aStatus Pop(SqStack &S,SElemType &a); /删除栈顶元素，a返回其值Status StackEmpty(SqStack S); /检查是否空栈Status MazePath(int maze1212,SqStack &S, PosType start, PosType end); /找通路void Initmaze(int maze1212,int size); /初始化迷宫void printmaze(int maze1212,int size); /显示迷宫Status Pass(int maze1212,PosType CurPos); /判断当前位置是否可通void Markfoot(int maze1212, PosType CurPos); /标记当前位置不可通PosType NextPos(PosType CurPos, int Dir); /进入下一位置void printpath(int maze1212,SqStack S,int size); /显示通路/* 主函数*/void main (void) SqStack S;int size,maze1212; for(int n=0;n<10;n+) printf("创建一个正方形迷宫，请输入迷宫尺寸(注意不要大于10):n"); /设置迷宫大小 scanf("%d",&size);if(size<1 | size>10)printf("输入错误!");return; Initmaze(maze,size); /初始化迷宫 printmaze(maze,size); /显示所创建的迷宫 PosType start,end; /设置入口和出口 printf("输入入口行坐标和列坐标:");scanf("%d",&start.row);scanf("%d",&start.line); printf("输入出口行坐标和列坐标:");scanf("%d",&end.row);scanf("%d",&end.line); if(MazePath(maze,S,start,end) /若有通路，显示通路 printpath(maze,S,size); else printf("找不到通路!nn");/*若迷宫maze中从入口 start到出口 end的通道，则求得一条存放在栈中 */Status MazePath(int maze1212,SqStack &S, PosType start, PosType end) PosType curpos;int curstep;SElemType e;InitStack(S);curpos = start; / 设定"当前位置"为"入口位置curstep = 1; / 探索第一步do if (Pass(maze,curpos) / 当前位置可通过，即是未曾走到过的通道块 Markfoot(maze,curpos); / 留下足迹 e.di =1; e.ord = curstep; e.seat= curpos; Push(S,e); / 加入路径 if (curpos.row=end.row && curpos.line=end.line) return OK; / 到达终点（出口） curpos = NextPos(curpos, 1); / 下一位置是当前位置的东邻 curstep+; / 探索下一步 else / 当前位置不能通过 if (!StackEmpty(S) Pop(S,e); while (e.di=8 && !StackEmpty(S) Markfoot(maze,e.seat); / 留下不能通过的标记，并退回一步 Pop(S,e); if (e.di<8) e.di+; / 换下一个方向探索 Push(S, e); curpos = NextPos(e.seat, e.di); / 当前位置设为新方向的相邻块 while (!StackEmpty(S);return ERROR; /* 初始化迷宫*/void Initmaze(int maze1212,int size) for(int i=0;i<size+2;i+)maze0i=1; for( i=1;i<size+1;i+) mazei0=1; for(int j=1;j<size+1;j+) mazeij=rand()%2; mazeisize+1=1; for(i=0;i<size+2;i+)mazesize+1i=1; /* 显示迷宫*/void printmaze(int maze1212,int size)printf("nn");printf("显示所建的迷宫(#表示外面的墙):n"); for(int i=0;i<size+2;i+)printf("%c ",'#');printf("n");for(i=1;i<size+1;i+) printf("%c "