北工大数据结构上机实验报告3.doc

上机题三报告 姓名： 学号： 完成日期：2015年5月5日 题目：表达式可以用表达式二叉树来表示。对于简单的四则运算表达式，请实现以下功能；（1）对于任意给出的前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号），能够在计算机内部构造出一棵表达式二叉树，并且以图示显示出来（字符图或图形的形式）。 对于构造好的内部表达式二叉树，按照用户要求，输出相应的前缀表达式（不带括号）、中缀表达式（可以带括号）或后缀表达式（不带括号）. 需求分析 输入形式、输入值的范围； 输出形式； 程序功能； 测试数据正确的输入输出 错误的输入输出 概要设计 ADT定义 主程序流程 各程序模块间的调用关系 详细设计 实现ADT定义的数据类型 class TNode//节点类 { public: char oper;//数据域，为简便起见，操作数用单个字符代替 TNode *left; TNode *right; int s;int t;//计算树的层数使用 TNode()//缺省构造函数 { left=right=NULL; oper=0; } TNode(char op)//赋值构造函数 { left=right=NULL; oper=op; } }; 算法描述 表达式转化为二叉树 void pre2tree(TNode *p, string str)//前缀表达式生成二叉树 { 碰到操作数则把其值赋给相应的新申请的二叉树结点，地址压栈； 碰到操作符则把其值赋给相应的新申请的二叉树，并从栈中弹出两个地址， 分别作为其左指针和右指针，然后再把其地址压栈，最后一个地址即为二叉树的根结点地址。 } void post2tree(TNode *p,string str)//后缀表达式生成二叉树 { //碰到操作数则把其值赋给相应的新申请的二叉树结点，若栈为空则地址压栈， //碰到操作符则把其值赋给相应的新申请的二叉树结点，取栈顶元素， //若当前元素的左孩子为空则设为其左孩子， //左孩子为满则设为其右孩子,开始那个元素地址为根结点地址，开始时用变量root保存。 } void in2tree(TNode *p, string str)//中缀表达式转换成后缀表达式生成二叉树 { 从中缀表达式中自左至右依次读入各个字符。? 如果读入操作数，直接输出到后缀表达式。 如果读入的是运算符，并且运算符栈为空，则将该运算符直接进栈；如果栈不为空， 则比较该运算符和栈顶运算符的优先级。? ?????若该运算符高于栈顶运算符的优先级，则将该运算符直接进栈； 若该运算符低于或等于栈顶运算符的优先级，则将栈中高于或等于该运算符优先级的元 素依次出栈输出到后缀表达式中，然后再将该运算符进栈。 在碰到开括号和栈为空前反复弹出栈中元素? 若栈非空栈顶不是左括号且栈顶元素优先级不低于输入运算符时， /将栈顶元素弹出到后缀表达式 } 二叉树表达式转化为表达式? void postOrder(TNode *p) //先序遍历 { if(p) { postOrder(p-left); postOrder(p-right); coutp-oper; } } void preOrder(TNode *p) //后序遍历 { if(p) { coutp-oper; preOrder(p-left); preOrder(p-right); } } void inOrder(TNode *p)//中序遍历，同时输出不带冗余括号的中缀表达式 { if(p) { if(p-left) {if(如果当前节点的左子树是运算符，且运算符优先级低于当前运算符， 那么左边的表达式要先计算，需要加括号) { cout(; inOrder(p-left); cout); } else//否则直接输出左子树 inOrder(p-left); } coutp-oper;//输出当前节点 if(p-right) { if(如果当前节点的右子树是运算符，且运算符优先级不高于当前运算符， 那么右边的表达式要先计算，需要加括号) { cout(; inOrder(p-right); cout); } else inOrder(p-right); } } 程序测试 用户使用说明 运行程序后，按照提示选择表达式类型（-1：前缀表达式；0：中缀表达式；1：后