实验3四则运算表达式求值

数据结构四则运算表达式求值实验报告四则运算表达式求值学生姓名：陈旸浩学生学号：20110807220专业班级：智能科学与技术2班指导老师：骆嘉伟数据结构四则运算表达式求值实验报告实验5四则运算表达式求值一、需求分析：1．本程序是利用二叉树后序遍历来实现表达式的转换，同时可以使用实验三的结果来求解后缀表达式的值。2．输入：在字符界面上输入一个中缀表达式，回车表示结束。3．输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示。4．测试数据输入：21+23*（12-6）输出：2123126-*+运算结果为：149二、概要设计抽象数据类型为实现上述程序的功能，应以二叉树类BiTree存储用户的输入，以及计算出的结果。算法的基本思想根据题目要求，利用栈计算，和二叉树存储，来计算表达式。该算法的基本思想是：先利用栈进行计算，然后用二叉树进行存储，和实验三算法一样来计算逆波兰表达式的值。程序的流程程序由三个模块组成：（1）输入模块：输入一个运算式（2）计算模块：利用栈进行表达式的计算，二叉树来存储。（3）输出模块：屏幕上显示出后缀表达式和运算结果。三、详细设计物理数据类型用二叉树表示表达式：若表达式为数或简单变量，则相应二叉树中仅有一个根结点，其数据域存放该表达式信息；若表达式=（第一操作数）（运算符）（第二操作数），则相应的二叉树中以左子树表示第一操作数，右子树表示第二操作数，根结点的数据域存放运算符（若为一元算符，则左子树空）。操作数本身又为表达式。算法的具体步骤数据结构四则运算表达式求值实验报告中序表达式转后序表达式*houxu(char*infix)：从左到右遍历中序表达式的每一数字和符号，若是数字就输出，即成为后序表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后序表达式为止。后序表达式计算结果qiuzhi(char*postfix)：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。算法的时空分析时间复杂度：O（n）；空间复杂度：O（n）；输入和输出的格式输入：输入表达式：输出：后序表达式：后续表达式求值：四、测试结果五、附录#includeiostreamusingnamespacestd;#includestdio.h#includestdlib.h#includestring.hintPRI(charop)//设定算符的优先级{switch(op){case'+':case'-':return1;case'*':case'/':return2;数据结构四则运算表达式求值实验报告default:return0;}}char*houxu(char*infix)//求后序表达式{intlength=strlen(infix);char*stack,*buf,*p,flag;charop;inti,top=0;if(!(stack=(char*)malloc(sizeof(char)*length)))//作为栈内存空间{cout内存分配失败!endl;exit(0);}if(!(buf=(char*)malloc(sizeof(char)*length)))//保存后序表达式字符串{cout内存分配失败!endl;exit(0);}p=buf;for(i=0;ilength;i++){op=infix[i];//获取表达式中一个字符switch(op)//根据字符进行入栈操作{case'('://为左括号if(toplength)//若栈未满{top++;//修改栈顶指针stack[top]=op;//保存运算符到栈}flag=0;break;case'+':case'-':case'*':case'/':while(PRI(stack[top])=PRI(op))//判断栈顶运算符与当前运算符的级别{*p++=stack[top];//将栈中的运算符保存到字符串top--;//修改栈顶指针flag=0;数据结构四则运算表达式求值实验报告}if(toplength)//栈未满{top++;//修改栈顶指针stack[top]=op;//保存运算符到栈if(flag==1)*p++='';//添加一个逗号分隔数字flag=0;}break;case')'://右括号while(stack[top]!='(')//在栈中一直找到左括号{*p++=stack[top];//将栈顶的运算符保存到字符串top--;//修改栈顶指针}flag=0;top--;//再将修改栈顶指针，将左括号出栈break;default://其他字符(数字、字母等非运算符)*p++=op;flag=1;break;}}while(top0)//若栈不为空{*p++=stack[top];//将栈中的运算符出栈top--;//修改栈顶指针}free(stack);//释放栈占用的内存*p='\0';return(buf);//返回字符串}//表达式求值如下：doublecalc(doubled1,charop,doubled2)//计算函数{switch(op)//根据运算符进行操作{case'+':returnd1+d2;case'-':数据结构四则运算表达式求值实验报告returnd1-d2;case'*':returnd1*d2;case'/':returnd1/d2;}return0;}doubleqiuzhi(char*postfix)//计算表达式的值{double*stack,num,k=1.0;//k为系数inti,length,top=0,dec=0,flag;//dec为0表示整数,为1表示小数,flag=1表示有数据需入栈chartoken;length=strlen(postfix);if(!(stack=(double*)malloc(sizeof(double)*length))){cout内存分配失败!endl;exit(0);}num=0;for(i=0;ilength;i++){token=postfix[i];//取出一个字符switch(token){case'+'://若是运算符case'-':case'*':case'/':if(toplength&&flag==1)//若栈未满{top++;//修改栈顶指针stack[top]=(double)num;//将数字保存到栈中num=0;}stack[top-1]=calc(stack[top-1],token,stack[top]);//取出栈栈前两个元素进行运算，结果保存到栈中top--;//修改栈顶指针dec=0;//先设为整数flag=0;//下一步操作不将数入栈break;default://不为运算符数据结构四则运算表达式求值实验报告if(token=='')//若为空格{if(toplength)//若栈未满{top++;//修改栈顶指针stack[top]=(double)num;//将数字保存到栈中num=0;dec=0;break;}}elseif(token=='.'){k=1.0;dec=1;break;}if(dec==1)//小数部分{k=k*0.1;num=num+(token-'0')*k;}else{num=num*10+token-'0';}flag=1;//有数需要入库break;}}returnstack[top];//返回栈顶的结果}intmain(){charzhongxu[80];cout输入表达式:;cinzhongxu;cout后序表达式:houxu(zhongxu)endl;cout后序表达式求值:qiuzhi(houxu(zhongxu))endl;getchar();return0;}