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

1、课程实习报告Word资料题 目：四则运算表达式求值学生姓名：周华毅学生学号:201308010411专业班级：计科1304指导老师：吴帆完成日期：2015/5/1 一、需求分析a)四则运算表达式求值，将四则运算表达式用中缀表达式表示，然后转换为后缀表达式，并计算结果。b)本程序要求利用二叉树后序遍历来实现表达式的转换，同时可以使用实验2的结果来求解后缀表达式的值。c) 在字符界面上输入一个中缀表达式，回车表示结束。如果该中缀表达式正确，那么在字符界面上输出其后缀表达式，其中后缀表达式中两相邻操作数之间利用空格隔 开；如果不正确，在字符界面上输出表达式错误提示。d)测试数据 输入： 21+23*

2、 (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、其后缀表达式和表 达式的值；如果不正确，在字符界面上输出表达式错误提示。三、详细设计物理数据类型题目要求输入的四则运算表达式运算符只有加减乘除，操作数有整数和小数， 为了能够存储，采用C语言中的字符串数组。char chMax;算法的时空分析算法的运行时间主要耗费在二叉树的建立过程中。可以发现，每当遇到一个运算符或操作数时，都要调用一次函数 char getOp（Node *temp） ,来将其存入二叉树的结点中，其 中也会遇到递归的情况，但耗时可以忽略。所以假设输入的字符串中字符个数为N,则算法的时间复杂度为O（N）。输入和输出的格式输入本程序可以将输入的四则运算表达式（中缀表达式）转换为后

6、缀表达式提示请输入四则运算表达式：提示 等待输入输出提示后缀表达式为：输出结果的位置表达式的值为：输出结果的位置四、调试分析本次实验的难点主要是在建立二叉树的问题上。关于如何把中缀表达式存入二叉树中， 我参考了网上的一些方法， 成功实现了目标，但是却遇到了一个问题， 那就是不能处理小数， 甚至两位或两位以上的整数。因为如果采用字符数组来存储操作数，运算符合一位整数还可以处理，但对于两位数就就会出问题，最后我改进采用字符串数组来存储操作数，成功解决了问题。另外在处理输入的非法表达式问题中，我也费了很大功夫，但总体问题不大。五、测试结果输人中缓表达式：21M3*（12川）谕出后舞表达式，21 23

7、 12 6 - * + 谕出后缀表达式的值；159.001-_- _I_I . 、 输入中缀莪达式:11*(18-5.3)-32/1.6愉出后缀表达式；2.1 1S 5. 3 - * 32 1.6 / -输出后缀表达式的值；e.67_ -18- H_1_I I_I_I II_|_| 瑜人申缴表达式士 +2的输出后缀表达式;2 3%十输出后缀未达式的值；2Wrcng Input! 一 _I -t- _I_. 六、用户使用说明（可选）1、本程序的运行环境为 DOS操作系统2、运行程序时提示输入四则运算表达式本程序可以将中缀表达式转化为后缀表达式，并计算结果请输入四则运算表达式：输出后缀表达式为:

8、表达式的值为:七、附录（可选）程序源代码（C+ ）1、利用二叉树后序遍历来实现表达式的转换: #include<iostream> #include<string>#include<stack> #include<iomanip> const int Max=100;using namespace std; class Nodepublic:char chMax;考虑到数值有时会是两位数，所以使用字符串数组Node* lChild;Node* rChild;Node()strcpy(ch,"");lChild=rChild=N

9、ULL;Node()if(lChild!=NULL) delete lChild;if(rChild!=NULL) delete rChild;static int count=0;/保存原始的中缀表达式保存后序遍历出来的字符串，为表达式求值提供方便/temp 指针保存每个结点，返回的是运算符/传入根结点指针，返回根结点指针/获得处理后的字符串/判断字符是否有问题/对字符数组进行处理/计算后缀表达式，得到其结果。static char arrayMax;static char str2*Max;static int k=0;char getOp(Node *temp);Node* crtTre

10、e(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;cout<<"输出后缀表达式的值："if(value(

11、str)!=0)cout<<fixed<<setprecision(2)<<value(str)<<endl;elsecout<<"A Wrong Input!"<<endl;return 0;将数字字符存入一个结点，并返回数字字符的后一个符号char getOp(Node *temp)int i=0;if( isError(arraycount)exit(0);while(arraycount<='9'&&arraycount>='0'|ar

12、raycount='.') temp->chi=arraycount;i+;count+;temp->chi尸0'count+;return arraycount-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->ch0=op;q->ch1='0'switch(op)case 

13、9;+':case '-':q->lChild=root;root=q;p=new Node;op=getOp(p);root->rChild=p;break;casel*1case '/':if(root->ch0='+'|root->ch0='-') p=new Node; strcpy(p->ch,root->ch); p->lChild=root; p->rChild=q; op=getOp(root); root=p; else q->lChild=root;

14、 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); 递归创建括号里的指针op=arraycount; count+; break;cas

15、e ')': return root; return root; 传入根结点，后序遍历，赋值给另一个字符数组(主要是为了给后序的计算表达式值提供 方便)void output(Node *root)int n;if(root)output(root->lChild);output(root->rChild);n=0;while(root->chn!='0')strk+=root->chn+;strk+尸；bool isError(char ch) /判断每个字符是否有错if(ch!='+'&&ch!=

16、9;-'&&ch!='*'&&ch!=7'&&!(ch<='9'&&ch>='0')&&ch!=.'&&ch!='(' &&ch!=')')cout << "字符错误！"return true;return false;void deal()/对字符数组进行处理int i=0,n=0;while(arrayi)if(arrayi='

17、; '|arrayi='=')i+;arrayn+=arrayi+;arrayn+='='arrayn='0'double value(string s2)/计算后缀表达式，得到其结果。stack < doubles;double x,y;int i = 0;while(i < s2.length() )if(s2i='')i+;switch(s2i)case '+':if(s.size()>=2)x = s.top(); s.pop(); x += s.top(); s.pop(); i

18、+; break;elsereturn 0;case '-':if(s.size()>=2)x = s.top(); s.pop(); x =s.top()-x; s.pop(); i+; break;elsereturn 0;casel*1if(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(

19、); x = s.top()/x; s.pop(); i+; break;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 +=

20、 y;break;if(x!=0)s.push(x);if( s.size()=1 )return s.top();elsereturn 0;2、利用堆栈来实现中缀表达式转换为后缀表达式。#include <iostream>#include <string>#include <stack>#include <iomanip> using namespace std;int cmp(char ch)switch(ch)/运算符优先级case '+': case '-': return 1;case '*&#

21、39;: 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的长度，不包括0if(s1i='(')s.push(s1i+);else if(s1i = ')') while( s.top() != '(')s2 += s.top();s2 +=''s.

22、pop();/中缀表达式转变后缀表达式分成四个级别来检验中缀表达式/s1.length()/级别一/级别二是为了s.pop();i+;/级别三else if( s1i = '+'|s1i = '-'|s1i = '*'|s1i = '/' )while( cmp(s.top() >= cmp(s1i) )s2 += s.top();s2 +=''s.pop();s.push(s1i);i+;else/级别四while('0' <= s1i&&s1i <= '

23、9'|s1i = '.')s2 += s1i+;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.length()-1if(s2i='') i+；switch(s2i)/最后一步/计算后缀表达式，得到其结果。/由于s2的最后一位是空格，影响判断，所以用x = s.top(); s.pop(); x += s.top(); s.pop(); i+;case '+': if(s.size()>=2)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.t