package trees.exprtrees;

import java.util.Scanner;
import java.util.ArrayDeque;
import java.util.Queue;
import trees.genericBinaryTrees.*;

/* This program uses recursion to buid an expression tree
 * of an arithmetic expression in infix notation.
 */
public class ExpressionTreeDemo {

	// Êëàñ çà ïðåäñòàâÿíå íà îïåðàöèèòå
	static enum Operation {
		L_BRACE ("("),
		PLUS	("+"),
		MINUS	("-"),
		MULT	("*"),
		DIV		("/"),
		R_BRACE ("(");
		
		private final String symbol;
		
		Operation(String s) {
			this.symbol = s;
		}
		
		public String toString() {
			return symbol;
		}
	}
	
	static char lookahead;
	static Scanner sc = new Scanner(System.in);
	static String input = sc.nextLine();
	static int ind = 0;
	
	static Queue<Object> lexer() throws Exception {
		ArrayDeque<Object> result = new ArrayDeque<Object>();  // Âåêòîð çà ïîëó÷àâàíå íà ðåçóëòàòà
		int val = 0;
		lookahead = getC();
		do {  // öèêúë çà ÷åòåíå íà ëåêñåìèòå îò âõîäà
			if (Character.isDigit(lookahead)){ // ÷åòåíà íà ëåêñåìà - ÷èñëî
				val = lookahead-'0';
				while (Character.isDigit(lookahead = getC()))
					val = val*10+lookahead-'0';
				result.add(new Integer(val)); // äîáàâÿíå íà ÷èñëîòî âúâ âåêòîðà
			}
			else {  // ÷åòåíå íà ëåêñåìà - îïåðàöèÿ
				switch(lookahead) {  // äîáàâÿíå íà îïåðàöèÿòà â ñòåêà
					case '(': result.add(Operation.L_BRACE); break;
					case '+': result.add(Operation.PLUS); break;
					case '-': result.add(Operation.MINUS); break;
					case '*': result.add(Operation.MULT); break;
					case '/': result.add(Operation.DIV); break;
					case ')': result.add(Operation.R_BRACE); break;
					default: throw new Exception("Error in expression"); 
				}		
				lookahead = getC();
			}
		} while (lookahead != '$');
		return result;
	}
	
	static char getC() {
	    try {
	    	while(Character.isWhitespace(input.charAt(ind++)));
	    	return input.charAt(ind-1);
	    }
	    catch (Exception e) {
	    	return '$';
	    }
	}
	
	static BinaryTree<Object> parser(Queue<Object> input) {
		BinaryTree<Object> result = expression(input);
		if(input.size() != 0) {  
			throw new IllegalArgumentException();    
		} 
		return result;
	}
	
	static BinaryTree<Object> expression(Queue input) { 
		BinaryTree<Object> result = term(input); 
		while(isAditive((Operation)input.peek())) {    
			BinaryTree<Object> arg1 = result;  
			result = new BinaryTree<Object>(input.poll());  
			BinaryTree<Object> arg2 = term(input);      
			result.setLeft(arg1);    
			result.setRight(arg2);    
		}     
		return result; 
	}
	
	static BinaryTree<Object> term(Queue input) {    
		BinaryTree<Object> result = factor(input);  
		while(isMultiplicative((Operation)input.peek())) {       
			BinaryTree<Object> arg1 = result;   
			result = new BinaryTree<Object>(input.poll());  
			BinaryTree<Object>  arg2 = factor(input);      
			result.setLeft(arg1);    
			result.setRight(arg2);  
		}      
		return result;  
	}
	
	static BinaryTree<Object> factor(Queue input){   
		Object token = input.poll();    
		if(isL_BRACE(token)) {      
			BinaryTree<Object> result = expression(input);  
			token = input.poll();      
			if(!isR_BRACE(token))      
				throw new IllegalArgumentException();    
			return result;    
		}       
		if(!isNumber(token))   
			throw new IllegalArgumentException();   
		return new BinaryTree<Object>(token); 
	}
	
	static boolean isAditive(Object op) {
		if(! (op instanceof Operation))
			return false;
		return op == Operation.PLUS || op == Operation.MINUS;
	}
	
	static boolean isMultiplicative(Object op) {
		if(! (op instanceof Operation))
			return false;
		return op == Operation.MULT || op == Operation.DIV;
	}
	
	static boolean isL_BRACE(Object op) {
		if(! (op instanceof Operation))
			return false;
		return op == Operation.L_BRACE;
	}
	
	static boolean isR_BRACE(Object op) {
		if(! (op instanceof Operation))
			return false;
		return op == Operation.R_BRACE;
	}
	
	static boolean isNumber(Object num) {
		return num instanceof Integer;
	}
	
	public static void main(String[] args) {
		BinaryTree<Object> t = null;
		try {
			t = parser(lexer());
		} catch (Exception e) {
			e.printStackTrace();
		}
		System.out.println(t.toString());
	}

}