数据结构 任务调度 实验报告

实验报告实验名称：表达式求值任务调度实验类型：综合性实验班级：学号：姓名：实验日期：2014.5.28表达式求值1.问题描述表达式是数据运算的基本形式。人们的书写习惯是中缀式，如：11+22*(7-4)/3。中缀式的计算按运算符的优先级及括号优先的原则，相同级别从左到右进行计算。表达式还有后缀式（如：2274-*3/11+）和前缀式（如：+11/*22–743）。后缀表达式和前缀表达式中没有括号，给计算带来方便。如后缀式计算时按运算符出现的先后进行计算。本设计的主要任务是进行表达式形式的转换及不同形式的表达式计算。2.数据结构设计建立栈，算数表达式的计算往往是通过栈来实现的，所以建立结构体，如下typedefstruct{float*base;//栈底指针float*top;//栈顶指针intstacksize;}SqStack_f;//实数栈typedefstruct{char*base;char*top;intstacksize;}SqStack_c;//字符栈3.算法设计voidTranslate(char*s1)//中缀转后缀{chars2[80];SqStack_cOptr;inti=0,j=0;chart;InitStack_c(&Optr);//初始化一个运算符栈Push_c(&Optr,'(');while(s1[i]!='#'){if(s1[i]='0'&&s1[i]='9'||s1[i]=='.'){s2[j++]=s1[i];if((s1[i+1]'0'||s1[i+1]'9')&&s1[i+1]!='.')s2[j++]='';//将完整的字符型数字存入然后存入空格}elseswitch(s1[i]){case'(':Push_c(&Optr,s1[i]);break;//遇到左括号将其压栈case')':Pop_c(&Optr,&t);//遇到右括号时将栈内运算符弹出并压入数组s2直到遇到左括号while(t!='('){s2[j++]=t;Pop_c(&Optr,&t);}break;default:while(GetTop_c(&Optr,&t),precede(t,s1[i]))//与栈顶元素比较若栈顶元素级别高则进行以下循环{Pop_c(&Optr,&t);s2[j++]=t;//弹出栈顶元素并存入数组s2}Push_c(&Optr,s1[i]);//将当前遇到运算符压栈}i++;}Pop_c(&Optr,&t);while(t!='('){s2[j++]=t;Pop_c(&Optr,&t);}for(i=0;ij;i++)s1[i]=s2[i];s1[i]='#';s1[i+1]='\0';}voidCalculate(SqStack_f*s,char*s2)//计算表达式的值{floatm,x,y,z;intp,i=0,j=0;while(s2[i]!='#'){if(s2[i]='0'&&s2[i]='9'||s2[i]=='.'){m=0;while(s2[i]!=''&&s2[i]!='.')m=m*10+(float)(s2[i++]-'0');if(s2[i]=='.'){j=0;i++;while(s2[i]!=''){m=m*10+(float)(s2[i++]-'0');j++;}while(j0){m/=10;j--;}}i++;Push_f(s,m);GetTop_f(s,&m);}else{Pop_f(s,&x);Pop_f(s,&y);switch(s2[i]){case'+':z=y+x;Push_f(s,z);break;case'-':z=y-x;Push_f(s,z);break;case'*':z=y*x;Push_f(s,z);break;case'/':if(x==0){printf(表达式出错，除数为‘0’，无意义\n);exit(1);}else{z=y/x;Push_f(s,z);break;}case'%':if(x==0||(int)x!=x||(int)y!=y){printf(表达式出错\n);exit(1);}else{p=(int)y%(int)x;Push_f(s,p);break;}}i++;}}}intprecede(charTop_char,chars1_char)//比较运算符的优先级{inti,pre[2];charop[2];op[0]=Top_char;op[1]=s1_char;for(i=0;i2;i++)switch(op[i]){case'(':case')':pre[i]=0;break;case'+':case'-':pre[i]=1;break;case'*':case'/':case’%’:pre[i]=2;break;}if(pre[0]=pre[1])//栈顶元素topchar=s1char就返回1return1;elsereturn0;}voidconvert(char*s,char*output)//中缀转前缀{intj=0;inttop=0;charstack[50];strcpy(output,);for(inti=strlen(s)-1;i=0;){if((s[i]=48&&s[i]=57)||s[i]=='.')output[j++]=s[i];if(s[i]==')'){top++;stack[top]=s[i];}while(s[i]=='+'||s[i]=='-'||s[i]=='*'||s[i]=='/'||s[i]=='%'){output[j++]='';if(top==0||stack[top]==')'||precede(s[i],stack[top])){top++;stack[top]=s[i];break;}else{output[j++]=stack[top];top--;}}if(s[i]=='('){while(stack[top]!=')'){output[j++]=stack[top];top--;}top--;}i--;}while(top!=0){output[j++]=stack[top];top--;}}4.界面设计printf(请输入算术表达式，结束前请输入#号！\n);5.运行、测试与分析6、实验收获与思考1．熟练掌握栈的定义及使用。2．了解表达式求值的转换算法。设计前、后缀表达式求值算法。3．设计操作数为多位实数，操作符为加、减、乘、除、求模的中缀表达式求值算法。定义算数符号的优先级。7、源代码#includestdio.h#includestdlib.h#includemalloc.h#includemath.h#includestring.h#defineTTACK_INIT_SIZE100#defineSTACKINCREMENT10typedefstruct{float*base;float*top;intstacksize;}SqStack_f;//实数栈typedefstruct{char*base;char*top;intstacksize;}SqStack_c;//字符栈voidInitStack_f(SqStack_f*s){s-base=(float*)malloc(TTACK_INIT_SIZE*sizeof(float));if(!s-base)exit(1);s-top=s-base;s-stacksize=TTACK_INIT_SIZE;}voidInitStack_c(SqStack_c*s){s-base=(char*)malloc(TTACK_INIT_SIZE*sizeof(char));if(!s-base)exit(1);s-top=s-base;s-stacksize=TTACK_INIT_SIZE;}voidGetTop_f(SqStack_f*s,float*e){if(s-top==s-base){printf(ERROR!\n);exit(1);}*e=*(s-top-1);}voidGetTop_c(SqStack_c*s,char*e){if(s-top==s-base){printf(ERROR!\n);exit(1);}*e=*(s-top-1);}voidPush_f(SqStack_f*s,floate){if(s-top-s-base=s-stacksize){s-base=(float*)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(float));if(!s-base){printf(OVERFLOW!\n);exit(1);}s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;}*s-top++=e;}voidPush_c(SqStack_c*s,chare){if(s-top-s-base=s-stacksize){s-base=(char*)realloc(s-base,(s-stacksize+STACKINCREMENT)*sizeof(char));if(!s-base){printf(OVERFLOW!\n);exit(1);}s-top=s-base+s-stacksize;s-stacksize+=STACKINCREMENT;}*s-top++=e;}voidPop_f(SqStack_f*s,float*e){if(s-top==s-base)exit(1);*e=*--s-top;}voidPop_c(SqStack_c*s,char*e){if(s-top==s-base)exit(1);*e=*--s-top;}intprecede(charTop_char,chars1_char)//比较运算符的优先级{inti,pre[2];charop[2];op[0]=Top_char;op[1]=s1_char;for(i=0;i2;i++)switch(op[i]){case'(':case')':pre[i]=0;break;case'+':case'-':pre[i]=1;break;case'*':case'/':case'%':pre[i]=2;break;}if(pre[0]=pre[1])//栈顶元素topchar=s1char就返回1return1;elsereturn0;}voidTranslate(char*s1)//中缀转后缀{chars2[80];SqStack_cOptr;inti=0,j=0;chart;InitStack_c(&Optr);//初始化一个运算符栈Push_c(&Optr,'(');while(s1[i]!='#'){if(s1[i]='0'&&s1[i]='9'||s1[i]=='.'){s2[j++]=s1[i];if((s1[i+1]'0'||s1[i+1]'9')&&s1[i+1]!='.')s2[j++]='';//将完整的字符型数字存入然后存入空格}elseswitch(s1[i]){case'(':Push_c(&Optr,s1[i]);break;//遇到左括号将其压栈case')':Pop_c(&Optr,&t);//遇到右括号时将栈内运算符弹出并压入数组s2直到遇到左括号while(t!='('){s2[j++]=t;Pop_c(&Optr,&t);}break;default:while(GetTop_c(&Optr,&t),precede(t,s1[i]))//与栈顶元素比较若栈顶元素级别高则进行以下循环{Pop_c(&Optr,&t);s2[j++]=t;//弹出栈顶元素并存入数组s2}Push_c(&O