/*
 * tree_examples.cpp
 *
 *  Created on: 28.11.2013
 *      Author: trifon
 */

#include <iostream>
#include <cmath>
#include "mtree.cpp"
#include "binary_tree.cpp"
using namespace std;

typedef BinaryTree<int> IntTree;

template <typename T>
int breadth(MTree<T> const& t) {
	int b = 0;
	int max = 0;
	for(typename MTree<T>::I it = t.iterator(); it; ++it) {
		int n = breadth(*it);
		if (n > max)
			max = n;
		b++;
	}
	// b - брой на поддърветата на t

	if (b > max)
		max = b;
	return max;
}


void testMTree() {
	MTree<int> t = 1;
	MTree<int> t2 = 2;
	MTree<int> t4 = 4;
	MTree<int> t6 = 6;
	t2.addChild(MTree<int>(3)).addChild(MTree<int>(3)).addChild(MTree<int>(3)).addChild(MTree<int>(3));
	t4.addChild(MTree<int>(5));
	t.addChild(t2);
	t.addChild(t4);
	t.addChild(t6);
	cout << t << endl;

	typedef MTree<int> IMTree;

	cout << IMTree(1)
				.addChild(IMTree(2).addChild(IMTree(3)))
				.addChild(IMTree(4).addChild(IMTree(5)))
				.addChild(IMTree(6)) << endl;

	cout << breadth(t) << endl;
}

void testBinaryTree() {
	IntTree empty, t4(4, empty, empty), t5(5, empty, empty),
			t6(6, empty, empty), t2(2, t4, t5),
			t3(3, empty, t6), t1(1, t2, t3);
	cout << "t1: " << t1 << endl;
	cout << "t4: " << t4 << endl;
}

void createFullTree(IntTree& t, int n) {
	if (n == 0)
		return;
	IntTree left, right;
	createFullTree(left, n - 1);
	createFullTree(right, n - 1);
	t = IntTree(n, left, right);
}



template <typename T>
int depth(BinaryTreeIterator<T> it) {
	if (!it)
		return 0;
	return 1 + fmax(depth(++it), depth(it++));
}

template <typename T>
int countNodes(BinaryTreeIterator<T> it) {
	if (!it)
		return 0;
	return countNodes(++it) + countNodes(it++) + 1;
}

template <typename T>
bool equalTrees(BinaryTreeIterator<T> it1, BinaryTreeIterator<T> it2) {
	/*
	if (!it1 && !it2)
		return true;
	// it1 - валиден или it2 - валиден
	if (!it1 || !it2)
		return false;
	if (*it1 != *it2)
		return false;
	return equalTrees(++it1, ++it2) && equalTrees(it1++, it2++);
	*/
	return (!it1 && !it2) ||
		   (it1 && it2 && equalTrees(++it1, ++it2)
					   && equalTrees(it1++, it2++));

}

void testFullTree() {
	IntTree t;
	createFullTree(t, 4);
	cout << t << endl;
	cout << depth(t.iterator()) << endl;
	cout << countNodes(t.iterator()) << endl;
	IntTree empty;
	IntTree t2(4, empty, empty);
	cout << equalTrees(t.iterator(), t2.iterator()) << endl;
}

/*
 * <израз> ::= <цифра> | ( <израз> <операция> <израз> )
 * <операция> ::= + | - | * | /
 */
void createExpressionTree(BinaryTree<char>& t, istream& is) {
	char c;
	is >> c;
	if (c >= '0' && c <= '9')
		t = BinaryTree<char>(c);
	else {
		BinaryTree<char> lt, rt;
		createExpressionTree(lt, is);
		is >> c;
		createExpressionTree(rt, is);
		t = BinaryTree<char>(c, lt, rt);
		is >> c;
	}
}

int calculateExpressionTree(BinaryTreeIterator<char> it) {
	if (*it >= '0' && *it <= '9')
		return *it - '0';
	int la = calculateExpressionTree(++it);
	int ra = calculateExpressionTree(it++);
	switch (*it) {
	case '+': return la + ra;
	case '-': return la - ra;
	case '*': return la * ra;
	case '/': return la / ra;
	}
}

void calculateExpression() {
	BinaryTree<char> t;
	createExpressionTree(t, cin);
	cout << t << endl;
	cout << calculateExpressionTree(t.iterator()) << endl;
}

int main() {
	// testMTree();
	// testBinaryTree();
	// testFullTree();
	calculateExpression();
	cout << "Alive\n";
	return 0;
}