/**
 * @author RafaelM
 *
 * TODO To change the template for this generated type comment go to
 * Window - Preferences - Java - Code Style - Code Templates
 */
public class Avaliador {
	
	public static int maxi(int a, int b){
		if(a > b){
			return a;
		}else{
			return b;
		}
	}
		
	public static int contarParentesis(char array[],int inicio, int fim){
		int i;
		int numeroParentese = 0;
		for(i = inicio; i < fim ; i++){
			
			if(array[i] == '('){
				
				numeroParentese++;
				
			}else if (array[i] == ')'){
				
				numeroParentese--;
				
			}else
				
				continue;
		}
		return numeroParentese;
	}
	
	//metodo que verifica se uma expressao é bem formada
	public static boolean expressaoBemFormada(char array[],int inicio, int fim){
		int j = acharOperadorPrincipal(array,inicio,fim);
		if(inicio == fim){
			
			if( (array[inicio] == 'x') || (array[inicio] == 'y') || (array[inicio] == 'z') || (array[inicio] == '0')
					|| (array[inicio] == '1') ){
				
				return true;
				
			}else{
				
				return false;
				
			}
		}else if ((fim - inicio) == 1){
			
			return false;
			
		}else if( j == -1){
			
			return false; // caso o operador principal não ser achado
			
		}else if( contarParentesis(array,inicio,fim+1) != 0 ){
			
			return false;
			
		}else if(array[j] == '-'){
			
			return ((expressaoBemFormada(array,j+1,fim-1)));
			
		}
		return ( (expressaoBemFormada(array,inicio + 1,(j - 1))) && (expressaoBemFormada(array,j + 1,fim - 1)) ) ;
	}

	public static int acharOperadorPrincipal(char[] array, int inicio, int fim){
		int i;
		int resp = -1;
		int parentesesAbertos = 0;
		int parentesesFechados = 0;
		for(i = (inicio + 1);i<(fim -1);i++){
			if( (array[i] == '.') || (array[i] == '-') || (array[i] == '+') ){
				if( (parentesesAbertos - parentesesFechados) == 0){
					resp = i;
					break;
				}
				
			}else{
				if(array[i] == '('){
					parentesesAbertos++;
				}else if (array[i] == ')'){
					
					parentesesFechados++;
				}else
					continue;
			}			
		}
		return resp; //se chegar aqui é porque a expressao eh mal formada		
	}
	
	//metodo que calcula o numero de operadores
	public static int numeroOperadores(char array[], int inicio, int fim){
		int j = acharOperadorPrincipal(array,inicio,fim);
		if(inicio == fim){
			
			return 0;
			
		}else if (array[j] == '-'){
			
			return (1 + numeroOperadores(array,j + 1,fim - 1));
			
		}else{
			return(1 + numeroOperadores(array,inicio + 1,j-1) + numeroOperadores(array,j + 1,fim - 1));
		}
	}
	
	//método que calcula a altura da arvore
	public static int posto(char array[],int inicio, int fim){
		int j = acharOperadorPrincipal(array,inicio,fim);
		if(inicio == fim){
			
			return 0;
			
		}else if(array[j] == '-'){
			
			return (1 + posto(array,j + 1,fim - 1));
			
		}else{
			
			return ( 1 + maxi(posto(array,inicio + 1,j - 1),posto(array,j+1,fim-1)) );
		}
	}
	
	//função que lista todas as subexpressões
	public static String subExpressoes(char array[], int inicio, int fim){
		int j = acharOperadorPrincipal(array,inicio,fim);
		String s = new String(array,inicio,(fim-inicio)+1);
		if(inicio == fim){
			
			return ((array[inicio])+", ");
			
		}else if(array[j] == '-'){
			
			return ( (subExpressoes(array,j + 1,fim - 1)) +s+", " );
		
		}else{
			return ( (subExpressoes(array,inicio + 1,j - 1)) +(subExpressoes(array,j + 1,fim - 1))
					+s+", ");
		}
	}
	
	public static String tirarVirgula(String expressao){
		char array[] = expressao.toCharArray();
		String s = new String (array,0,expressao.length()-2);
		return s;
		
	}
	
	public static void main(String[] args) {
		
		Arquivo arq = new Arquivo("Entrada", "Saida");
		String expressao;
		expressao = arq.readString();
		char array[] = expressao.toCharArray();
		if( (expressaoBemFormada(array,0,array.length - 1)) ){
			arq.println("Expressao bem-formada");
			arq.println("Altura da arvore: " +posto(array,0,array.length-1));
			arq.println("Sub-expressoes: " +tirarVirgula(subExpressoes(array,0,array.length-1)));
			arq.println("Numero de operadores: " +numeroOperadores(array,0,array.length-1));
		}else{
			arq.println("Expressao mal-formada");
		}		
						
	}
}