#define ResultType double
#include<iostream>
#include<vector>
#include<string>
using namespace std;
/*********************建立表达式二叉树************/ 
//定义表达式树
typedef int TreeElemType;
typedef struct TreeNode {
	TreeElemType data;//可以将运算符转化储存，通过分辨左右孩子指针分辨是否是叶子节点，记得初始化！ 
	struct TreeNode* left;
	struct TreeNode* right;
}TreeNode;
//算符优先级比较表 
char CList[7][7] =
{
	{ '>','>','<','<','<','>','>' },
	{ '>','>','<','<','<','>','>' },
	{ '>','>','>','>','<','>','>' },
	{ '>','>','>','>','<','>','>' },
	{ '<','<','<','<','<','=',' ' },
	{ '>','>','>','>',' ','>','>' },
	{ '<','<','<','<','<',' ','=' },
};//注意等号的处理 
string Op = "+-*/()#";//方便用数组
bool In(char ch){
	int i=0;
	while(ch!=Op[i])
	{i++;if(i>=7) break;}
	return i<7;	
}
void CreateExpTree(ExpTree &T, TreeNode* left, TreeNode* right, TreeElemType data)//建立叶子节点 
{
	T = new TreeNode;
	T->data = data;
	T->left = left;
	T->right = right;
}
//将数值型字符串转换成int型数字
int Atoi(string str)
{
	int res = 0;
	for(int i=0;i<str.size();i++)
		res = res * 10 + (str[i]-'0');
	return res;
}
//判断算符优先级
char Precede(char c1, char c2)
{
	int i = 0, j = 0;
	while (Op[i] && Op[i] != c1)
		i++;
	while (Op[j] && Op[j] != c2)
		j++;
	return CList[i][j];//i行j列 
}
//表达式树的创建算法
TreeNode* InitExpTree()
{
	vector<TreeNode> eTStackNode;//树栈 
	vector<char> chStackNode;//算符栈
	chStackNode.push('#');
	char ch;
	while(ch!='#'||chStackNode.pop()!='#')//取反为退出条件 
	{
		if(!In(ch))//输入的是数字 
		{
			string num="";//定义在内部，每轮更新 
			num+=ch;	cin>>ch;
			while(!In(ch)){
				num+=ch; cin>>ch;
			} //最后输入的是符号，注意程序的进行
			TreeNode* T;
			CreateExpTree(T,NULL,NULL,Atoi(num));//NULL,NULL叶子节点 
			eTStackNode.push_back(T);
		}
		else{
			switch(Precede(chStackNode.back(),ch)){
				case '<':
					chStackNode.push_back(ch);
					cin>>ch;
					break;
				case '>':
					char temp_char=chStackNode.back();chStackNode.pop_back();
					TreeNode* temp1=eTStackNode.back();eTStackNode.pop_back();
					TreeNode* temp2=eTStackNode.back();eTStackNode.pop_back();
					TreeNode* T;
					CreateExpTree(T,temp1,temp2,temp_char);
					eTStackNode.push_back(T);
					break;
				case '=':
					chStackNode.push_back(ch);
					cin>>ch;
					break;
			}
		}
	}
	return eTStackNode.back();
}