//測試數據?前綴表達式?-?/?*?+?1?3?4?5?6
//?????????中綴表達式?（?1?+?3?）?*?4?/?5?-?6?#
//?????????后綴表達式?1?3?+?4?*?5?/?6?-?#
#define?_CRT_SECURE_NO_WARNINGS
#include
#include
#include
#include
#include
using?namespace?std;

class?BinaryTreeNode?{
public:
	string?element;
	int?position;
	BinaryTreeNode?*leftChild?*rightChild;
	BinaryTreeNode（）?{
		leftChild?=?rightChild?=?NULL;
	}
	BinaryTreeNode（string?elem）?{
		element?=?elem;
		leftChild?=?rightChild?=?NULL;
	}
	bool?isLeaf（）?{
		return?leftChild?==?NULL?&&?rightChild?==?NULL;
	}
};

class?BinaryTree?{
private:
	BinaryTreeNode?*?mRoot;
	int?priority（char?op）?{
		switch?（op）?{
		case‘+‘:
		case‘-‘:
			return?1;
			break;
		case‘*‘:
		case‘/‘:
			return?2;
			break;
		default:
			return?3;
		}
	}
	string?MtoB（）?{//中綴表達式轉為后綴表達式
		char?c;
		stack?s;
		int?num;
		s.push（‘#‘）;
		ostringstream?exp;
		for?（;;）?{
			cin?>>?c;
			if?（c?>=?‘0‘?&&?c?<=?‘9‘）?{
				cin.putback（c）;
				cin?>>?num;
				exp?<			}
			else?if?（c?==?‘（‘）?{
				s.push（‘（‘）;
			}
			else?if?（c?==?‘）‘）?{
				while?（s.top（）?!=?‘（‘）?{
					exp?<					s.pop（）;
				}
				if?（s.top（）?==?‘（‘）
					s.pop（）;
			}
			else?if?（c?==?‘#‘）?{
				while?（s.top（）?!=?‘#‘）?{
					exp?<					s.pop（）;
				}
				break;
			}
			else?{
				while?（s.top（）?!=?‘#‘?&&?s.top（）?!=?‘（‘&&?priority（s.top（））?>=?priority（c））?{
					exp?<					s.pop（）;
				}
				s.push（c）;
			}
		}
		exp?<		return?exp.str（）;
	}
	string?PtoB（）?{//前綴表達式轉為后綴表達式
		char?c[20];
		string?a?b;
		scanf（“%s“?c）;
		if?（*c?==?‘+‘?||?*c?==?‘-‘?||?*c?==?‘*‘?||?*c?==?‘/‘）?{
			a?=?PtoB（）;
			b?=?PtoB（）;
			return?a?+?‘?‘?+?b?+?‘?‘?+?*c;
		}
		else?return?c;
	}
	void?setpostion（BinaryTreeNode*?root?int?pos?int?k）?{
		if?（root?==?NULL）return;
		root->position?=?pos;
		setpostion（root->leftChild?pos?-?k?/?2?k?/?2）;
		setpostion（root->rightChild?pos?+?k?/?2?k?/?2）;
	}
public:
	BinaryTree（）?{?mRoot?=?NULL;?}
	void?set（BinaryTreeNode*?root）?{
		mRoot?=?root;
	}
	BinaryTreeNode*?BulitbyBack（string?expression）?{
		stack?s;
		BinaryTreeNode*?p;
		char?c;
		int?n;
		istringstream?exp（expression）;
		char?i?=?0;
		for?（;;）?{
			exp?>>?c;
			if?（c?>=?‘0‘&&c?<=?‘9‘）?{
				exp.putback（c）;
				exp?>>?n;
				p?=?new?BinaryTreeNode（to_string（n））;
				s.push（p）;
			}
			else?if?（c?==?‘+‘?||?c?==?‘-‘?||?c?==?‘*‘?||?c?==?‘/‘）?{
				char?op[2]?=?{?c‘\0‘?};
				p?=?new?BinaryTreeNode（op）;
				p->rightChild?=?s.top（）;//先彈出的作右子樹
				s.pop（）;
				p->leftChild?=?s.top（）;//后彈出的做左子樹
				s.pop（）;
				s.push（p）;
			}
			else?if?（c?==?‘#‘）?{
				break;
			}
			else?assert（0）;
		}
		return?s.top（）;
	}