《数据结构实验报告-表达式求值与任务调度》由会员分享，可在线阅读，更多相关《数据结构实验报告-表达式求值与任务调度（22页珍藏版）》请在金锄头文库上搜索。
1、数据结构与程序设计实验实 验 报 告课程名称数据结构与程序设计实验课程编号0906550实验项目名称表达式求值、任务调度学号年级姓名专业计算机科学与技术学生所在学院计算机学院指导教师杨静实验室名称地点21B276哈尔滨工程大学实验报告二实验课名称：数据结构与程序设计实验实验名称：表达式求值、任务调度班级 学号 姓名时间 2016.04.12一、问题描述1. 表达式求值问题表达式是数据运算的基本形式。人们的书写习惯是中缀式， 如：11+22*(7-4)/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：22 7 4 - * 3 / 11 +）和前缀
2、式（如：+11 / * 22 7 4 3）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2. 任务调度多用户多任务操作系统中，多个任务同时共享计算机系统资源。为了使多个任务均能够顺利执行，操作系统要按一定的原则对它们进行调度，使它们按一定的次序进行。设只有一个CPU，现有多个任务，它们需要CPU 服务的时间已知。在下列假设下，按平均等待时间最短为原则，设计算法求出任务的执行顺序。忽略任务提交的时间差，即认为各任务同时提交。各任务不同时提交。二、数据结构设计1. 表达式求值：通过算符优先
3、算法来进行表达式求值，为实现算符优先算法，可以使用两个工作栈，一个称为OPTR，用以寄存运算符；另一个称为OPND，用以寄存操作数或运算结果。声明操作数栈：typedef struct NumStack / number stack int *base; int *top; int stacksize; NumStack;声明运算符栈：typedef struct SymStack / symbol stack char *base; char *top; int stacksize; SymStack;2. 任务调度：用结构体存储每个任务的任务顺序，需要时间，提交时间，开始时间，等待时间，结
4、束时间struct taskint order, need, t,start,wait,end; T100;三、算法设计1.表达式求值：Precede函数用以比较运算符的优先级，返回，= 或 , -, *, /, %, (, , #, ,=, ; /优先级表格 for(i=0;i9;i+) if(Table0i=a) /纵坐标寻找 break; for(j=0;j=49&s=57) /数字的ASCII码所在范围 /这儿决定了本程序只能计算一位数的四则运算 s-=48; return s; else return 0;/ReadNum求值函数result, 其基本求值过程为：1. 首先至操作数栈
5、为空栈，表达式起始符#为运算符的栈底元素；2. 依次读入表达式中每个字符，若是操作数则进OPND栈，若是运算符则和OPTR栈的栈顶运算符进行比较优先权后做相应的操作，直至整个表达式求值完毕（即OPTR栈的栈顶元素和当前读入的字符均为#）int 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
6、(ai+); else if(ai=+|ai=-|ai=*|ai=/|ai=%|ai=#|ai=(|ai=) switch(Precede(ai,CharGetTop(OPTR) 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); /打印输出表达式值 ret
7、urn OK; /while/result将中缀表达式转换为前缀表达式：1）求输入串的逆序。2）检查输入的下一元素。3）假如是操作数，把它添加到输出串中。4）假如是闭括号，将它压栈。5）假如是运算符，则i)假如栈空，此运算符入栈。ii)假如栈顶是闭括号，此运算符入栈。iii)假如它的优先级高于或等于栈顶运算符，此运算符入栈。iv)否则，栈顶运算符出栈并添加到输出串中，重复步骤5。6）假如是开括号，栈中运算符逐个出栈并输出，直到遇到闭括号。闭括号出栈并丢弃。7）假如输入还未完毕，跳转到步骤2。8）假如输入完毕，栈中剩余的所有操作符出栈并加到输出串中。9）求输出串的逆序。char perfix(c
8、har *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=-|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;
