1、湖南大学数据结构四则运算表达式求值实验报告HUNAN UNIVERSITY 课程实习报告 题 目： 四则运算表达式求值 学生姓名 学生学号 专业班级 指导老师 吴帆 完 成 日 期 一、 需求分析：1.本程序要求用户在字符界面上输入一个中缀表达式，回车表示结束。完成初始化后，把中缀表达式转化为后缀表达式输出，同时输出计算结果。2. 使用二叉树来实现 3. 测试数据：输入：21+23*（12-6）输出：21 23 12 6 - * +二、概要设计： 抽象数据类型利用二叉树后序遍历实现后缀表达式来实现算法。中缀表达式的存入和读取要用到两个临时的栈一个存操作数，一个存运算符。利用二叉树，根结点存操作
2、符，其他结点存操作数，利用二叉树的遍历可以方便的存入和读出操作数和运算符。结点的ADT定义如下： ADT BinNode数据对象：整型基本操作：string& element() ;/获取结点的值 string setElement(const string&) ;/设置结点的值 BinNode* left() const ; /获取左结点 void setLeft(BinNode*) ;/设置左结点 BinNode* right() const ; /获取右结点 void setRight(BinNode*) ;/设置右结点 bool isLeaf();/是否是叶子结点二叉树的ADT：ADT
3、 BinTree数据对象：BinNode基本操作： bool ErrorCheck(string a); /表达式错误检测 bool BintreeCreate(string str); /中缀表达式建树 int Precedence(const char&); /运算符op所对应的优先级划定 void postOrderTraverse(); /后序遍历 double value() return val(Root); /递归求表达式的值 void print(BinNode*); /打印函数void destroy(BinNode* cur) /后序销毁树 if (cur) destroy
4、(cur-lc); destroy(cur-rc); delete cur; double cacul(double a, char op, double b) /用于计算四则运算的工具函数 switch (op) case +: return a + b; case -: return a - b; case *: return a * b; case /: return a / b; double val(BinNode* cur) /在树中递归求值工具函数 if (cur-lc = NULL & cur-rc= NULL) double n; strq.clear(); strq opn
5、d); strqn; return n; else return cacul(val(cur-lc), cur-optr, val(cur-rc); void postOrder(BinNode* p) /后序遍历树的工具函数 if (p != NULL) postOrder(p-lc); postOrder(p-rc); print(p); ADT Stack：数据对象：BinNode类型数据关系：线性关系基本操作： void push(const E& it); /入栈 E pop(); /出栈 int length() const; /栈的大小 const E& topValue() c
6、onst; /返回栈顶元素的值 bool empty(); /是否为空树算法的基本思想(1)将中缀表达式转为二叉树 输入表达式 对表达式做错误检测； 中缀建树：利用两个临时的栈（一个存操作数，一个存运算符），扫描字符串：.进行括号检测：遇到左括号则入栈，扫描到的字符为“加、减、乘、除“且不为括号时弹出存操作数栈的栈顶两个操作数和此字符形成一个新的上一层结点并将其重新入栈，检测到右括号时弹出字符栈中的左括号，按此原理依次抵消每对括号；. 遇到数字或小数点继续扫描直到遇到符号为止，取此段扫描到的子串利用stringstream流（头文件）将子串转换成浮点型数据；.符号优先级比较：定义在栈中的左括号
7、和栈底字符（此程序中设为）的优先级最低，比较扫描到的字符和存字符栈的栈顶元素，若栈顶符号的优先级比扫描到的运算符优先级高则弹出存操作数栈的栈顶两个操作数和此字符形成一个结点并将其重新入栈按此规律依次将每一步运算的结果变成新的上一层结点入栈，最终剩下弹出的则为根结点，最后得到完整二叉树。（2）利用树的后序遍历提取后缀表达式；（3）利用树的递归求值： 分别对左右子树递归求出每一步的运算结果覆盖父结点操作数的值，递归返回直至覆盖到根结点，即为表达式的值。中缀建树：算法利用两个临时的栈，一个存操作数，一个存操作符，检测到操作数，建立叶子节点，压入存入操作数栈，遇到操作符，存入操作符栈，每次存操作符时与
8、前一个操作符做运算级别比较，若上一个操作符级别大，则弹出上一个操作符，同时弹出两个操作数建立二叉树，操作符做根节点，在把根节点压入操作数栈，括号做优先级最高处理，遇到右括号（前提是有了左括号和必要的运算式），操作符栈弹出，同时弹出两个操作数，建立二叉树，根节点压入操作数的栈。bool BinTree:BintreeCreate(string str) if (str.length() = 0) cout str; if(!ErrorCheck(str) coutsorry! 公式有误！endl; return 0; else Stack nodeStack; Stack opStack; op
9、Stack.push(); for (int i = 0; i 0) nodeStack.push(new BinNode(opStack.pop(),nodeStack.pop(), nodeStack.pop(); opStack.pop(); /弹出栈顶左括号 break; case +: case -: case *: case /: while(Precedence(opStack.topValue()=Precedence(stri) nodeStack.push(new BinNode(opStack.pop(),nodeStack.pop(), nodeStack.pop();
10、 opStack.push(stri); break; default:/扫描数字 int j; for(j=i+1;jstr.length();j+) if(strj=+|strj=-|strj=*|strj=/|strj=) break; nodeStack.push(new BinNode(str.substr(i,j-i),20); i=j-1; break; while (opStack.topValue() != ) nodeStack.push(new BinNode(opStack.pop(),nodeStack.pop(), nodeStack.pop(); Root =(B
11、inTree*) nodeStack.pop(); return 1;后序遍历提取后缀表达式： void BinTree:postOrderTraverse() cout The houzhui string is: endl; postOrder(Root); cout lc); postOrder(p-rc); print(p); 递归求值： double val(BinNode* cur)/在树中递归求值工具函数 if (cur-lc = NULL & cur-rc= NULL) double n; strq.clear(); /清空I/O流 strq opnd); strqn; ret
12、urn n; else return cacul(val(cur-lc), cur-optr, val(cur-rc); double cacul(double a, char op, double b)/用于计算四则运算的工具函数 switch (op) case +: return a + b; case -: return a - b; case *: return a * b; case /: return a / b; 程序的流程程序由五个模块组成：（1）初始化模块：完成中缀表达式的输入；（2）错误检测：检测中缀表达式输入的合法性；（3）中缀转换建树模块：中缀表达式建树，并利用后序遍
13、历输出树；（4）计算模块：利用递归计算表达式的值；（5）输出模块：输出后缀表达式及计算结果。三、详细设计：物理数据类型 用栈存取中缀表达式中的操作符和操作栈： class Stackprivate: int size; int top; float *listArray;public: Stack(int sz)size=sz; top=0; listArray=new BinNode size; Stack(); delete listArray;void push(const BinNode & it)/入栈 if(top=size) cout Stack is full endl; li
14、stArraytop+=it; E pop(BinNode & it)/出栈 if(top=0) cout Stack is empty endl; return listArray-top; const BinNode & topValue() const if(top=0) cout Stack is empty endl; return listArraytop-1; bool empty()/是否为空树判断栈是否为空 if(top=0) return true; else return false;int length() const return top; 用结点存操作数、操作符：
15、class BinNode public: BinNode(char,BinNode*,BinNode*); BinNode(string,int); BinNode() string& element() ;/获取节点的值 string setElement(const string&) ;/设置节点的值 BinNode* left() const ; /获取左结点 void setLeft(BinNode*) ;/设置左结点 BinNode* right() const ; /获取右结点 void setRight(BinNode*) ;/设置右结点 bool isLeaf();/是否是叶
16、子节点 char optr;/运算符 string opnd;/操作数 BinNode* lc; BinNode* rc; int len; BinNode:BinNode(char op, BinNode* l, BinNode* r): optr(op), lc(l), rc(r) BinNode:BinNode(string m,int leng): opnd(m), lc(NULL), rc(NULL),len(leng) string& BinNode:element() return opnd; string BinNode:setElement(const string& e)
17、opnd=e; return opnd; inline BinNode* BinNode:left() const return lc; void BinNode:setLeft(BinNode* b) lc = (BinNode*)b; inline BinNode* BinNode:right() const return rc; void BinNode:setRight(BinNode* b) rc = (BinNode*)b; bool BinNode:isLeaf() return (lc = NULL) & (rc = NULL); 算法的具体步骤 主函数流程图如下： 算法的时空
18、分析 此算法利用栈和二叉树来实现,故次算法的的时间复杂度为(n)。函数的调用关系图 输入字符串，创建Stack对象!ErrorCheck(str) 主程序switch (stri)BintreeCreate(string str) Root =(BinTree*) nodeStack.pop(); postOrderTraverse()value()输入和输出的格式 输入 Enter the string of zhongzhui(End up with CR)： /提示等待输入输出 The houzhui string is: /输出表达式结果的位置 The result is: /输出表达
19、式值结果的位置四、调试分析： 无五、测试结果: 六、用户使用说明:1、本程序的运行环境为DOS操作系统，执行文件为szys.exe2、运行程序时提示输入Enter the string of zhongzhui(End up with CR)： 请输入一个中缀表达式（以正整数作为操作数，混合+、-、*、/运算和（），以回车结束输入） 输出 The houzhui string is: 后缀表达式 The result is: 后缀表达式的值七 、实验心得： 这次的实验感觉很难，大致的建树和遍历的大致思想比较好理解，递归求值的效率和简洁度也很令人佩服，难点就在建树过程中括号的检测，出入栈结合叶子
20、结点和分支结点的建立操作起来感觉也有些吃力，还是要巩固对栈、二叉树的掌握，提高编程能力。八、附录： /Stack.htemplateclass Stack public: Stack(int sz=10); Stack(); void push(const E& it);/入栈 E pop();/出栈 int length() const; const E& topValue() const;/返回栈顶元素的值 bool empty();/是否为空树 private: int size; int top; E *listArray;templateStack:Stack(int sz) /栈构
21、造函数 size=sz; top=0; listArray=new Esize;templateStack:Stack() delete listArray;templatevoid Stack:push(const E& it) if(top=size) cout Stack is full endl; listArraytop+=it;templateE Stack:pop() if(top=0) cout Stack is empty endl; return listArray-top; templateconst E& Stack:topValue() const if(top=0)
22、 cout Stack is empty endl; return listArraytop-1;templateint Stack:length() const return top;templatebool Stack:empty() if(top=0) return true; else return false;/BinNode.hclass BinNode public: BinNode(char,BinNode*,BinNode*); BinNode(string,int); BinNode() string& element() ;/获取节点的值 string setElemen
23、t(const string&) ;/设置节点的值 BinNode* left() const ; /获取左结点 void setLeft(BinNode*) ;/设置左结点 BinNode* right() const ; /获取右结点 void setRight(BinNode*) ;/设置右结点 bool isLeaf();/是否是叶子节点 char optr;/运算符 string opnd;/操作数 BinNode* lc; BinNode* rc; int len; BinNode:BinNode(char op, BinNode* l, BinNode* r): optr(op)
24、, lc(l), rc(r) BinNode:BinNode(string m,int leng): opnd(m), lc(NULL), rc(NULL),len(leng) string& BinNode:element() return opnd; string BinNode:setElement(const string& e) opnd=e; return opnd; inline BinNode* BinNode:left() const return lc; void BinNode:setLeft(BinNode* b) lc = (BinNode*)b; inline Bi
25、nNode* BinNode:right() const return rc; void BinNode:setRight(BinNode* b) rc = (BinNode*)b; bool BinNode:isLeaf() return (lc = NULL) & (rc = NULL); /BinTree.h#includeBinNode.h#includeStack.h#includestringstream strq;class BinTree:public BinNodepublic: BinTree(char op,BinNode* let,BinNode*ret) :BinNo
26、de(op,let,ret)Root=NULL; bool ErrorCheck(string a); bool BintreeCreate(string str); /中缀表达式建树 BinTree()destroy(Root); int Precedence(const char&); /返回运算符op所对应的优先级 void postOrderTraverse(); /后序遍历 double value() return val(Root); /递归求表达式的值 void print(BinNode*); private: BinNode * Root; void destroy(BinNode* cur) if (cur) destroy(cur-lc); destroy(cur-rc); delete cur; double cacul(double a, char op, double b)/用于计算四则运算的工具函数 switch (op) case +: return a + b; case -: return a - b; case *: return
