数据结构 第3章 中缀表达式

1、 数据结构 实验报告 （第三章）实验类型：综合性实验班级： 学号： 姓名： 实验日期：2014年5月24日一、表达式求值1. 问题描述表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*(7-4)/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：22 7 4 - * 3 / 11 +）和前缀式（如：+ 11 / * 22 7 4 3）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。 2.基本要求l 从文件或键盘读入中缀表达

2、式。l 设计操作数为多位整数，操作符为加、减、乘、除、求模的中缀表达式求值算法。l 设计将中缀表达式转换为后缀表达式的算法。l 设计将中缀表达式转换为前缀表达式的算法。l 设计后缀表达式求值算法。l 设计前缀表达式求值算法。l 输出各种形式的表达式。3. 数据结构设计 任何一个表达式都是由操作符，运算符和界限符组成的。我们分别用顺序栈来寄存表达式的操作数和运算符。栈是限定于紧仅在表尾进行插入或删除操作的线性表。顺序栈的存储结构是利用一组连续的存储单元依次存放自栈底到栈顶的数据元素，同时附设指针top指示栈顶元素在顺序栈中的位置，base为栈底指针，在顺序栈中，它始终指向栈底，即top=base

3、可作为栈空的标记，每当插入新的栈顶元素时，指针top增1，删除栈顶元素时，指针top减1。typedef structint *base;int *top;int numstacksize;/数字栈 numstack;typedef structchar *base;char *top;int charstacksize;/字符栈 charstack; 4. 算法设计（1） 中缀表达式求值1.从左到右读入中缀表达式，每次一个字符。2.如果是操作数，压入操作数栈。3.如果是操作符，压入操作符栈。4.如果是左括号，直接忽略。5.如果是有括号，弹出操作符栈栈顶元素，然后弹出操作数栈两个元素，进行操作

4、以后结果压入操作数栈。（2）中缀表达式变后缀表达式1.从左到右读入中缀表达式，每次一个字符。2.如果字符是操作数，直接输出。3.如果是 (，入栈。4.如果是)，则依次把栈中的的运算符加入后缀表达式中，直到出现(，从栈中删除( 。5.若为除括号外的其他运算符， 当其优先级高于除(以外的栈顶运算符时，直接入栈。否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。6.当扫描的中缀表达式结束时，栈中的的所有运算符出栈。（3）中缀表达式变前缀表达式1.从右至左扫描中缀表达式，从右边第一个字符开始判断。2.如果是数字，则分析到数字串的结尾

5、并将数字串直接输出。3.如果是运算符，则比较优先级。如果当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时，直接入栈)，则将运算符直接入栈；否则将栈顶运算符出栈并输出，直到当前运算符的优先级大于等于栈顶运算符的优先级(当栈顶是括号时，直接入栈)，再将当前运算符入栈。4.如果是括号，根据括号的方向处理。如果是右括号，则直接入栈；否则，遇右括号前将所有的运算符全部出栈并输出，遇右括号后将左右的两括号一起删除。5. 重复上述操作2直至扫描结束，将栈内剩余运算符全部出栈并输出。6.再逆序输出字符串。中缀表达式就转换为前缀表达式了。（4）后缀表达式求值1.从左到右读入后缀表达式2.如果字符是一

6、个操作数，把它压入栈。3.如果字符是个操作符，弹出两个操作数，执行恰当操作，然后把结果压入堆栈。4.到后缀表达式末尾，从堆栈中弹出结果。若后缀表达式格式正确，那么堆栈应该为空。（5）前缀表达式求值1.从右至左扫描中缀表达式，从右边第一个字符开始判断，2.如果当前字符是数字，则分析到数字串的结尾并将数字入栈。3.如果是运算符，则将栈中最上面两个数字弹出并进行相应的运算。结果入栈。4.一直扫描到表达式的最左端时，最后栈中的值也就是表达式的值。5.主要操作对数字栈的操作和对字符栈的操作类似，以下只写出对字符栈的操作。/构建一个字符空栈status initstack(charstack &s) s.

7、base=(char *)malloc(stack_init_size*sizeof(char);if(!s.base) exit(-2);/如果地址申请失败，退出s.top=s.base;/栈顶栈尾指向同一位置s.charstacksize=stack_init_size;cout准备完毕，请输入表达式：=s.charstacksize)s.base=(char*)realloc(s.base,(s.charstacksize+stackincrement)*sizeof(char);if(s.base) exit(-2);s.top=s.base+s.charstacksize;s.cha

8、rstacksize+=stackincrement;*s.top+=e;return 1;/出字符站，用e返回 status pop(charstack &s,char &e)if(s.top=s.base) return 0;e=*-s.top;return 1;/出字符站status pop(charstack &s)if(s.top=s.base) return 0;-s.top;return 1; /判断运算符优先级char precede(char a,char b) char youxian99=0,+,-,*,/,(,),%,=, +, -, *, /, (,=, , %, =

9、, ,= ;int i,j;for(j=0;j9;j+)if(youxian0j=b) break;for(i=0;i9;i+)if(youxiani0=a) break;return youxianij;/判断ch是否是运算符int in(char ch)char ptr10=+,-,*,/,(,),%,=;int i;for(i=0;i8;i+)if(ch=ptri) return 1;return 0; /计算二元表达式的值int operate(int aa,char thetaa,int bb)int cc;if(thetaa=/|thetaa=%)&bb=0) cout输入有误!n

10、ext=NULL; return 1; int queuelength(linkqueue Q) / 求队列的长度 int i=0; sqlistptr p; p=Q.front; while(Q.rear!=p) i+; p=p-next; return i; / 若队列不空,则用e返回Q的队头元素,并返回1,否则返回0 int gethead(linkqueue Q,node &e) sqlistptr p; if(Q.front=Q.rear) return 0; p=Q.front-next; e.number=p-number; e.time=p-time; e.tijiao=p-t

11、ijiao; e.wait=p-wait; return 1; / 插入元素e为Q的新的队尾元素 int enqueue(linkqueue &Q,node e) sqlistptr p; if(!(p=(sqlistptr)malloc(sizeof(node) / 存储分配失败 exit(-2); p-number=e.number;/编号 p-time=e.time; /所需时间 p-tijiao=e.tijiao; /提交时间 p-wait=e.wait; /等待时间 p-next=NULL; Q.rear-next=p; Q.rear=p; return 1; / 若队列不空,删除Q

12、的队头元素,用e返回其值,并返回1,否则返回0 int dequeue(linkqueue &Q,node &e) sqlistptr p; if(Q.front=Q.rear) return 0; p=Q.front-next; e.number=p-number; e.time=p-time; e.tijiao=p-tijiao; e.wait=p-wait; Q.front-next=p-next; if(Q.rear=p) Q.rear=Q.front; free(p); return 1; /把time最小的放在首位void sort(linkqueue &l) node *p,*q

13、;int i,j,temp; n=queuelength(l);/任务数量 n p=l.front-next;/p指向第一个任务 for(i=1;inext;/q指向p的下一个任务 if(p-timeq-time) temp=p-number;/交换number p-number=q-number;q-number=temp;temp=p-time;/交换time p-time=q-time;q-time=temp;temp=p-tijiao;/交换tijiao p-tijiao=q-tijiao;q-tijiao=temp;temp=p-wait;/交换wait p-wait=q-wait;

14、q-wait=temp; if(p-next-next=NULL) break;/当p指向倒数第二的结点时，退出p=p-next; /end for循环 /任务不同时提交，按平均等待时间最短执行时的操作过程cout第nn个任务 ; /nn从1递增，用来给任务编号赋值e.number=nn; /第一个任务输入coute.time;e.tijiao=0;e.wait=0;enqueue(l,e); /把新的任务 入队while(1) /时间流逝 ，ss是流逝的时间 pp=l.front-next; /pp是第一个任务 pp-time=(pp-time)-1;/头指针所需时间减一秒 +ss; /时间

15、加一秒 qq=pp; nm=queuelength(l); /任务数量 nmfor(int i=1;inext; qq-wait+; if(pp-time=0)/如果第一个结点所需时间为0，则删除，并入另一个队列k dequeue(l,ee); enqueue(k,ee);nm=queuelength(l);if(nm=0) break;/当l队列为空时，退出 coutendlendl当前时间是：ss 秒endl;/输出当前时间 cout是否有新任务？ 1.是 0.否j;if(j)/输入新的任务 +nn;/任务号 e.number=nn;cout第nn个任务; coute.time;e.tij

16、iao=ss;e.wait=0;enqueue(l,e); /把新的任务 入队 sort(l);/插入新任务后，把time最小的任务放在队首 /while，跳出while后，输出k队列相应信息等到平均等待时间/输出k队列的信息node *qwe;nn=queuelength(k);/队列k的长度 qwe=k.front-next;/pp是k的第一个结点 for(int i=1;i=nn;i+)/依次输出队列k信息 cout任务number的提交时间是：tijiao 等待时间是：wait开始执行时间是：tijiao+qwe-waitwait;if(qwe-next=NULL) break;qwe

17、=qwe-next;cout平均等待时间是：1.0*s/nnendl;/输出平均等待时间 6. 运行、测试与分析1) 运行程序，如图2) 任务同时提交3) 任务不同时提交4) 容错检验实验收获及思考 遇到的问题： 1.无法编译。 2.输出结果不正确。 3.容错机制不正确。 解决办法： 1.通过错误提示，找出了错误所在，一般是因为部分变量拼写错误造成的。 2.在表达式求值问题中，重新梳理算法，检查程序执行过程，按照程序在纸上一步一步模拟运算过程，发现错误之处并且改正。在cpu调度问题中，通过程序分块检查、测试，发现是排序函数出错，通过纸上的一步一步运算，改正了其中的错误。最后输出正确结果。 3.

18、在每个getchar处进行判断，进行多重限制，比如，只允许输入“+ 、-、*、/、%、（、）”和“1、2、3、4、5、6、7、8、9”。实验的收获：第一次编写这么庞大的程序，编写过程中虽然有很多错误，但通过花费大量的时间，不断改正错误，提高了编写、调试较大程序的能力，同时体会到了自己编写的头文件为写程序提供的方便。通过编写不同表达式求值的程序，更熟悉其运算过程，通过测试不同调度方式也切实体会到了好算法的重要性，同时也更熟悉栈和队列的操作。思考：最短作业优先，存在“长任务饥饿”的问题，即如果动态地不断加入作业，只要提交作业所需要的CPU服务时间比较短，则先提交的长任务将一直得不到服务，如何解决该

19、问题？答： 可以在每个任务结点中加一个int型变量shu，用来记录此任务到达cpu后等待的时间，当该任务不执行时，每过1秒就对该任务的shu加1，当该任务执行时，每过1秒对该任务的shu减1，再设定当有任务的shu大于某一值v时，立刻执行此任务，直到小于另一设定值u为止，再检查是否有shu超过特定值v，如有，执行此任务，如没有，按最短作业优先执行。这样就可以解决“长任务饥饿”问题。附录：一、表达式求值/stack.h 表达式求值时用到的栈操作和数据结构 #include#include#include#includeusing namespace std;#define stack_init_

20、size 100#define stackincrement 10typedef int status;typedef struct/数字栈 int *base;int *top;int numstacksize;numstack;typedef struct/字符栈 char *base;char *top;int charstacksize;charstack; /*/栈的操作/构建一个数字空栈 status initstack(numstack &s)s.base=(int *)malloc(stack_init_size*sizeof(int);if(!s.base) exit(-2)

21、;s.top=s.base;s.numstacksize=stack_init_size;coutendl;return 1; /构建一个字符空栈status initstack(charstack &s) s.base=(char *)malloc(stack_init_size*sizeof(char);if(!s.base) exit(-2);s.top=s.base;s.charstacksize=stack_init_size;cout准备完毕，请输入表达式：=s.numstacksize)s.base=(int*)realloc(s.base,(s.numstacksize+sta

22、ckincrement)*sizeof(int);if(s.base) exit(-2);s.top=s.base+s.numstacksize;s.numstacksize+=stackincrement;*s.top+=e;return 1;/字符入字符栈status push(charstack &s,char e)if(s.top-s.base=s.charstacksize)s.base=(char*)realloc(s.base,(s.charstacksize+stackincrement)*sizeof(char);if(s.base) exit(-2);s.top=s.bas

23、e+s.charstacksize;s.charstacksize+=stackincrement;*s.top+=e;return 1;/出数字栈 ，用e返回 status pop(numstack &s,int &e)if(s.top=s.base) return 0;e=*-s.top;return 1;/出字符站，用e返回 status pop(charstack &s,char &e)if(s.top=s.base) return 0;e=*-s.top;return 1;/出数字栈 status pop(numstack &s)if(s.top=s.base) return 0;-

24、s.top;return 1;/出字符站status pop(charstack &s)if(s.top=s.base) return 0;-s.top;return 1; /*/判断运算符优先级char precede(char a,char b) char youxian99=0,+,-,*,/,(,),%,=, +, -, *, /, (,=, , %, =, ,= ;int i,j;for(j=0;j9;j+)if(youxian0j=b) break;for(i=0;i9;i+)if(youxiani0=a) break;return youxianij;/判断ch是否是运算符int

25、 in(char ch)char ptr10=+,-,*,/,(,),%,=;int i;for(i=0;i8;i+)if(ch=ptri)return 1;return 0; /计算二元表达式的值int operate(int aa,char thetaa,int bb)int cc;if(thetaa=/|thetaa=%)&bb=0) cout输入有误!endl;exit(-2); if(thetaa=+)cc=aa+bb;else if(thetaa=-)cc=aa-bb;else if(thetaa=*)cc=aa*bb;else if(thetaa=/) cc=aa/bb;else

26、 cc=aa%bb;return cc; /3.1中缀求值 #include#include#include#includestack.h using namespace std;int main()while(1)cout正在准备，请稍等=0&c=9)|(c=()cout输入有误!=0&c=9)/字符是数字 dd=0; k+; if(kj) num2=num2*10+(c-48); k=j=0; c=getchar();if(!(c=0&c=9)|in(c)=1) cout输入误!endl;exit(-2); if(!in(c) k+; if(k=j) push(opnd,num2);num

27、2=0; else switch(precede(gettop(optr),c) case=0&c=9)|in(c)=1) cout输入有误!=0&c=9)|in(c)=1) cout输入有误!:/退栈并将运算结果入栈 pop(optr,theta); pop(opnd,b); pop(opnd,a); push(opnd,operate(a,theta,b); break;default: cout输入有误!endl; exit(-2); /switch/whilecout结果是：gettop(opnd)endl;return 0;/3.2中缀变后缀 #include #include#in

28、clude#includestack.h using namespace std;int main()cout中缀变后缀 =0&c=9)|(c=()cout输入有误!=0&c=0&c=0&c=9)|in(c)=1) cout输入有误!=0&c=9)|in(c)=1) cout输入有误!=0&c=9)|in(c)=1) cout输入有误!endl;exit(-2);else if(c=+|c=-|c=*|c=/|c=%) if(precede(gettop(optr),c)=0&c=9)|in(c)=1) cout输入有误!)/栈顶优先级大于c while(precede(gettop(optr),c)=) pop(optr,cc); houxuk=cc; k+; push(optr,c); c=getchar();if(!(c=0&c=9)|in(c)=1) cout输入有误!)pop(optr,cc); houxuk=cc; k+; coutendl后缀表达式是：;for(int i=0;ik;i+)couthouxui;break;/whilereturn 0;/3.3中缀变前缀 #include #include#include#includestack.h using namespace std;int main