数据结构 四则运算表达式求值 实验四报告.docVIP

HUNAN UNIVERSITY实验四最终报告题 目： 四则运算表达式求值 学生姓名 学生学号 专业班级 指导老师 李晓鸿 完 成 日 期 2014年5月8日 一、 需求分析1 本程序要求把用户输入的中缀四则算术表达式，转化为后缀表达式，并计算出结果，然后输出到DOS界面。2 输入形式：21+23*（12-6）处理非法操作，对输入表达式含有两个连续的运算符、除数为0、括号不匹配的非法输入报错。3 输出形式：输入表达式正确时，输出转换后的后缀表达式，显示计算结果。输入表达式错误时，对相应的非法输入显示报错的提示。4 程序功能：用二叉树实现四则运算表达式的求值，并把输入的中缀四则运算表达式转换成后缀表达式后，计算结果输出。5 测试数据包含合法输入和非法输入的情况后，共有四种情况：1) 输入：21+23*（12-6）输出：后缀表达式为：23 12 6 -*+ result is 1592) 输入：（1+2）*3输出：错误！括号不匹配！3) 输入：12-5/0输出：后缀表达式为：32 5 0 / + 错误！除数不能为0！4) 输入：1+3*3输出：错误！不能有连续的两个运算符！二、概要设计抽象数据类型使用二叉树实现四则运算表达式的求值，为本问题确定一个树型关系，数据对象为树的每一个结点。因为表达式中会含有实数和字符，所以树每一个结点将要存放的数据既可能为实数也可能为字符。在创建二叉树时，用两个堆栈先分别存储字符和操作数，根据操作数和操作符间的运算关系，把操作数和操作符存储到二叉树的结点中。根据算术运算的普遍规律，我们为程序中所存储的操作数定义为浮点型变量。二叉树节点BinNode的ADT：数据对象：Elem基本操作：void setVal(const Elem& e) it = e; inline BinNode* left() const =0; return lc; /返回左子节点的节点信息inline BinNode* right() const =0;return rc;/返回右子节点的节点信息二叉树BiTree 的ADT： 数据对象D：D是BinNode类的数据元素的集合数据关系R：若D为空集，则称为空树 。否则: (1) 在D中存在唯一的称为根的数据元素root； (2) 当n1时，其余结点可分为m (m0)个互不相交的有限集T1, T2, , Tm，其中每一棵子集本身又是一棵符合本定义的树，称为根root的子树。 基本操作：void creatTree(BinNodePtr*,char*); /创建二叉树void postTraver(BinNodePtr*,char*,int&); /后序周游二叉树int creatNode(StackBinNodePtr*& ,char * ); /创建存储操作数的叶子节点void creatSub(StackBinNodePtr* &,char);/创建存储操作符的节点堆栈的ADT：数据对象D：D是BinNode类的数据元素的集合数据关系：R=|ai-1,aiD,i=1,2,3.n基本操作：bool push(const BinNode& item); /入栈bool pop(BinNode& it); /出栈bool topValue(BinNode& it) const; /获取栈顶的值int length() const; /栈的长度算法的基本思想构建二叉树，把输入的表达式存储在字符数组中，遍历字符数组把字符压入一个栈中，并逐个弹出栈中字符，根据字符的ASC判断字符表示数字或者运算符。若字符表示数字时，二叉树中以左子树表示第一操作数，右子树表示第二操作数，为她创建一个叶子结点保存，并把结点压入操作数栈中；若字符为运算符，并且运算符优先的情况下，把运算符存储为子结点的根结点，压入运算符栈中，直至栈为空。对二叉树进行后续遍历，可以得到后缀表达式。运算时，运算符栈顶弹栈，然后获取操作数栈顶和次栈顶的值进行运算，把运算结果创建一个叶子结点保存，把结点压回操作数栈中。如果操作数栈或运算符栈不为空时，继续进行运算操作。最后操作数栈中的值，就是运算结果。程序的流程（1） 输入模块：输入把原始的中缀表达式的操作数和操作字符存储为一个字符串。（2） 处理模块：把字符串逐个分解，调整各项字符的顺序，分解的中缀表达式转换为后缀表达式。 （3） 计算模块：计算后缀表达式的值。（4） 输出模块：输出后缀表达式及其计算结果。 三、详细设计物理数据类型因为表达式由用户输入，存储操作符和操作数的栈长度不能确定，所以使用链式堆栈存储这些变量。堆栈基本操作如下：bool push(const Elem& item) /压栈top=new link(item,top);size+;return true;bool pop(Elem& it) /弹栈if(size=0) return false;it=top-elem;link* ltemp=top-next;delete top;top=ltemp;size-;return true;bool topValue(Elem& it) const /获取栈顶的值if(size=0) return false;it=top-elem;return true;int length() constreturn size; /栈的长度 二叉树基本操作如下：(一) 创建二叉树模块（1）、 创建一颗二叉树：当把字符数组中的所有字符压入到栈中后，为了方便后面函数的读取相应大小的栈中数据，在栈顶先加入一个结束符”#”。void BiTree:creatTree(BinNodePtr* root,char exp) Stack PTR; /存储操作数的栈Stack OPTR; /存储操作符的栈char op,item;int i=0;OPTR.push(#); /添加一个结束符号OPTR.topValue(op);bool flag=true;while(!(expi=#)&(OPTR.topValue(item)=#) /不为结束符号#时if(isNum(expi) /为操作数flag=true;i+=creatNode(OPTR,&expi); /操作数入栈，并建立叶子结点保存else if(expi= )i+;flag=true;elseswitch(expi)case(: flag=true;OPTR.push(expi);i+;break;case):OPTR.topValue(op);OPTR.pop();while(op!=()flag=true;creatSub(PTR,op); /操作符入栈，保存为根结点 OPTR.topValue(op);OPTR.pop(item);i+;break;default:while(OPTR.length()0)OPTR.topValue(op);if(!flag)cout不能有两个连续的运算符)creatSub(PTR,op); /操作符入栈，保存为根结点OPTR.pop();if(expi!=#)OPTR.push(expi);i+;flag=false;break;root=PTR.topValue(); /返回树的根结点PTR.pop();（2）、 创建叶子节点：int creatNode(StackBinNodePtr*&PTR,char *c)BinNodePtr* T;int i=0;while(isNum(ci)T-iti=ci;i+;T-count=i;T-lc=T-rc=NULL;PTR.push(T);return i;（3）、 创建存储操作符的结点：void creatSub(StackBinNodePtr* &PTR,char c)BinNodePtr* T;T-it=c;T-count=1;PTR.topValue(T-rc);PTR.pop(T-rc);PTR.topValue(T-lc);PTR.pop(T-lc);PTR.push(T-lc);(二) 遍历模块： 创建二叉树完成后，后序遍历得到后缀表达式。/后序遍历二叉树void BiTree:postTraver(BinNodePtr* subroot,char *exp,int& n)if(subroot!=NULL)postTraver(subroot-left(),exp,n);postTraver(subroot-right(),exp,n);for(int i=0;icount;i+)expn+=subroot-setVal(i);expn+= ;(三) 判断模块：（1）、 字符代表数字int isNum(char ch)if(ch=0&ch, , , , /符号优先级 , , , , , , , , , , , , , , , , , =; char Precede(char a,char b) /返回比较的优先级结果 return(symbolsym_num(a)sym_num(b); (四) 运算模块：（1）、 运算调用模块void caculate(char ch,double &result)Stack S;int i=0;while(chi!=#&i100)if(isNum(chi)i+=EvalValue(&chi,S);/转换实数部分else if(chi= )i+;elseEvalExpr(chi,S); /弹栈，运算部分i+;if(S.length()=1)S.pop(result);（2）、 转换实数int EvalValue(char* ch,Stack &S)int i=0;double result=0;char a;a=chi;while(isNum(a) /字符代表数字result=10*result+(double)(a-48); /数字字符到实数的换算a=ch+i;S.push(result); /压入操作数栈中return i; （3）、 运算void EvalExpr(char ch,Stack &S)double s1=0,s2=0;if(S.length()2)cout表达式错误endl;exit(0);switch(ch)case+: /如果为加法S.pop(s1);S.pop(s2);S.push(s2+s1); break;case-: /如果为减法S.pop(s1);S.pop(s2);S.push(s2-s1); break;case*:/如果为乘法S.pop(s1);S.pop(s2);S.push(s2*s1); break;case/: /如果为除法S.pop(s1);S.pop(s2);if(s1!=0)S.push(s2/s1); else /非法输入报错cout除数不能为0！endl;exit(0);break;default: cout输入错误！endl;算法的具体步骤(一) 建树(二) 运算BinNodePtr T;BiTree t;/获得输入的表达式，并用字符数组存储起来while(i100)scanf(%c,&c);chi+=c;if(c=n)ch-i=#;break;i=0; /如果字符不为结束符号，进入输入表达式括号匹配的判断while(chi!=#) if(chi=(&chi+1!=) /如果左括号大于右括号 coutk+; else if(chi=(&chi+1=) coutk=1; break; else if(chi=)&chi-1!=() /如果右括号大于左括号coutk-; i+; if(coutk0) cout括号不匹配!endl; exit(0); /根据字符串ch的内容构建表达式二叉树Tt.creatTree(T, ch);/后序遍历二叉树，得到后缀表达式t.postTraver(T, exp, count);cout后缀表达式为n;for(i=0; icount; i+)coutexpi;coutendl;expcount = #; /添加结束符/计算表达式的结果caculate (exp, result); printf(result);算法的时空分析及改进设想 建树复杂度：每次递归查找根节点的复杂度是Q (n)Q，n为当前表达式树的节点数，所以总的开销是按这种规则所建的树中的所有子树的规模之和。其他部分的复杂度：后续遍历的复杂度是