《四则运算表达式求值(栈+二叉树-c++版)》由会员分享，可在线阅读，更多相关《四则运算表达式求值(栈+二叉树-c++版)（11页珍藏版）》请在金锄头文库上搜索。
1、HUNANUNIVERSITYHUNANUNIVERSITY课程实习报告题目：四那么运算表达式求值学生：周华毅学生学号：1专业班级：计科 1304：完成日 期 ：2015/5/11 / 11一、需求分析一、需求分析a)四那么运算表达式求值， 将四那么运算表达式用中缀表达式表示， 然后转换为后缀表达式，并计算结果。b)本程序要求利用二叉树后序遍历来实现表达式的转换， 同时可以使用实验 2 的结果来求解后缀表达式的值。c)在字符界面上输入一个中缀表达式， 回车表示完毕。如果该中缀表达式正确， 那么在字符界面上输出其后缀表达式， 其中后缀表达式中两相邻操作数之间利用空格隔开；如果不正确，在字符界面上
2、输出表达式错误提示。d)测试数据输入：21+23*12-6输出：21 23 12 6 -*+二、概要设计二、概要设计抽象数据类型抽象数据类型为实现上述程序的功能，应以字符串存储用户的输入，以与计算出的结果。算法的根本思想算法的根本思想根据题目要求， 利用二叉树后序遍历来实现表达式的转换。 该算法的根本模块包括二叉树的建立以与如何把输入的中缀表达式利用二叉树后序遍历转化为后缀表达式。1、首先要将输入的中缀表达式数字字符存入到二叉树中，由于存在两位或者两位以上的数，甚至还有小数，所以考虑用字符型指针存储数字字符和操作符。2、为了便于将中缀表达式存入二叉树中，在录入中缀表达式后，要进展相应的处理，比
3、如去掉空格符，添加完毕标志，如= 、 #等。3、中缀表达式存入到二叉树的过程中，要注意处理的顺序，如+ 、 -号的优先级比* 、 /号的 低，当遇到* 、 /号时，要判断树以上的节点中是否有+ 、 -号，有的话要与其交换位置。遇到 时要反复创建二叉树的结点，构建子二叉树，考虑到括号要处理的步骤可能会较多，可以考虑用递归。遇到 时那么直接完毕此子二叉树的建立。此外二叉树中叶子结点存储操作数，非叶子结点存储操作码。4、对创建好的二叉树进展后序遍历，即可得到相应的后缀表达式，实现方法可以用递归的方式， 由于后面还要计算表达式的值， 故便利的过程中要将结点中得到的数据存入新的字符数组中。程序的流程程序
4、的流程程序由三个模块组成：（1）输入模块：完成一个中缀表达式的输入，存入字符串数组arrayMax中。（2）计算模块：设计一个建立二叉树的函数，Node* crtTree(Node* root)，传入根结点指针，返回根结点指针，该函数的实现还要反复使用另一个函数chargetOp(Node *temp)，其将数字字符存入一个结点，并返回数字字符的后一个符号。void deal()函数功能是对字符数组进展处理。void output(Node *root);函数功能是获得处理后的字符串，也就是中缀表达式转化为的后缀表达式。（3）输出模块：如果该中缀表达式正确，那么在字符界面上输出其后缀表达式和表
5、达式的值；如果不正确，在字符界面上输出表达式错误提示。三、详细设计三、详细设计物理数据类型物理数据类型2 / 11题目要求输入的四那么运算表达式运算符只有加减乘除， 操作数有整数和小数， 为了能够存储，采用 C 语言中的字符串数组。char chMax;算法的时空分析算法的时空分析算法的运行时间主要消耗在二叉树的建立过程中。 可以发现， 每当遇到一个运算符或操作数时，都要调用一次函数char getOp(Node *temp)，来将其存入二叉树的结点中，其中也会遇到递归的情况，但耗时可以忽略。所以假设输入的字符串中字符个数为N，那么算法的时间复杂度为 O(N)。输入和输出的格式输入和输出的格式
6、输入本程序可以将输入的四那么运算表达式中缀表达式转换为后缀表达式/提示请输入四那么运算表达式：/提示等待输入输出/提示后缀表达式为：/输出结果的位置表达式的值为：/输出结果的位置四、调试分析四、调试分析本次实验的难点主要是在建立二叉树的问题上。关于如何把中缀表达式存入二叉树中，我参考了网上的一些方法， 成功实现了目标， 但是却遇到了一个问题， 那就是不能处理小数，甚至两位或两位以上的整数。 因为如果采用字符数组来存储操作数， 运算符合一位整数还可以处理，但对于两位数就就会出问题， 最后我改良采用字符串数组来存储操作数， 成功解决了问题。另外在处理输入的非法表达式问题中，我也费了很大功夫，但总体
7、问题不大。五、测试结果五、测试结果六、用户使用说明可选六、用户使用说明可选1、本程序的运行环境为DOS 操作系统2、运行程序时提示输入四那么运算表达式本程序可以将中缀表达式转化为后缀表达式，并计算结果请输入四那么运算表达式：输出后缀表达式为：表达式的值为：3 / 11七、附录可选七、附录可选程序源代码c+1 1、利用二叉树后序遍历来实现表达式的转换：、利用二叉树后序遍历来实现表达式的转换：#include#include#include#includeconst int Max=100;using namespace std;class Nodepublic:char chMax; /考虑到数
8、值有时会是两位数，所以使用字符串数组Node* lChild;Node* rChild;Node()strcpy(ch,);lChild=rChild=NULL;Node()if(lChild!=NULL)delete lChild;if(rChild!=NULL)delete rChild;static int count=0;static char arrayMax; /保存原始的中缀表达式static char str2*Max; /保存后序遍历出来的字符串，为表达式求值提供方便static int k=0;char getOp(Node *temp); /temp指针保存每个结点，返回
9、的是运算符Node* crtTree(Node* root); /传入根结点指针，返回根结点指针void output(Node *root); /获得处理后的字符串bool isError(char); /判断字符是否有问题void deal(); /对字符数组进展处理double value(string); / 计算后缀表达式，得到其结果。int main()Node* root=NULL;cout输入中缀表达式：;cin.getline(array,40);deal();root=crtTree(root);cout输出后缀表达式：;output(root);4 / 11coutstr
10、endl;cout输出后缀表达式的值：;if(value(str)!=0)coutfixedsetprecision(2)value(str)endl;elsecoutA Wrong Input!endl;return 0;/将数字字符存入一个结点，并返回数字字符的后一个符号char getOp(Node *temp)int i=0;if( isError(arraycount) )exit(0);while(arraycount=0|arraycount=.)temp-chi=arraycount;i+;count+;temp-chi=0;count+;return arraycount-1
11、;/传入根结点指针，返回根结点指针Node* crtTree(Node* root) Node *p,*q;char op;if(root=NULL)root=new Node;p=new Node;op=getOp(root);while(op!=)q=new Node;q-ch0=op;q-ch1=0;switch(op)case +:case -:q-lChild=root;root=q;p=new Node;op=getOp(p);root-rChild=p;5 / 11break;case *:case /:if(root-ch0=+|root-ch0=-)p=new Node;st
12、rcpy(p-ch,root-ch);p-lChild=root;p-rChild=q;op=getOp(root);root=p; else q-lChild=root;root=q;p=new Node;op=getOp(p);root-rChild=p; break;case (:p=root;while(p-rChild)p=p-rChild;if(p-lChild=NULL) p-lChild=crtTree(p-lChild); /递归创建括号里的指针op=arraycount;count+;break; elsep-rChild=crtTree(p-rChild); /递归创建括
13、号里的指针op=arraycount;count+;break;case ):return root;return root;/传入根结点，后序遍历,赋值给另一个字符数组主要是为了给后序的计算表达式值提供方便void output(Node *root)int n;if(root)output(root-lChild);6 / 11output(root-rChild);n=0;while(root-chn!=0)strk+=root-chn+;strk+= ;bool isError(char ch) /判断每个字符是否有错if(ch!=+&ch!=-&ch!=*&ch!=/&!(ch=0)
14、&ch!=.&ch!=(&ch!=)cout 字符错误！;return true;return false;void deal() /对字符数组进展处理int i=0,n=0;while(arrayi)if(arrayi= |arrayi=)i+;arrayn+=arrayi+;arrayn+=;arrayn=0;double value(string s2) / 计算后缀表达式，得到其结果。 stack s; double x,y; int i = 0;while(i =2)x = s.top(); s.pop(); x += s.top(); s.pop(); i+; break;else
15、return 0;case -:if(s.size()=2)x = s.top(); s.pop(); x =s.top()-x; s.pop(); i+; break;7 / 11 elsereturn 0;case *:if(s.size()=2)x = s.top(); s.pop(); x *= s.top(); s.pop(); i+; break; elsereturn 0;case /:if(s.size()=2)if( s.top()=0) return 0;elsex = s.top(); s.pop(); x = s.top()/x; s.pop(); i+; break;
16、 elsereturn 0;default :x = 0;while(0 = s2i&s2i = 9)x = x*10+s2i - 0;i+;if(s2i = .)double k = 10.0;y = 0;i+;while(0 = s2i&s2i = 9)y += (s2i-0)/k);i+;k *= 10;x += y;break; if(x!=0)s.push(x); if( s.size()=1 )return s.top();elsereturn 0;8 / 112 2、利用堆栈来实现中缀表达式转换为后缀表达式。、利用堆栈来实现中缀表达式转换为后缀表达式。#include #incl
17、ude #include #include using namespace std;int cmp(char ch) / 运算符优先级 switch(ch) case +: case -: return 1; case *: case /: return 2; default : return 0; void change(string &s1, string &s2) / 中缀表达式转变后缀表达式 stack s; s.push(#); int i = 0; while(i = cmp(s1i) ) s2 += s.top(); s2 += ; s.pop(); s.push(s1i); i
18、+; 9 / 11 else /级别四 while(0 = s1i&s1i = 9|s1i = .) s2 += s1i+; s2 += ; while(s.top() != #) /最后一步 s2 += s.top(); s2 += ; s.pop(); double value(string &s2) / 计算后缀表达式，得到其结果。 stack s; double x,y; int i = 0; while(i =2) x = s.top(); s.pop(); x += s.top(); s.pop(); i+;break; else return 0;case -: if(s.siz
19、e()=2)x = s.top(); s.pop(); x =s.top()-x; s.pop(); i+;break; else return 0;case *: if(s.size()=2)x = s.top(); s.pop(); x *= s.top(); s.pop(); i+;break; else return 0;case /: if(s.size()=2)x = s.top(); s.pop(); x = s.top()/x; s.pop(); i+;break; else return 0; default : x = 0; while(0 = s2i&s2i = 9) x
20、 = x*10+s2i - 0; i+; if(s2i = .) double k = 10.0;10 / 11 y = 0; i+; while(0 = s2i&s2i = 9) y += (s2i-0)/k); i+; k *= 10; x += y; break; s.push(x); if( s.size()=1 )return s.top();elsereturn 0;int main() string s1,s2; couts1;s2=;change(s1,s2);if(value(s2) cout输出 1后缀表达式 ：; couts2endl; cout输出 2表达式的值 ：; coutfixedsetprecision(2)value(s2)endl;elsecoutA wrong input!endl; return 0;11 / 11
