将通过二叉链表实现的表达式二叉树进行输出, 同时计算出结果.
要求:
1)二叉树建立时, 使用先序建立;
2)四个运算符包括:+, -, *, /;
3 ) 在输出时, 遇到优先级问题时, 相应的括号也要输出.
提示:
1)递归执行下列步骤即可求值: 先分别求出左子树和右子树表示的子表达式的值, 最后根据根结点的运算符的要求, 计算出表达式的最后结果.
2)二叉树的中序遍历序列与原算术表达式基本相同, 但是需要将中序序列加上括号, 即当根结点运算符优先级高于左子树 (或右子树) 根结点运算符时, 就需要加括号.
例如:
输入 | Result |
---|---|
-+3@@*2@@-4@@1@@/6@@2@@ | 3+2*(4-1)-6/2=6 |
*3@@+/6@@2@@-3@@1@@ | 3*(6/2+3-1)=15 |
本题可以利用谦虚遍历以及中序遍历的特点来实现
详见代码.
一, 首先构建二叉树:
- class Node
- {
- friend Tree;
- public:
- Node():Lc(NULL),Rc(NULL) {}
- Node(char d,Node *l=NULL,Node *r=NULL)// 析构函数, 设定优先级
- {
- data=d;
- Lc=l;
- Rc=r;
- if (data>= '0' && data <= '9')
- num = data - '0', op = 0;
- else if (data == '*')
- op = 3;
- else if (data == '+')
- op = 1;
- else if (data == '-')
- op = 1;
- else if (data == '/')
- op = 3;
- }
- private:
- Node *Lc,*Rc;
- char data;
- int num,op;
- };
- class Tree
- {
- public:
- friend Node;
- Tree():root(NULL) {}
- Tree(char value )// 析构函数
- {
- Trv=value;
- root = NULL;
- }
- private:
- Node *root;// 根节点
- char Trv;
- };
二, 输入表达式
- void input(Node *&p)
- {
- char d;
- cin>>d;
- if(d!='@')
- {
- p = new Node(d);// 前插法
- input(p->Lc);
- input(p->Rc);
- }
- else
- {
- p=NULL;
- }
- }
三, 进行计算输出(主要)
- int LVR(Node *p)// 中序遍历
- {
- if(p->op==0)// 如果操作数为 0, 为数字, 返回运算结果
- {
- cout<<p->data;
- return p->num;
- }
- else // 否则进行运算
- {
- int a;// 对左子树进行运算
- if(p->Lc->op&&p->Lc->op<p->op)// 如果左孩子操作数存在, 并且优先级高于本身则输出括号
- {
- printf("(");
- a=LVR(p->Lc);// 递归括号内容并进行计算
- printf(")");
- }
- else
- {
- a=LVR(p->Lc);// 否则进行递归计算
- }
cout<<p->data; 输出等式
- int b;// 同左子树
- if(p->Rc->op&&p->Rc->op<p->op)
- {
- printf("(");
- b=LVR(p->Rc);
- printf(")");
- }
- else
- {
- b=LVR(p->Rc);
- }
- if(p->data=='+')
- {
- return a+b;
- }// 进行计算 +, 同时 return 结果
- else if(p->data=='-')
- {
- return a-b;
- }// 进行计算 -, 同时 return 结果
- else if(p->data=='*')
- {
- return a*b;
- }// 进行计算 *, 同时 return 结果
- else if(p->data=='/')
- {
- return a/b;
- }// 进行计算 /, 同时 return 结果
- }
- }
四, 程序介绍:
本程序主要利用了递归, 前序遍历, 中序遍历的特点来实现表达式的求知. 对于刚刚学习的同学来说可能稍微难理解, 一些简单的注释有助于大家理解.
本人水平很低, 复习数据结构对原来的代码进行整理.
欢迎批评指正
来源: https://www.cnblogs.com/shdwin/p/11066963.html