#include <iostream>
#include <fstream>
#include <string>
#include <stdlib.h>
#include <stack>

enum  Operator  { Plus , Minus , Multiply , Divide , None };

ostream&  operator<< ( ostream& out , const Operator& op ) {
	if ( op == Plus )
		out << "+"  ;
	else if ( op == Minus )
		out << "-"  ;
	else if ( op == Multiply )
		out << "*"  ;
	else if ( op == Divide )
		out << "/"  ;
	return out ;
}

template <class T>
struct Node {
	Operator  op ;
	T         no ;
	Node<T>  *left , *right ;
	Node( const T& num )         : no(num), op(None)  { left = right = NULL ; }
	Node( const Operator& oper ) : op(oper) { left = right = NULL ; }
};

int op_pri(Operator op) {
	if( op == Plus || op == Minus) { return 1; }
	else if (op == Multiply || op == Divide ) { return 2; }
}

template <class T>
class  Expression_Tree {
	Node<T> *root;
	private:
		char expression[1024];

		Node<T> * infix(char *s, int &index) {
			int j;
			char buf[1024];
			Node<T> *tmp;
			stack<Node<T>*> ops;
			stack<Node<T>*> nos;

			while(s[index] != 0) {

				// trim spaces
				for(;s[index] == ' '; index++);

				// copy to buf
				for(j = 0; s[index] != 0 && s[index] != ' '; index++, j++) {
					buf[j] = s[index];
				}
				buf[j] = 0;

				if(buf[j - 1] >= '0' && buf[j - 1] <= '9'){
					tmp = new Node<T> (atoi(buf));
					nos.push(tmp);
				} else if (buf[j - 1] == '(') {
					index++;
					tmp = infix(s, index);
					nos.push(tmp);
				} else if (buf[j - 1] == ')') {
					while( !ops.empty() ) {
						(ops.top())->right = nos.top();
						nos.pop();
						(ops.top())->left = nos.top();
						nos.pop();
						nos.push(ops.top());
						ops.pop();
					}
					if(s[index] != 0) { index++; }
					return nos.top();
				} else {
					switch(buf[j - 1]) {
					case '+': tmp = new Node<T> (Plus); break;
					case '-': tmp = new Node<T> (Minus); break;
					case '*': tmp = new Node<T> (Multiply); break;
					case '/': tmp = new Node<T> (Divide); break;
					};

					while (!ops.empty() && op_pri(tmp->op) <= op_pri((ops.top())->op)) {
						(ops.top())->right = nos.top();
						nos.pop();

						(ops.top())->left = nos.top();
						nos.pop();

						nos.push(ops.top());
						ops.pop();
					}
					ops.push(tmp);
				}

				// trim spaces
				for(;s[index] == ' '; index++);
			}

			while( !ops.empty() ) {
				(ops.top())->right = nos.top();
				nos.pop();
				(ops.top())->left = nos.top();
				nos.pop();
				nos.push(ops.top());
				ops.pop();
			}
			return nos.top();

		}

		struct Node<T> * postfix(char *s) {
			int j, index = 0;
			char buf[1024];
			Node<T> *tmp;
			stack<Node<T>*> nos;

			while(s[index] != 0) {
				// trim spaces
				for(;s[index] == ' '; index++);

				// copy to buf
				for(j = 0; s[index] != 0 && s[index] != ' '; index++, j++) {
					buf[j] = s[index];
				}
				buf[j] = 0;

				if(buf[j - 1] >= '0' && buf[j - 1] <= '9'){
					tmp = new Node<T> (atoi(buf));
					nos.push(tmp);
				} else {
					switch(buf[j - 1]) {
					case '+': tmp = new Node<T> (Plus); break;
					case '-': tmp = new Node<T> (Minus); break;
					case '*': tmp = new Node<T> (Multiply); break;
					case '/': tmp = new Node<T> (Divide); break;
					};
					tmp->right = nos.top();
					nos.pop();
					tmp->left = nos.top();
					nos.pop();
					nos.push(tmp);
				}
				// trim spaces
				for(;s[index] == ' '; index++);
			}
			return nos.top();
		}

		void show_tree(Node<T> *r, int d) {
			for(int i = 1; i < d; i++) {
				cout << "     ";
			}

			if( r->op != None) {
				cout << (d==0?"":"|==> ") << r->op << endl;
				if(r->right != NULL) { show_tree(r->right, d + 1); }
				if(r->left != NULL) {show_tree(r->left, d + 1); }
			} else {
				cout << (d==0?"":"|--> ") << r->no << endl;
			}

		}
		
		T evaluate_tree(Node<T> *r) {
			if( r->op != None) {
				T L, R;
				L = evaluate_tree(r->left);
				R = evaluate_tree(r->right);
				switch( r->op ) {
				case Plus : return L + R;
				case Minus : return L - R;
				case Multiply : return L * R;
				case Divide : return L / R;
				};
			}
			return r->no;
		}

	public:
		void establish_tree_from_infix(string filename) {
			int index = 0;
			ifstream in;
			in.open(filename.c_str());
			in.getline(expression, 1024);
			root = infix(expression, index);
		}

		void establish_tree_from_postfix(string filename) {
			ifstream in;
			in.open(filename.c_str());
			in.getline(expression, 1024);
			root = postfix(expression);
		}

		void print_tree_expression() {
			show_tree(root, 0);
		}

		T evaluate_expression() {
			return evaluate_tree(root);
		}
};

int main() {

	string  filename1 = "infix_expression_file" ;
	string  filename2 = "postfix_expression_file" ;

	Expression_Tree<int>  foo ;

	foo.establish_tree_from_infix( filename1 ) ;
	foo.print_tree_expression() ;
	cout << "\n> value : " << foo.evaluate_expression() << endl << endl ;

	foo.establish_tree_from_postfix( filename2 ) ;
	foo.print_tree_expression() ;
	cout << "\n> value : " << foo.evaluate_expression() << endl ;

}