软件综合实习-算术表达式实验报告

算术表达式求值实验报告1.实验题目求一个可能包含加，减，乘，除，乘方的中缀表达式的值。2.需求分析程序用栈和序列编写，首先将中缀表达式转换到后缀表达式，然后对后缀表达求值。①输入的形式和输入值的范围：输入包含加、减、乘、除、乘方运算的中缀表达式；②输出的形式：先把中缀表达式转换为后缀表达式，再对后缀表达式求值，输出一个整数。③程序所能达到的功能：能对包含加，减，乘，除，乘方的中缀表达式求值。④测试数据：31*(5-(-3+25))+70^2输出结果为43742*5+6*(7-8)+6输出结果为103.概要设计1)为了实现上述程序的功能，需要定义操作数栈和运算符栈:typedefintStatus;{templatetypenameT1,typenameT2StatusInitStack(T1&S){S.base=(T2*)malloc(STACK_INIT_SIZE*sizeof(T2));if(!S.base)exit(overflow);S.top=S.base;//顺序栈结构floatdata[MaxSize];inttop;}OpStack,SeqStack;voidInitStack(SeqStack&s);//初始化voidPush1(SeqStack&S1,chare);//声明入栈函数voidPush2SeqStack2&S2,floate);//声明入压栈函数intStackEmpty(SeqStack&s);//判断栈是否为空intGetTop(SeqStack&s,DataType*e);//取栈顶元素intPushStack(SeqStack&s,DataTypee);//入栈intPopStack(SeqStack&s,DataType*e);//出栈voidTranslateE(chars1[],chars2[]);//将中缀表达式转化为后缀表达式floatComputeE(chars[]);//计算后缀表达式2)本程序包含7个函数：①主函数main()②计算后缀表达式的函数ComputeE()③中缀表达式转换为后缀表达式的函数TranslateE()④初始化栈InitStack()⑤判断栈是否为空的函数StackEmpty()⑥入栈函数PushStack()⑦出栈函数popStack()4.详细设计部分重要伪码算法:1)栈的定义typedefstruct{floatdata[MaxSize];inttop;}OpStack,SeqStack;2)判断栈是否为空/*若栈S为空栈，则返回TRUE，否则返回FALSE*/StatusStackEmpty(LinkStackS){if(S.count==0)returnTRUE;elsereturnFALSE/*把S置为空栈*/StatusClearStack(LinkStack*S){LinkStackPtrp,q;p=S-top;while(p){q=p;p=p-next;free(q);}S-count=0;returnOK;}3）中缀表达式转换为后缀表达式voidTranslateE(charstr[],charexp[]){SeqStacks;charch;DataTypee;inti=0,j=0;InitStack(&s);ch=str[i];i++;while(ch!='\0')//依此扫描中缀表达式中的每个字符{switch(ch){case'('://遇到左括号,将其进栈PushStack(&s,ch);break;case')'://遇到右括号,将栈中的操作数出栈,并将其存入数组exp中while(GetTop(s,&e)&&e!='('){PopStack(&s,&e);exp[j]=e;j++;}PopStack(&s,&e);//将左括号出栈break;case'+':case'-'://遇到加减号,将栈顶字符出栈,并将其存入数组exp中,然后将当前运算符进栈while(!StackEmpty(s)&&GetTop(s,&e)&&e!='('){PopStack(&s,&e);exp[j]=e;j++;}PushStack(&s,ch);break;case'*'://遇到乘除号,先将同级运算符出栈,并存入数组exp中,然后将当前的运算符进栈case'/':while(!StackEmpty(s)&&GetTop(s,&e)&&e=='/'||e=='*'){PopStack(&s,&e);exp[j]=e;j++;}PushStack(&s,ch);break;case'':break;default://遇到操作数,则将操作数直接送入数组exp中,并在其后添加一个空格,用来分隔数字字符while(ch='0'&&ch='9'){exp[j]=ch;j++;ch=str[i];i++;}i--;exp[j]='';j++;}ch=str[i];//读入下一个字符i++;}while(!StackEmpty(s))//将栈中所有剩余的运算符出栈,送入数组exp中{PopStack(&s,&e);exp[j]=e;j++;}exp[j]='\0';}5．调试分析(略)6．使用说明程序名为experiment1.exe，运行环境为vc6等。7．测试结果8.附录#includestdio.h#includemalloc.h#includemath.h#includestring.h#includectype.h#includestdlib.h#defineSTACK_INIT_SIZE100#defineSTACKINCREMENT10//类型声明部分typedefstruct{char*base;char*top;intstacksize;}Sqstack1;//运算符栈类型定义typedefstruct{double*base;double*top;intstacksize;}Sqstack2;//操作数栈类型定义/***********************************函数声明部分******************************************///运算符栈相关操作声明intInitStack1(Sqstack1&S);charGetTop1(Sqstack1&S);intPush1(Sqstack1&S,chare);intPop1(Sqstack1&S,char&e);charPrecede(charc1,charc2);//操作数栈相关操作声明intInitStack2(Sqstack2&S);doubleGetTop2(Sqstack2&S);intPush2(Sqstack2&S,doublee);intPop2(Sqstack2&S,double&e);//其他相关操作声明doubleOperate(doublea,chartheta,doubleb);intIn(charc);Sqstack1OPTR;Sqstack2OPND;chartemp[100];inti=0,j;intmain()//主函数部分{charc,x,theta;doublea,b,num=0,ans;intcount=0,flag=1;InitStack1(OPTR);Push1(OPTR,'#');InitStack2(OPND);Push2(OPND,0);c=getchar();while(c!='#'||GetTop1(OPTR)!='#'){temp[i]=c;if(c=='(')j=i;i++;if(!In(c))//不是运算符则进栈{//当读入非运算符，将字符转换成数字储存，读入下一个字符，若下一个字符为数字，则进行进位运算,继续读入下一个字符//若下一个字符为小数点，则保留进位运算的结果作为整数部分，将flag=0，读入小数点后的字符，自动转换成数字//count由零开始自增，直到读入字符为操作符时，将num，flag，integer，decimal还原if(c=='.'){flag=0;c=getchar();}else{if(flag==1){num=num*10+c-48;c=getchar();}else{count++;num+=(c-48)/pow(10,count);c=getchar();}}if(In(c)){Push2(OPND,num);flag=1;count=0;num=0;}}elseswitch(Precede(GetTop1(OPTR),c)){case''://栈顶元素优先级低Push1(OPTR,c);c=getchar();break;case'='://脱括号并接收下一字符Pop1(OPTR,x);c=getchar();break;case''://退栈并将运算结果入栈Pop1(OPTR,theta);Pop2(OPND,b);Pop2(OPND,a);Push2(OPND,Operate(a,theta,b));break;}//switch}//whileans=GetTop2(OPND);printf(%.2f\n,ans);}//主函数结束/*******************函数实现部分************************///运算符栈的相关函数实现intInitStack1(Sqstack1&S){S.base=(char*)malloc(STACK_INIT_SIZE*sizeof(char));if(!S.base)return-1;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return1;}//InitStackcharGetTop1(Sqstack1&S){//若栈不空，用e返回S的栈顶元素，并返回1，否则返回-1chare;if(S.top==S.base)return-1;e=*(S.top-1);returne;}//GetTopintPush1(Sqstack1&S,chare){//插入元素e为新的栈顶元素if(S.top-S.base=S.stacksize){//栈满，追加存储空间S.base=(char*)realloc(S.base,(S.stacksize+STACKINCREMENT)*sizeof(char));if(!S.base)return-1;S.top=S.base+S.stacksize;S.stacksize+=STACKINCREMENT;}*S.top++=e;return1;}//PushintPop1(Sqstack1&S,char&e){//若栈不空，则删除S的栈顶元素，用e返回其值，并返回1，否则返回-1if(S.top==S.base)return-1;e=*--S.top;return1;}//Pop/**********************************************************************************************///操作数栈的相关函数实现intInitStack2(Sqstack2&S){S.base=(double*)malloc(STACK_INIT_SIZE*sizeof(double));if(!S.base)return-1;S.top=S.base;S.stacksize=STACK_INIT_SIZE;return1;}//InitStackdoubleGetTop2(Sqstack2&S){//若栈不空，用e返回S的栈顶元素，并返回1，否则返回-1doublee;if(S.top==S.base)return-1;e=*(S.top-1);returne;}//GetTopintPush2(Sqstack2&S,doublee)//插入元素e为新的栈顶元素{if(S.top-S.base=S.st