2019-11-17

code / c++

10 分钟读完 (大约 1560 个字)

Binary Tree Calculator

1.基本思路

Binary tree calculator也就是使用二叉树实现计算器的功能，相信大家以前都使用栈实现过计算器功的能，使用两个栈分别存数字与字符，一边计算一边“pop”、“push”，或是先将输入的中缀表达式转为后缀表达式，之后运算。而我们的Binary tree calculator则也需要用到栈，先将中缀表达式转为后缀表达式，之后使用指针栈构建Expression tree，再利用二叉树节点之间的关系递推遍历计算即可。

2.中缀表达式转后缀表达式

那么怎么才能将中缀表达式转为后缀表达式呢？我们来看下面一个例子。

a+b*(c-d)/e

上述则为一个中缀表达式，它的后缀表达式如下：

abcd-*e/+

我们利用栈来实现这个过程：

(1)若遇到数字直接输出。

(2)若遇到字符(‘+’、’-‘、’*’、’/‘),对比栈顶元素的优先级，如果比栈顶元素优先级高，则直接入栈，否则将栈中元素不断出栈，直到出现优先级比存入字符低，则将字符入栈。

(3)若字符为’(‘,则直接入栈，若遇到‘)’，则将‘(’前的元素弹出。

(4)若扫描完成后栈中还有元素滞留，则将栈中元素全部弹出。

为了使得大家清晰可见看懂，实现过程的图片每一步兔子都将它画了出来，所以图片有一点多……

3.构建Expression tree

我们将每一个数或符号都看做一个节点，在此基础上构建Expression tree。

创建一个指针栈，遍历后缀表达式，若遇到数字则作为一个节点存入指针栈，若遇到符号则取出栈中两个节点作为此节点的左右儿子，再将节点存入栈中，以此类推。当后缀表达式被完全遍历后，栈中将只存在一个节点指针，此指针则为树的根节点。

由于a-d都为数字则直接存入栈中不再重复作图

4.计算Expression tree

我们已经建立好了Expression tree，现在我们只需要计算出值就可以完成我们的Binary tree calculator了！

那么…..要怎么计算呢？

兔子思考了一下，发现可以使用递归的方法计算答案！

我们从树的根节点开始从上往下遍历，每遇到一个符号则在使用此函数返回与符号相符的运算式，直到遇到数字则返回数字本身的值。

例如，根节点为‘+’，则return 计算'+'的左节点的值 + 计算'+'右节点的值，而为了得到左右节点的值，函数会继续运算，当遇到‘+’的左儿子则return a，当遇到右儿子‘/’则会继续返回左右儿子的计算值return计算'/'的左节点的值 / 计算'/'右节点的值,而为了得到左右节点的值，函数会继续运算，当遇到左儿子‘*’则会继续返回左右儿子的计算值return计算 * 的左节点的值 * 计算 * 右节点的值,而为了得到左右节点的值，函数会继续运算，当遇到 * 的左儿子则return b，当遇到右儿子‘-’则会继续返回左右儿子的计算值return计算'-'的左节点的值 - 计算'-'右节点的值,而为了得到左右节点的值，函数会继续运算，当遇到‘-’的左儿子则return c，当遇到右儿子则 return d,当遇到‘/’的右儿子则return e.

经历了层层的递归返回，我们将得到最终表达式答案！

5.完整代码

#include<iostream>
#include<stack>
#include<cmath>
using namespace std;
double QAQ(string pe)
{
	double num1=0;
	double num2=0;
	int size = 0;
	int f = 1;
	for(int i = 0; i < pe.length(); i++)
	{
		if(pe[i] == '.') 
		{
			f = 0;
			continue;
		}
		if(f) num1 = num1 * 10 + pe[i] - '0';
		else
		{
			num2 = num2 * 10 + pe[i] - '0';
			size ++;
		}
	}
	return (num1 + num2 / pow(10,size)); 
}
void ppe(string ix,string &pe)//中缀转后缀 
{
	stack<char> QWQ;
	for(int i = 0; i < ix.length(); i++)
	{
		if((ix[i] <= '9' && ix[i] >= '0') || ix[i] == '.')
		{
			while((ix[i] <= '9' && ix[i] >= '0') || ix[i] == '.')
			{
				pe += ix[i];
				i++;
			}
			pe +=' ';
			i--;
		}//数字直接放 
		else if((ix[i] == '+' || ix[i] == '-'))
		{
			if(QWQ.empty() || QWQ.top() == '(')
			{
				QWQ.push(ix[i]);
			}
			else
			{
				while(!QWQ.empty())
				{
					if(QWQ.top() == '(') break;
					pe += QWQ.top();
					QWQ.pop();
				}
				QWQ.push(ix[i]);
			}
		}
		else if((ix[i] == '*' || ix[i] == '/'))
		{
			if(QWQ.empty() || QWQ.top() == '+' || QWQ.top() == '-')
			{
				QWQ.push(ix[i]);
			}
			else
			{
				while(!QWQ.empty())
				{
					if(QWQ.top() == '+'|| QWQ.top() == '-'|| QWQ.top() == '(') break;
					pe += QWQ.top();
					QWQ.pop();
				}
				QWQ.push(ix[i]);
			}
		}
		else if(ix[i] == '(')
		{
			QWQ.push(ix[i]);
		}
		else if(ix[i] == ')')
		{
			while(QWQ.top() != '(')
			{
				pe += QWQ.top();
				QWQ.pop();
			}
			QWQ.pop();
		}
	}
	while(!QWQ.empty())
	{
		pe += QWQ.top();
		QWQ.pop();
	}
	cout << pe << endl; 
}
struct tree
{
	string data;
	tree *left;
	tree *right;
};//一棵树 
void insert(string value,stack<tree *> &ss,int flag)// 
{
	tree *t = new tree();
	t -> data = value;
	t -> left = NULL;
	t -> right = NULL;
	if(!ss.empty() && flag)
	{
		tree *p1 = ss.top();
		ss.pop();
		tree *p2 = ss.top();
		ss.pop();
		t -> left = p2;
		t -> right = p1;
	}	
	ss.push(t);
} 
tree *creat_tree(string pe,stack<tree *> &ss)//建立表达式树 
{	
	for(int i = 0; i < pe.length(); i++)
	{
		string num_ex = "";
		string ch_ex = "";
		
		if((pe[i] <= '9' && pe[i] >= '0') || pe[i] == '.')
		{
			while(pe[i] != ' ')
			{
				num_ex += pe[i];
				i++;
			}
			insert(num_ex, ss,0);
		}
		else 
		{	
			ch_ex += pe[i];
			insert(ch_ex, ss,1);
		}	
	}
	tree *tmp = ss.top();
	return ss.top();
}
double Calculator(tree *t)//计算器 
{
	if(t -> data == "+") return Calculator(t -> left) + Calculator(t -> right);
	else if(t -> data == "-") return Calculator(t -> left) - Calculator(t -> right);
	else if(t -> data == "*") return Calculator(t -> left) * Calculator(t -> right);
	else if(t -> data == "/") return Calculator(t -> left) / Calculator(t -> right);
	else return QAQ(t -> data);
} 
int main()
{
	string ix;
	string pe;
	stack<tree *> ss;//指针栈 
	cin >> ix;
	ppe(ix,pe);
	cout << Calculator(creat_tree(pe,ss)) << endl;
	return 0;
}

# data structure