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

数据结构 四则运算表达式求值实验报告 四则运算表达式求值 学生姓名：陈旸浩 学生学号：20110807220 专业班级：智能科学与技术2班 指导老师：骆嘉伟 实验5四则运算表达式求值1、 需求分析：1． 本程序是利用二叉树后序遍历来实现表达式的转换，同时可以使用实验三的结果来求解后缀表达式的值2． 输入：在字符界面上输入一个中缀表达式，回车表示结束3． 输出：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上输出表达式错误提示4． 测试数据输入：21+23*（12-6）输出：21 23 12 6 -*+运算结果为：149二、概要设计 抽象数据类型为实现上述程序的功能，应以二叉树类BiTree存储用户的输入，以及计算出的结果算法的基本思想根据题目要求，利用栈计算，和二叉树存储，来计算表达式该算法的基本思想是：先利用栈进行计算，然后用二叉树进行存储，和实验三算法一样来计算逆波兰表达式的值。

程序的流程 程序由三个模块组成： （1） 输入模块：输入一个运算式 （2） 计算模块：利用栈进行表达式的计算，二叉树来存储 （3 ） 输出模块：屏幕上显示出后缀表达式和运算结果三、详细设计物理数据类型用二叉树表示表达式：若表达式为数或简单变量，则相应二叉树中仅有一个根结点，其数据域存放该表达式信息；若表达式=（第一操作数）（运算符）（第二操作数），则相应的二叉树中以左子树表示第一操作数，右子树表示第二操作数，根结点的数据域存放运算符（若为一元算符，则左子树空）操作数本身又为表达式算法的具体步骤中序表达式转后序表达式*houxu(char *infix)：从左到右遍历中序表达式的每一数字和符号，若是数字就输出，即成为后序表达式的一部分；若是符号，则判断其与栈顶符号的优先级，是右括号或优先级低于栈顶符号（乘除优先加减）则栈顶元素依次出栈并输出，并将当前符号进栈，一直到最终输出后序表达式为止后序表达式计算结果qiuzhi(char *postfix)：从左到右遍历表达式的每个数字和符号，遇到是数字就进栈，遇到是符号，就将处于栈顶两个数字出栈，进行运算，运算结果进栈，一直到最终获得结果。

算法的时空分析时间复杂度：O（n）； 空间复杂度：O（n）；输入和输出的格式输入：输入表达式：输出：后序表达式：后续表达式求值：四、 测试结果五、附录#include using namespace std;#include #include #include int PRI(char op) //设定算符的优先级{ switch (op) { case +: case -: return 1; case *: case /: return 2; default: return 0; }}char *houxu(char *infix) // 求后序表达式{ int length=strlen(infix); char *stack,*buf,*p,flag; char op; int i,top=0; if(!(stack=(char *)malloc(sizeof(char)*length))) //作为栈内存空间 { cout<<"内存分配失败!"<=PRI(op)) //判断栈顶运算符与当前运算符的级别 { *p++=stack[top]; //将栈中的运算符保存到字符串 top--; //修改栈顶指针 flag=0; } if(top0) //若栈不为空 { *p++=stack[top]; //将栈中的运算符出栈 top--; //修改栈顶指针 } free(stack);//释放栈占用的内存 *p=\0; return (buf); //返回字符串 }//表达式求值如下：double calc(double d1, char op, double d2) //计算函数 { switch (op) //根据运算符进行操作 { case +: return d1 + d2; case -: return d1 - d2; case *: return d1 * d2; case /: return d1 / d2; } return 0;}double qiuzhi(char *postfix) //计算表达式的值 { double *stack,num,k=1.0; //k为系数 int i,length,top=0,dec=0,flag;//dec为0表示整数,为1表示小数,flag=1表示有数据需入栈 char token; length=strlen(postfix); if(!(stack=(double *)malloc(sizeof(double)*length))) { cout<<"内存分配失败!"<>zhongxu; cout<<"后序表达式:"<