数据结构实验报告表达式求值、任务调度

1、实验报告二实验课名称：数据结构与程序设计实验实验名称：表达式求值、任务调度班级 学号 姓名 时间一、问题描述1. 表达式求值问题表达式是数据运算的基本形式。人们的书写习惯是中缀式， 如：11+22*(7-4)/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：22 7 4 - * 3 / 11 +）和前缀式（如：+11 / * 22 7 4 3）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2. 任务调度多用户多任务操作系统中，多个任务同

2、时共享计算机系统资源。为了使多个任务均能够顺利执行，操作系统要按一定的原则对它们进行调度，使它们按一定的次序进行。设只有一个CPU，现有多个任务，它们需要CPU 服务的时间已知。在下列假设下，按平均等待时间最短为原则，设计算法求出任务的执行顺序。忽略任务提交的时间差，即认为各任务同时提交。各任务不同时提交。二、数据结构设计1. 表达式求值：通过算符优先算法来进行表达式求值，为实现算符优先算法，可以使用两个工作栈，一个称为OPTR，用以寄存运算符；另一个称为OPND，用以寄存操作数或运算结果。声明操作数栈：typedef struct NumStack / number stack 

3、  int *base;    int *top;    int stacksize; NumStack;声明运算符栈：typedef struct SymStack / symbol stack    char *base;    char *top;    int stacksize; SymStack;2. 任务调度：用结构体存储每个任务的任务顺序，需要时间，提交时间，开始时间，等待时间，结束时间struct taskint order, need, t,start,wait,e

4、nd; T100;三、算法设计1.表达式求值：Precede函数用以比较运算符的优先级，返回>，= 或 <。char Precede(char a,char b) int i,j; char Table99= ' ','+','-','*','/','%','(',')','#', '+','>','>','<','<','<

5、;','<','>','>', '-','>','>','<','<','<','<','>','>', '*','>','>','>','>','>','<','>

6、9;,'>', '/','>','>','>','>','>','<','>','>', '%','>','>','>','>','>','<','>','>', '(',

7、9;<','<','<','<','<','<','=',' ', ')','>','>','>','>','>',' ','>','>', '#','<','<','<',&

8、#39;<','<','<',' ','=', ; /优先级表格 for(i=0;i<9;i+) if(Table0i=a) /纵坐标寻找 break; for(j=0;j<9;j+) /横坐标寻找 if(Tablej0=b) break; return Tableji; / b Table a/Precedeoperate函数传入操作数a, b, 和操作符theta, 计算操作结果并返回。int Operate(int a,char theta,int b) /计算表达式值：主要是将大的表达

9、式 /转化成小的表达式进行逐步求值 int c; if(theta='+') c=a+b; else if(theta='-') c=a-b; else if(theta='*') c=a*b; else if(theta='%') c=a%b; else c=a/b; return c;/OperatereadNum函数将字符型数字转换为int型。int ReadNum(char s) /将字符型的数字转化成int型 if(s>=49&&s<=57) /数字的ASCII码所在范围 /这儿决定了本程序只

10、能计算一位数的四则运算 s-=48; return s; else return 0;/ReadNum求值函数result, 其基本求值过程为：1. 首先至操作数栈为空栈，表达式起始符#为运算符的栈底元素；2. 依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符进行比较优先权后做相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为#）int result(char *a,NumStack *OPND,SymStack *OPTR) /求值 char theta; int b,c,i=0; IntInitStack(OPND); C

11、harInitStack(OPTR); CharPush(OPTR,'#'); while(1) if(ReadNum(ai) IntPush(OPND,ReadNum(ai+); else if(ai='+'|ai='-'|ai='*'|ai='/'|ai='%'|ai='#'|ai='('|ai=')') switch(Precede(ai,CharGetTop(OPTR) case '<':CharPush(OPTR,ai+

12、);break; case '=':CharPop(OPTR);i+;break; case '>':theta=CharPop(OPTR); /栈顶元素优先权高 c=IntPop(OPND); b=IntPop(OPND); IntPush(OPND,Operate(b,theta,c); break; /switch /else if if(ai='#'&&CharGetTop(OPTR)='#') printf("The result is %d.n",IntGetTop(OPND)

13、; /打印输出表达式值 return OK; /while/result将中缀表达式转换为前缀表达式：1）求输入串的逆序。2）检查输入的下一元素。3）假如是操作数，把它添加到输出串中。4）假如是闭括号，将它压栈。5）假如是运算符，则i)假如栈空，此运算符入栈。ii)假如栈顶是闭括号，此运算符入栈。iii)假如它的优先级高于或等于栈顶运算符，此运算符入栈。iv)否则，栈顶运算符出栈并添加到输出串中，重复步骤5。6）假如是开括号，栈中运算符逐个出栈并输出，直到遇到闭括号。闭括号出栈并丢弃。7）假如输入还未完毕，跳转到步骤2。8）假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。9）求输出串的逆

14、序。char perfix(char *a) /此函数将中缀表达式转换为后缀表达式 char ch, b100; int j=0; SymStack r, *R; R = &r; CharInitStack(R); /CharPush(R,'#'); int i = strlen(a)-2; ch=ai; while(i>=0) if(ch>=49&&ch<=57) ch-=48; bj+=ch; if(ch=')') CharPush(R,ch); while(ch='+'|ch='-'

15、|ch='*'|ch='/'|ch='%') if(*R).top=(*R).base|CharGetTop(R) = ')'|Precede(ch,CharGetTop(R)='<') CharPush(R,ch); break; else bj+=CharPop(R); if(ch='(') while(CharGetTop(R)!=')') bj+=CharPop(R); CharPop(R); ch=a-i; /while while(*R).top != (*R).b

16、ase) bj+=CharPop(R); bj = '0' printf("The changed pre expression is: "); int t=strlen(b)-1; for(t;t>=0;t-) /打印输出前缀表达式 if(bt>=1&&bt<=9) printf("%d",bt); else printf("%c",bt); /for printf(".n"); return OK;/prefix将中缀表达式转换为后缀表达式：算法描述：将中缀表达

17、式转换为等价的后缀表达式的过程要使用一个栈放“（”，具体可以按照下面的方式进行。1）从左到右一次扫描中缀表达式的每一个字符，如果是数字字符和圆点“.”则直接将它们写入后缀表达式中。2）如果遇到的是开括号“（”，则将它们压入一个操作符栈（不需要与栈顶操作符相比较），它表明一个新的计算层次的开始，在遇到和它匹配的闭括号“）”时，将栈中的元素弹出来并放入后缀表达式中，直到栈顶元素为“(”时，将栈顶元素“（”弹出（不需要加入后缀表达式），表明这一层括号内的操作处理完毕。3）如果遇到的是操作符，则将该操作符和操作符栈顶元素比较： i)当所遇到的操作符的优先级小于或等于栈顶元素的优先级时，则取 出栈顶元素

18、放入后缀表达式，并弹出该栈顶元素，反复执行直到栈顶元素的优 先级小于当前操作符的优先级（或遇到（）； ii)当所遇到的操作符的优先级大于栈顶元素的优先级的时则将它压入 栈中。4）重复上述步骤直到遇到中缀表达式的结束符标记“#”，弹出栈中的所有元素并放入后缀表达式中，转换结束char postfix(char *a) /此函数将中缀表达式转换为后缀表达式 char ch, b100; int i=0, j=0; SymStack r, *R; R = &r; CharInitStack(R); CharPush(R,'#'); ch=ai; while(ch!='

19、#') if(ch>=49&&ch<=57) ch-=48; bj+=ch; ch=a+i; else if(ch='(') CharPush(R,ch); ch=a+i; else if(ch=')') if(CharGetTop(R)!='(') bj+=CharPop(R); else CharPop(R); ch=a+i; else if(ch='+'|ch='-'|ch='*'|ch='/'|ch='%') if(Prec

20、ede(ch,CharGetTop(R)='<') / if Top(R) < ch CharPush(R,ch); ch=a+i; else bj+=CharPop(R); /while ch=CharPop(R); while(ch!='#') bj=ch; j+; ch=CharPop(R); bj='#' printf("The changed expression is: "); for(i=0;bi!='#'i+) /打印输出后缀表达式 if(bi>=1&&bi&l

21、t;=9) printf("%d",bi); else printf("%c",bi); /for printf(".n"); return OK;/postfix2任务调度：(1). 同时提交获取每个任务所需的时间，输出按顺序执行时每个任务的序号，开始时间，等待时间和结束时间；按所需时间从小到大排序后，依次执行即为最短等待时间。int cmp(const void *a,const void *b) /相同时间排序, 从小到大return (*(struct task *)a).need-(*(struct task *)b).ne

22、ed;void sametime(int n)double sum,sum2;int i;for(i=0;i<n;i+)/输入任务信息 printf("请输入第%d个任务所需要的时间: ",i+1);Ti.t=0;scanf("%d",&Ti.need);Ti.order=i+1;t=0;sum=0; printf("顺序执行:n");printf("序号 开始时间 等待时间 结束时间n");for(i=0;i<n;i+)/顺序执行任务，输出执行信息 printf("%-7d"

23、;,i+1);printf("%-7d",t);printf("%-8d",t);t+=Ti.need;printf("%-8d",t);printf("n");sum+=(n-i-1)*Ti.need);printf("n"); printf("平均时间最短:n");printf("序号 开始时间 等待时间 结束时间n");qsort(T, n, sizeof(T0), cmp);/按最短时间排序 t=0;sum2=0;for(i=0;i<n;i+

24、)/排序后输出任务执行信息 printf("%-7d",Ti.order);printf("%-7d",t);printf("%-8d",t);t+=Ti.need;printf("%-8dn",t);printf("n");sum2+=(n-i-1)*Ti.need);printf("顺序执行等待平均时间为 %.3lfn",sum/n);printf("最短等待平均时间为 %.3lfn",sum2/n);(2). 不同时间提交int comp(const

25、 void *a,const void *b)/不同时间排序 return T*(int *)a.need>T*(int *)b.need;void dele()int i;printf("%-10d%-10d%-10d%-20dnn",Tque0.order,Tque0.start,Tque0.wait,Tque0.end);for(i=0;i<rear-1;i+)quei=quei+1;rear-;int check(int num1)int i;Tque0.need-;if(Tque0.need<=0)Tque0.end=t;dele();for(i

26、=0;i<rear;i+)Tquei.wait+;return 1;elsefor(i=1;i<rear;i+)Tquei.wait+;return 0;/时间段移动查寻当前队列 void insert(int n)int i,rec;for(i=0;i<rear;i+)if(Tquei.need>Tn.need)break;rec=i;for(i=rear;i>rec;i-)quei=quei-1;querec=n; rear+;void difftime(int n)/输入本来按照先后顺序 int tdiff;double sum;int i,j;rear=0

27、;sum=0;for(i=0;i<n;i+)/输入每个任务信息 printf("请输入第%d个任务提交时刻和执行时间n",i+1,i+1); printf("提交时刻: "); scanf("%d",&Ti.t); printf("执行时间: "); scanf("%d",&Ti.need);Ti.order=i+1;Ti.start=-1;Ti.end=-1;Ti.wait=0;printf("序号 开始时间 等待时间 结束n");que0=0;rea

28、r=1;T0.start=0;i=0;t=0;j=1;while(i<n)t+;/时间移动 i+=check(tdiff);/时间移动后检查是否有完成的任务，并且就算等待时间 if(t>=Tj.t&&j<n)/假入在当前任务执行时间内有任务提交 insert(j); /把任务插入到队列 j+;qsort(que, rear, sizeof(que0), comp);/按时间长短排序 if(Tque0.start=-1)/给队列最前点赋起始值 Tque0.start=t;for(i=0;i<n;i+)/计算出所有等待时间 sum+=Ti.wait;prin

29、tf("平均等待时间为 %.3lfsnn",sum/n);四、界面设计1.表达式求值需要输入以#结尾的中缀表达式，以提示语句的方式给出。输出注明是什么结果。2.任务调度需要输入任务数，任务需要执行时间，（不同时需要任务提交时间），按平均等待时间最短为原则，输出出任务的执行顺序。五、运行测试与分析1.表达式求值1).输入一个以#结尾的中缀表达式：2).输出计算结果，后缀表达式以及前缀表达式：3.任务调度：(1). 同时提交i).输入:ii).输出:(2). 不同时间提交i).输入:ii).输出:六、实验收获与思考1熟练掌握栈的定义及使用。2了解表达式求值的转换算法。设计前、后

30、缀表达式求值算法。3设计操作数为多位实数，操作符为加、减、乘、除、求模的中缀表达式求值算法。定义算数符号的优先级。4. 从理论到实践，巩固了学过的知识。七、附录（原程序）1.表达式求值#include<stdio.h> #include<stdlib.h> #include<string.h>#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define ERROR 0#define OK 1typedef struct NumStack / number stack int *base; int *t

31、op; int stacksize;NumStack;typedef struct SymStack / symbol stack char *base; char *top; int stacksize;SymStack;void IntInitStack(NumStack *S) S->base=(int *)malloc(STACK_INIT_SIZE*sizeof(int); if(!S->base) exit(ERROR); S->top=S->base; S->stacksize=STACK_INIT_SIZE;/IntInitStackvoid Ch

32、arInitStack(SymStack *S) S->base=(char *)malloc(STACK_INIT_SIZE*sizeof(char); if(!S->base) exit(ERROR); S->top=S->base; S->stacksize=STACK_INIT_SIZE;/CharInitStackint IntGetTop(NumStack *S) /取栈顶元素 int e; if(*S).top=(*S).base) return 0; e=*(*S).top-1); return e;/IntGetTopchar CharGetTo

33、p(SymStack *S) /取栈顶元素 char e; if(*S).top=(*S).base) return 0; e=*(*S).top-1); return e;/IntGetTopint IntPush(NumStack *S,int e) *(*S).top+=e; return OK;/IntPushint CharPush(SymStack *S,char e) *(*S).top+=e; return OK;/CharPushint IntPop(NumStack *S) int e; if(*S).top=(*S).base) return 0; e=*-(*S).to

34、p; return e;/IntPopint CharPop(SymStack *S) char e; if(*S).top=(*S).base) return 0; e=*-(*S).top; return e;/CharPopchar Precede(char a,char b) int i,j; char Table99= ' ','+','-','*','/','%','(',')','#', '+','>'

35、;,'>','<','<','<','<','>','>', '-','>','>','<','<','<','<','>','>', '*','>','>','>',&#

36、39;>','>','<','>','>', '/','>','>','>','>','>','<','>','>', '%','>','>','>','>','>','&

37、lt;','>','>', '(','<','<','<','<','<','<','=',' ', ')','>','>','>','>','>',' ','>','>', 

38、9;#','<','<','<','<','<','<',' ','=', ; /优先级表格 for(i=0;i<9;i+) if(Table0i=a) /纵坐标寻找 break; for(j=0;j<9;j+) /横坐标寻找 if(Tablej0=b) break; return Tableji; / b Table a/Precedeint Operate(int a,char theta,int b) /计

39、算表达式值：主要是将大的表达式 /转化成小的表达式进行逐步求值 int c; if(theta='+') c=a+b; else if(theta='-') c=a-b; else if(theta='*') c=a*b; else if(theta='%') c=a%b; else c=a/b; return c;/Operateint ReadNum(char s) /将字符型的数字转化成int型 if(s>=49&&s<=57) /数字的ASCII码所在范围 /这儿决定了本程序只能计算一位数的四则

40、运算 s-=48; return s; else return 0;/ReadNumint result(char *a,NumStack *OPND,SymStack *OPTR) /求值 char theta; int b,c,i=0; IntInitStack(OPND); CharInitStack(OPTR); CharPush(OPTR,'#'); while(1) if(ReadNum(ai) IntPush(OPND,ReadNum(ai+); else if(ai='+'|ai='-'|ai='*'|ai=

41、9;/'|ai='%'|ai='#'|ai='('|ai=')') switch(Precede(ai,CharGetTop(OPTR) case '<':CharPush(OPTR,ai+);break; case '=':CharPop(OPTR);i+;break; case '>':theta=CharPop(OPTR); /栈顶元素优先权高 c=IntPop(OPND); b=IntPop(OPND); IntPush(OPND,Operate(b,th

42、eta,c); break; /switch /else if if(ai='#'&&CharGetTop(OPTR)='#') printf("表达式的结果是%d.n",IntGetTop(OPND); /打印输出表达式值 return OK; /while/reslutchar postfix(char *a) /此函数将中缀表达式转换为后缀表达式 char ch, b100; int i=0, j=0; SymStack r, *R; R = &r; CharInitStack(R); CharPush(R,&#

43、39;#'); ch=ai; while(ch!='#') if(ch>=49&&ch<=57) ch-=48; bj+=ch; ch=a+i; else if(ch='(') CharPush(R,ch); ch=a+i; else if(ch=')') if(CharGetTop(R)!='(') bj+=CharPop(R); else CharPop(R); ch=a+i; else if(ch='+'|ch='-'|ch='*'|ch=&

44、#39;/'|ch='%') if(Precede(ch,CharGetTop(R)='<') / if Top(R) < ch CharPush(R,ch); ch=a+i; else bj+=CharPop(R); /while ch=CharPop(R); while(ch!='#') bj=ch; j+; ch=CharPop(R); bj='#' printf("它的后缀表达式为: "); for(i=0;bi!='#'i+) /打印输出后缀表达式 if(bi>

45、;=1&&bi<=9) printf("%d",bi); else printf("%c",bi); /for printf(".n"); return OK;/postfixchar perfix(char *a) /此函数将中缀表达式转换为后缀表达式 char ch, b100; int j=0; SymStack r, *R; R = &r; CharInitStack(R); /CharPush(R,'#'); int i = strlen(a)-2; ch=ai; while(i

46、>=0) if(ch>=49&&ch<=57) ch-=48; bj+=ch; if(ch=')') CharPush(R,ch); while(ch='+'|ch='-'|ch='*'|ch='/'|ch='%') if(*R).top=(*R).base|CharGetTop(R) = ')'|Precede(ch,CharGetTop(R)='<') CharPush(R,ch); break; else bj+=Char

47、Pop(R); if(ch='(') while(CharGetTop(R)!=')') bj+=CharPop(R); CharPop(R); ch=a-i; /while while(*R).top != (*R).base) bj+=CharPop(R); bj = '0' printf("它的前缀表达式为: "); int t=strlen(b)-1; for(t;t>=0;t-) /打印输出前缀表达式 if(bt>=1&&bt<=9) printf("%d",bt

48、); else printf("%c",bt); /for printf(".n"); return OK;/perfixvoid main() /主函数，使用自定义函数完成功能 char a100; NumStack s1,*OPND; SymStack s2,*OPTR; OPND=&s1; OPTR=&s2; printf("请输入一个以'#'结尾的中缀表达式.n"); printf("这个表达式:"); scanf("%s",&a); result

49、(a,OPND,OPTR); postfix(a); perfix(a);2.任务调度1)同时提交#include <stdio.h>#include <stdlib.h>#include <string.h>int que100,rear=0,t=0;struct taskint order,need,t,start,wait,end;/任务顺序，需要时间，提交时间，开始时间，等待时间，结束时间 T100;int comp(const void *a,const void *b)/不同时间排序 return T*(int *)a.need>T*(in

50、t *)b.need;void dele()int i;printf("%-10d%-10d%-10d%-20dnn",Tque0.order,Tque0.start,Tque0.wait,Tque0.end);for(i=0;i<rear-1;i+)quei=quei+1;rear-;int check(int num1)int i;Tque0.need-;if(Tque0.need<=0)Tque0.end=t;dele();for(i=0;i<rear;i+)Tquei.wait+;return 1;elsefor(i=1;i<rear;i+)

51、Tquei.wait+;return 0;/时间段移动查寻当前队列 void insert(int n)int i,rec;for(i=0;i<rear;i+)if(Tquei.need>Tn.need)break;rec=i;for(i=rear;i>rec;i-)quei=quei-1;querec=n; rear+;void difftime(int n)/输入本来按照先后顺序 int tdiff;double sum;int i,j;rear=0;sum=0;for(i=0;i<n;i+)/输入每个任务信息 printf("请输入第%d个任务提交时刻和

52、执行时间n",i+1,i+1); printf("提交时刻: "); scanf("%d",&Ti.t); printf("执行时间: "); scanf("%d",&Ti.need);Ti.order=i+1;Ti.start=-1;Ti.end=-1;Ti.wait=0;printf("序号 开始时间 等待时间 结束n");que0=0;rear=1;T0.start=0;i=0;t=0;j=1;while(i<n)t+;/时间移动 i+=check(tdiff);/时间移动后检查是否有完成的任务，并且就算等待时间 if