当前位置:首页 >> 计算机软件及应用 >>

四则运算表达式求值(栈+二叉树,c++版)


数据结构——实验报告

HUNAN

UNIVERSITY

课程实习报告



目:

四则运算表达式求值 周华毅
201308010411

学生姓名: 学生学号: 专业班级: 指导老师: 完成日 期 :

计科 1304 吴帆 2015/5/1

1 / 11

数据结构——实验报告

一、需求分析 a) 四则运算表达式求值, 将四则运算表达式用中缀表达式表示, 然后转换为后缀表达 式,并计算结果。 b) 本程序要求利用二叉树后序遍历来实现表达式的转换, 同时可以使用实验 2 的结果 来求解后缀表达式的值。 c) 在字符界面上输入一个中缀表达式,回车表示结束。如果该中缀表达式正确,那么 在字符界面上输出其后缀表达式, 其中后缀表达式中两相邻操作数之间利用空格隔 开;如果不正确,在字符界面上输出表达式错误提示。 d) 测试数据 输入: 21+23*(12-6) 输出: 21 23 12 6 -*+ 二、概要设计 抽象数据类型 为实现上述程序的功能,应以字符串存储用户的输入,以及计算出的结果。 算法的基本思想 根据题目要求, 利用二叉树后序遍历来实现表达式的转换。 该算法的基本模块包括二叉 树的建立以及如何把输入的中缀表达式利用二叉树后序遍历转化为后缀表达式。 1、首先要将输入的中缀表达式(数字字符)存入到二叉树中,由于存在两位或者两位 以上的数,甚至还有小数,所以考虑用字符型指针存储数字字符和操作符。 2、为了便于将中缀表达式存入二叉树中,在录入中缀表达式后,要进行相应的处理, 比如去掉空格符,添加结束标志,如‘=’ 、 ‘#’等。 3、中缀表达式存入到二叉树的过程中,要注意处理的顺序,如‘+’ 、 ‘-’号的优先级 比‘*’ 、 ‘/’号的 低,当遇到‘*’ 、 ‘/’号时,要判断树以上的节点中是否有‘+’ 、 ‘ -’ 号,有的话要与其交换位置。遇到‘ (’时要反复创建二叉树的结点,构建子二叉树,考虑 到括号内要处理的步骤可能会较多,可以考虑用递归。遇到‘) ’时则直接结束此子二叉树 的建立。此外二叉树中叶子结点存储操作数,非叶子结点存储操作码。 4、对创建好的二叉树进行后序遍历,即可得到相应的后缀表达式,实现方法可以用递 归的方式, 由于后面还要计算表达式的值, 故便利的过程中要将结点中得到的数据存入新的 字符数组中。 程序的流程 程序由三个模块组成: (1) 输入模块:完成一个中缀表达式的输入,存入字符串数组 array[Max]中。 (2) 计算模块:设计一个建立二叉树的函数,Node* crtTree(Node* root),传入根结 点指针, 返回根结点指针 ,该函 数的实现还要反复使用另 一个函 数 char getOp(Node *temp),其将数字字符存入一个结点,并返回数字字符的后一个符 号。 void deal() 函数功能是对字符数组进行处理。 void output(Node *root); 函数功能是获得处理后的字符串,也就是中缀表达式转化为的后缀表达式。 (3) 输出模块:如果该中缀表达式正确,那么在字符界面上输出其后缀表达式和表 达式的值;如果不正确,在字符界面上输出表达式错误提示。 三、详细设计 物理数据类型
2 / 11

数据结构——实验报告

题目要求输入的四则运算表达式运算符只有加减乘除, 操作数有整数和小数, 为了能够 存储,采用 C 语言中的字符串数组。 char ch[Max]; 算法的时空分析 算法的运行时间主要耗费在二叉树的建立过程中。 可以发现, 每当遇到一个运算符或操 作数时,都要调用一次函数 char getOp(Node *temp),来将其存入二叉树的结点中,其中也 会遇到递归的情况,但耗时可以忽略。所以假设输入的字符串中字符个数为 N,则算法的时 间复杂度为 O(N)。 输入和输出的格式 输入 本程序可以将输入的四则运算表达式(中缀表达式)转换为后缀表达式 //提示 请输入四则运算表达式://提示 等待输入 输出 //提示 后缀表达式为://输出结果的位置 表达式的值为://输出结果的位置 四、调试分析 本次实验的难点主要是在建立二叉树的问题上。关于如何把中缀表达式存入二叉树中, 我参考了网上的一些方法, 成功实现了目标, 但是却遇到了一个问题, 那就是不能处理小数, 甚至两位或两位以上的整数。 因为如果采用字符数组来存储操作数, 运算符合一位整数还可 以处理,但对于两位数就就会出问题,最后我改进采用字符串数组来存储操作数,成功解决 了问题。 另外在处理输入的非法表达式问题中,我也费了很大功夫,但总体问题不大。 五、测试结果

六、用户使用说明(可选) 1、本程序的运行环境为 DOS 操作系统 2、运行程序时 提示输入四则运算表达式 本程序可以将中缀表达式转化为后缀表达式,并计算结果 请输入四则运算表达式: 输出 后缀表达式为: 表达式的值为: 七、附录(可选)
3 / 11

数据结构——实验报告

程序源代码(c++) 1、利用二叉树后序遍历来实现表达式的转换: #include<iostream> #include<string> #include<stack> #include<iomanip> const int Max=100; using namespace std; class Node{ public: char ch[Max]; //考虑到数值有时会是两位数,所以使用字符串数组 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 array[Max]; //保存原始的中缀表达式 static char str[2*Max]; //保存后序遍历出来的字符串,为表达式求值提供方便 static int k=0; char getOp(Node *temp); //temp 指针保存每个结点,返回的是运算符 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); cout<<str<<endl;
4 / 11

数据结构——实验报告

cout<<"输出后缀表达式的值:"; if(value(str)!=0) cout<<fixed<<setprecision(2)<<value(str)<<endl; else cout<<"A Wrong Input!"<<endl; return 0; } //将数字字符存入一个结点,并返回数字字符的后一个符号 char getOp(Node *temp){ int i=0; if( isError(array[count]) ) exit(0); while(array[count]<='9'&&array[count]>='0'||array[count]=='.'){ temp->ch[i]=array[count]; i++; count++; } temp->ch[i]='\0'; count++; return array[count-1]; } //传入根结点指针,返回根结点指针 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->ch[0]=op; q->ch[1]='\0'; switch(op) { case '+': case '-': q->lChild=root; root=q; p=new Node; op=getOp(p); root->rChild=p; break;
5 / 11

数据结构——实验报告

case '*': case '/': if(root->ch[0]=='+'||root->ch[0]=='-'){ p=new Node; strcpy(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=array[count]; count++; break; } else{ p->rChild=crtTree(p->rChild); //递归创建括号里的指针 op=array[count]; count++; break; } case ')': return root; } } return root; } //传入根结点, 后序遍历,赋值给另一个字符数组 (主要是为了给后序的计算表达式值提供方 便) void output(Node *root){ int n; if(root){ output(root->lChild); output(root->rChild);
6 / 11

数据结构——实验报告

n=0; while(root->ch[n]!='\0') str[k++]=root->ch[n++]; str[k++]=' '; } } bool isError(char ch){ //判断每个字符是否有错 if(ch!='+'&&ch!='-'&&ch!='*'&&ch!='/'&&!(ch<='9'&&ch>='0')&&ch!='.'&&ch!='('&&ch!=')'){ cout << "字符错误!"; return true; } return false; } void deal(){ //对字符数组进行处理 int i=0,n=0; while(array[i]){ if(array[i]==' '||array[i]=='=') i++; array[n++]=array[i++]; } array[n++]='='; array[n]='\0'; } double value(string s2){ // 计算后缀表达式,得到其结果。 stack < double> s; double x,y; int i = 0; while(i < s2.length() ){ if(s2[i] == ' ') i++; switch(s2[i]) { 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;
7 / 11

数据结构——实验报告

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){ if( s.top()==0) return 0; else{ x = s.top(); s.pop(); x = s.top()/x; s.pop(); i++; break; } } else return 0; default : x = 0; while('0' <= s2[i]&&s2[i] <= '9'){ x = x*10+s2[i] - '0'; i++; } if(s2[i] == '.'){ double k = 10.0; y = 0; i++; while('0' <= s2[i]&&s2[i] <= '9'){ y += ((s2[i]-'0')/k); i++; k *= 10; } x += y; } break; } if(x!=0) s.push(x); } if( s.size()==1 ) return s.top(); else return 0; } 2、利用堆栈来实现中缀表达式转换为后缀表达式。
8 / 11

数据结构——实验报告

#include <iostream> #include <string> #include <stack> #include <iomanip> 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 <char> s; s.push('#'); int i = 0; while(i < s1.length()){ //分成四个级别来检验中缀表达式 //s1.length()是为了 s1 的 长度,不包括\0 if(s1[i] == '(') //级别一 s.push(s1[i++]); else if(s1[i] == ')'){ //级别二 while( s.top() != '(' ){ s2 += s.top(); s2 += ' '; s.pop(); } s.pop(); i++; }else if( s1[i] == '+'||s1[i] == '-'||s1[i] == '*'||s1[i] == '/' ){ //级别三 while( cmp(s.top()) >= cmp(s1[i]) ){ s2 += s.top(); s2 += ' '; s.pop(); } s.push(s1[i]); i++; } else{ //级别四 while('0' <= s1[i]&&s1[i] <= '9'||s1[i] == '.'){ s2 += s1[i++];
9 / 11

数据结构——实验报告

} s2 += ' '; } } while(s.top() != '#'){ s2 += s.top(); s2 += ' '; s.pop(); } //最后一步

} double value(string &s2){ // 计算后缀表达式,得到其结果。 stack <double> s; double x,y; int i = 0; while(i < s2.length()-1){ // 由于 s2 的最后一位是空格,影响判断,所以用 s2.length()-1 if(s2[i] == ' ') i++; switch(s2[i]) { 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; 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' <= s2[i]&&s2[i] <= '9'){ x = x*10+s2[i] - '0'; i++; } if(s2[i] == '.'){ double k = 10.0; y = 0; i++; while('0' <= s2[i]&&s2[i] <= '9'){ y += ((s2[i]-'0')/k); i++; k *= 10; }
10 / 11

数据结构——实验报告

x += y; } break; } } s.push(x); } if( s.size()==1 ) return s.top(); else return 0; } int main(){ string s1,s2; cout<<"输入(中缀表达式) :"; cin>>s1; s2=""; change(s1,s2); if(value(s2)){ cout<<"输出 1(后缀表达式) :"; cout<<s2<<endl; cout<<"输出 2(表达式的值) :"; cout<<fixed<<setprecision(2)<<value(s2)<<endl; } else cout<<"A wrong input!"<<endl; return 0; }

11 / 11


相关文章:
四则运算表达式求值(栈+二叉树,c++版).doc
四则运算表达式求值(栈+二叉树,c++版)_计算机软件及应用_IT/计算机_专业
四则运算表达式求值.doc
四则运算表达式求值_数学_自然科学_专业资料。数据...后缀表达式可以用二叉树来实现, 因为如果二叉树的中...(c++) 利用二叉树后序遍历来实现表达式的转换: /*...
数据结构 四则运算表达式求值 实验四报告.doc
数据结构 四则运算表达式求值 实验四报告_电脑基础知识_IT/计算机_专业资料。用...顶的值 int length() const; //的长度 算法的基本思想 构建二叉树,把...
四则运算表达式求值.doc
先出的原则, 采用来实现 四则运算表达式的求值。...(2) 算法基本思想: 用二叉树来存储四则表达式, ...C++四则运算表达式求值算... 14页 1下载券 程序...
湖南大学数据结构试验3四则运算表达式求值.doc
要求对四则运算表达式求值,将四则运算表达式用中缀表达式表示,然后转 换为后缀...类型:c++标准容器 stack 容器 2.根据二叉树的特点,T 即为该二叉树的名称...
实验4四则运算表达式求值.doc
问题描述 四则运算表达式求值,将四则运算表达式用中缀表达式,然后转换为后缀表达式...输入模块:输入一个运算式( 2) 计算模块:利用进行表达式的计算,二叉树来存储...
数据结构实验报告五四则运算表达式求值.doc
数据结构实验报告五四则运算表达式求值_工学_高等教育_教育专区。C++数据结构...三、详细设计物理数据类型 程序含有两个类,其中不再赘述,另一个类为二叉树 ...
四则运算表达式求值.doc
表达树,将得到中缀表达式;后序遍历表达式树,将得到 后缀表达式,而使用对后序表达式求取较为方便 因此,获取的四则运算表达式使用线性表临时存储,再转存至二叉树...
四则运算表达式求值实验报告.doc
值为://输出结果的位置 三、调试分析 本次实验的难点主要是在建立二叉树的...请输入四则运算表达式: 输出 后缀表达式为: 表达式的值为: 程序源代码(c++) ...
数据结构实验4四则运算表达式求值实验报告.doc
HUNAN UNIVERSITY 课程实验报告 题目:四则运算表达式求值 学生姓名: 学生学号: ...抽象数据类型定义一个二叉树,用来存储用户输入的表达式。表达式通过定义一个 来...
湖南大学数据结构四则运算表达式报告.doc
数据结构实验报告 实验 4 四则运算表达式求值 背景 在工资管理软件中,不可避免...,操作 符弹出,同时弹出两个操作数,建立二叉树,根节点压入操作数的 。 Bin...
四则运算表达式求值_图文.pdf
后缀遍历二叉树 编码实现和静态检查 上机调试及测试...{//建立叶子节点并入 PTR i+=CrtNode(PTR, &...四则运算表达式求值 6页 免费 C++四则运算表达式...
数据结构实验报告四则运算表达式求值.doc
数据结构实验报告四则运算表达式求值_工学_高等...操作数本身又为表 达式.后缀遍历二叉树码实现和...如果试图从中弹出两个元素是, 该中并没有, ...
四则运算式_图文.ppt
问题描述 四则运算表达式求值,将四则运算表达式用 中缀表达式,然后转换为后缀...后序遍历二叉树,得到后缀表达式的形式。 计算后缀表达式的值,使用,已在前面...
实验四 四则运算表达式求值.doc
c); DestroyBiTree(&T); DeleteChild(T, p, LR); 经过二叉树的后序遍历后的表达式惊醒运算是满足后进先出的原则, 采用来实现四则 运算表达式求值。 数...
四则运算c++实现.doc
一、需求分析 1.利用二叉树后序遍历来实现表达式的...c++创建的 全部过程,让我的这个小组对的了解有...C++四则运算表达式求值算... 14页 1下载券 【C++...
C语言实现一.二叉树操作 二.用栈实现算术表达式求值 课....pdf
实现算术表达式求值 课设报告_电子/电路_工程...颗二叉树,并输 出这棵树的深度,结果如图: 四、...c语言,c++算数表达式求值... 18页 免费 数据结构...
c语言实现一.二叉树操作 二.用栈实现算术表达式求值 课....doc
c语言实现一.二叉树操作 二.用栈实现算术表达式求值...c语言,c++算数表达式求值... 18页 免费 数据结构...四则运算表达式求值(栈+... 11页 1下载券 二叉...
四则运算实验报告.doc
实验3 四则运算表达式求值背景在工资管理软件中, 不可避免的要用到公式的定义...*递归构造中缀表达式转化为的二叉树(利用栈) */ void InorderCreate(BiTree...
表达式求值.doc
《数据结构(C++版) 》课设计报告 20122013 学年...顶元素(并不删除) int Empty( ); //判断...实现对算术四则混合运算表达式求值,并仿照课本上的...
更多相关标签: