中缀表达式转为后缀表达式并求值

哈尔滨工业大学计算机科学与技术学院实验报告课程名称：数据结构与算法课程类型：必修实验项目名称：线性表的实现与应用实验题目：中缀表达式转成后缀表达式并求值班级：1203103学号：1120310321姓名：张文博设计成绩报告成绩指导老师一、实验目的：1.练习栈的创建和常规操作，例：置空栈，判断空栈，返回栈顶元素，压栈，出栈……2.学习中缀表达式和后缀表达式的定义和表示方法。3.学习中缀表达式和后缀表达式的存储和输出。4.学习中缀表达式转化为后缀表达式。5.学习后缀表达式的求值。6.练习编写循环程序的算法。二、实验要求及实验环境实验要求：输入中缀表达式，把中缀表达式转化为后缀表达式，输出后缀表达式，并对后缀表达式进行求值输出，其中能运行算术四则运算和求模运算。实验环境：codeblocks三、设计思想（本程序中的用到的所有数据类型的定义，主程序的流程图及各程序模块之间的调用关系）1.逻辑结构：线性结构2.物理结构：线性存储结构中的顺序结构，即用数组和栈存储数据。本实验中定义了两种线性表形式：数组和栈。用字符型数组存储输入的字符串和和转化为的后缀表达式。在把中缀表达式转化为后缀表达式时，用字符栈存储字符串中的字符，并永远保证栈顶的字符优先级最高；在进行后缀表达式求值时，用数据栈存储数字，按顺序存储，遇到字符时，从栈顶依次弹出两个数据。此外，还定义了一些整型和字符型变量，用于辅助程序的正确运行。主函数中调用change函数，把中缀表达式转化为后缀表达式；主函数调用operate函数，进行算术式的运算。Change函数调用precede函数，进行字符优先级的比较。主函数和change函数都调用in函数，进行是否为字符的判断。此外，主函数和change函数都有调用initstack函数，push函数，pop函数，gettop函数……来帮助函数的运行。我编写程序的大致思路：1.中缀表达式转为后缀表达式首先是遇见数字存入数组，遇见字符压栈，并且先把字符栈底压入一个‘#’。当遇见‘（’时，根据下一个字符是否是‘-’来判断是否是负数。若有‘-’，是负数，存入数组，若没有，把‘（’压栈。例：（-5）。当遇见‘）’时，开始把运算符弹栈，直到遇到‘（’。当遇见其他运算符时，根据比较与字符栈顶元素的优先级决定如何压栈。优先级设定：#为0，（）为1，+-为2，*/%为3。当栈顶元素的优先级大于等于此运算符时，弹栈进入数组，否则把该运算符压栈。2.求后缀表达式的值遇见数字时压栈，遇见运算符时从栈中弹出两个，进行运算。遇见‘-’时，根据后一位元素是否为数字，进而判断是负号，还是减号，若是负号，求出该负数对应的正数，再取反压栈即可。遇见浮点数数时，先求小数点前面的整数部分，再求小数点后面整数部分，根据位数a，除以10*a，即可得到小数部分，小数部分与整数部分相加即为该浮点数，压栈即可。开始时，将操作数进栈保留；当遇到操作符时，从栈中退出两个操作数并作相应运算，将计算结果进栈保留；直到表达式结束，栈中唯一元素即为表达式的值结束时，将操作数进栈保留；当遇到操作符时，从栈中退出两个操作数并作输出相应的后缀表达式输入中缀表达式并存储到数组中输出后缀表达式的值计算后缀表达式的值调用change函数，把中缀表达式转化为后缀表达式四、测试结果输入中缀表达式输出后缀表达式结果(2.5*4+5)/32.54*5+3/5(-5)+10*2/(-4)-5102*-4/+-10五、系统不足与经验体会系统不足：没有完全考虑输错情况下，程序该如何操作，进而导致程序的健壮性不好，此外，没有过多的考虑由于外面因素，程序错误运行的情况。经验体会：1.对栈的操作要深刻明白先进后出，后进数据的位于栈顶。2.数组是按址调用，在调用函数内可以改变其值。3.程序循环运行每轮结束后，一定要记得释放内存，或清空数组里的内容。4.小数和负数要特殊考虑，编写合适的算法。5.条件语句中的条件要慎重考虑，反复斟酌。六、附录：源代码（带注释）#includestdio.h#includestdlib.h#defineSIZE100#defineERROR0typedefstruct//定义数据栈{floatdata[SIZE];inttop;intbase;}SqStack_f;typedefstruct//定义字符栈{chardata[SIZE];inttop;intbase;}SqStack_c;charOPSET[8]={'+','-','*','/','%','(',')','#'};//定义OPSET字符数组为算符集合voidInitStack_f(SqStack_f*s)//置数据栈S为空{s-top=0;s-base=0;}voidInitStack_c(SqStack_c*s)//置字符栈S为空{s-top=0;s-base=0;}intEmpty_f(SqStack_f*s)//判定s是否为空栈{if(s-base==s-top)return1;elsereturn0;}intEmpty_c(SqStack_c*s)//判定s是否为空栈{if(s-base==s-top)return1;elsereturn0;}floatGetTop_f(SqStack_f*s)//若数据栈非空，则返回s的栈顶元素；否则返回ERROR{if(s-top==s-base)returnERROR;return(s-data[s-top-1]);}charGetTop_c(SqStack_c*s)//若字符栈非空，则返回s的栈顶元素；否则返回ERROR{if(s-top==s-base)returnERROR;return(s-data[s-top-1]);}voidPush_f(SqStack_f*s,floate)//插入e为新的栈顶元素{s-data[s-top]=e;s-top++;}voidPush_c(SqStack_c*s,chare)//插入e为新的栈顶元素{s-data[s-top]=e;s-top++;}floatPop_f(SqStack_f*s)//若数据栈不空，则删除之，并返回栈顶值；否则返回REEOR{floate;if(s-base==s-top)returnERROR;else{e=s-data[s-top-1];s-top--;}returne;}charPop_c(SqStack_c*s)//若字符栈不空，则删除之，并返回栈顶值；否则返回REEOR{chare;if(s-base==s-top)returnERROR;else{e=s-data[s-top-1];s-top--;}returne;}intIn(chars,char*TestOp)//s为待判断字符，TestOp为已知的算符集合{intFind=0,i;for(i=0;i8;i++){if(s==TestOp[i]){Find=1;}}returnFind;}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'#':pre[i]=0;break;case'(':case')':pre[i]=1;break;case'+':case'-':pre[i]=2;break;case'*':case'/':case'%':pre[i]=3;break;}}if(pre[0]=pre[1])return1;elsereturn0;}voidChange(char*s1,char*s2)//将中缀表达式转为后缀表达式{SqStack_cOPTR;charch;inti=0,j=0;InitStack_c(&OPTR);Push_c(&OPTR,'#');while(s1[i]!='\0'){if(!In(s1[i],OPSET))//不是运算符则进数组{while((s1[i]='0'&&s1[i]='9')||s1[i]=='.'){s2[j++]=s1[i];i++;}s2[j++]='';//存入一个空格}else{switch(s1[i]){case'(':i++;if(s1[i]=='-')//此处判断是否是负数，若是，把负数存入数组，若不是，把运算符存入堆栈。{while(s1[i]!=')'){s2[j++]=s1[i];i++;}s2[j++]='';//存入一个空格i++;}else{i--;Push_c(&OPTR,s1[i]);i++;}break;case')':ch=Pop_c(&OPTR);do//输出括号内的所有运算符{s2[j++]=ch;s2[j++]='';//补入一个空格作为间隔ch=Pop_c(&OPTR);}while(ch!='(');i++;break;default:while(precede(GetTop_c(&OPTR),s1[i]))//判断运算符的优先级，始终保存栈顶的优先级最高{s2[j++]=Pop_c(&OPTR);s2[j++]='';//补入一个空格作为间隔}Push_c(&OPTR,s1[i]);i++;}}}while(GetTop_c(&OPTR)!='#')//当s1扫描完成后，把运算符栈中的运算符全部输出存入数组s2{s2[j++]=Pop_c(&OPTR);s2[j++]='';//补入一个空格作为间隔}}floatOperate(floata,chartheta,floatb)//返回a与b间theta运算的结果{intd,e;switch(theta){case'+':returna+b;break;case'-':returna-b;break;case'*':returna*b;break;case'/':if(b==0){printf(ErrorDivisoris0\n);returnERROR;}returna/b;break;case'%':d=(int)a;e=(int)b;if(e==0){printf(ErrorDivisoris0\n);returnERROR;}return(float)(d%e);break;default:printf(Error\n);returnERROR;}}intmain()//计算后缀表达式的值{SqStack_fOPND;charc,ch;inti=0,step=0,j=0;floata=0,b=0,s=0;do{i=0;charreceive[100]={0},exp[100]={0};InitStack_f(&OPND);printf(请输入一个中缀表达式：\n);gets(receive);//输入中缀表达式,负数的输入必须要加括号，eg：（-5）+6Change(receive,exp);printf(相应的后缀表达式为：\n);puts(exp);//输出对应的后缀表达式ch=exp[0];while(ch!='\0')//计算后缀表达式的值{if(!In(exp[i],OPSET))//不是运算符则压入栈中{s=0;a=b=step=0;while(exp[i]='0'&&exp[i]='9'&&exp[i]!='.'&&exp[i]!='')//算出小数点前面的整数数值{s=10*s+exp[i]-48;i++;}if(exp[i]=='.')//满足此条件的为小数，算出小数点后面的数值{i++;while(exp[i]='0'&&exp[i]='9'&&exp[i]!=''){b=10*b+exp[i]-48;i++;step++;}for(j=0;jstep;j++){b=b/10;}}a=s+b;//一个数的整数部分和小数部分相加，赋于aPush_f(&OPND,a);c