import java.util.ArrayList;

public class MyExpressionTree {
	private MyNode<Character> r;
	private MyNode<MyExpressionTree> root;
	private MyNode<MyExpressionTree> left;
	private MyNode<MyExpressionTree> right;
	private ArrayList<Character> expression;

	public MyExpressionTree(ArrayList<Character> e) {
		expression = e;
	}

	private MyExpressionTree(MyNode<Character> x) {
		r = x;
	}

	private MyExpressionTree(MyNode<MyExpressionTree> a,
			MyNode<MyExpressionTree> b, MyNode<MyExpressionTree> c) {
		root = a;
		left = b;
		right = c;
	}

	public void run() {
		buildTree();
	}

	public void buildTree() {
		MyStack<MyExpressionTree> m = new MyStack<MyExpressionTree>();
		for (int i = 0; i < expression.size(); i++) {
			if (!isOperator(expression.get(i))) {
				MyNode<Character> node = new MyNode<Character>(
						expression.get(i));
				m.push(new MyExpressionTree(node));
			} else {
				MyNode<MyExpressionTree> T1 = new MyNode<MyExpressionTree>(
						m.pop());
				MyNode<MyExpressionTree> T2 = new MyNode<MyExpressionTree>(
						m.pop());
				MyNode<Character> node = new MyNode<Character>(
						expression.get(i));
				MyExpressionTree r = new MyExpressionTree(node);
				MyNode<MyExpressionTree> newRoot = new MyNode<MyExpressionTree>(
						r);
				MyExpressionTree tree = new MyExpressionTree(newRoot, T2, T1);
				m.push(tree);
			}
		}
	}

	public boolean isOperator(char x) {
		if (x == '+' || x == '-' || x == '*' || x == '/')
			return true;
		else
			return false;
	}

	public boolean isLeaf(MyNode<MyExpressionTree> t) {
		if (t.getLeftChild() == null && t.getRightChild() == null)
			return true;
		else
			return false;
	}

	public int evaluate(MyNode<MyExpressionTree> n){
		if (n != null) {
			if (isLeaf(n))
				return Integer.parseInt(n.getElement().toString());
			else {
				int leftChild = evaluate(n.getLeftChild());
				int rightChild = evaluate(n.getRightChild());
				char root = n.getElement().toString().charAt(0);
				return calculate(leftChild, root, rightChild);
			}
		}
		return 0;
	}
	public int calculate(int a, char b, int c) {
		int result = 0;
		if (b == '+') {
			result = a + c;
		} else if (b == '-') {
			result = a -c;
		} else if (b == '*') {
			result = a * c;
		} else {
			result = a / c;
		}
		return result;
	}
}