Balancear parenteses

9 de maio de 2009 4 respostas

raqh 9 de maio de 2009

Olá pessoal!

Estou a tentar fazer um programa para balencear parenteses…mas apesar de não ter erros, não funciona bem. Em todos os casos ele diz que a expressão está bem balenciada :roll:

Envio-vos o meu código. Alguém me poderia ajudar?

Obrigado.

public interface Stack { public Object push(int i); public Object pop(); public boolean isEmpty(); }

class PilhaArray implements Stack 
{
	Object[] pilha;
	int inicio;
	
	public PilhaArray() 
	{
		pilha = new Object[100];
		inicio=-1;
	}
	
	
	public boolean isEmpty() 
	{
		return inicio == -1;
	}
	
	
	public Object push(int item) 
	{
		if (inicio==pilha.length-1)  
		{
			pilha[++inicio] = item;
		}
		
		return item;
	} 
	

	public Object pop() 
	{
		
		if(!isEmpty())
		{
			inicio--;
		}
			
		return pilha[inicio];
	}
}

import java.io.*;
   
   public class BalenPararenteses 
   {
   
     public static boolean verificarParen(String s) 
    {
       PilhaArray stack = new PilhaArray ();     
   
       for (int i = 0; i < s.length()-1; i++) 
	{
		switch (s.charAt(i)) 
		{
			case '(':
					stack.push(new Character ('('));
			break;
			case '[':
					stack.push(new Character ('['));
			break;

			case '{':
					stack.push(new Character ('{'));

			break;
			case ')':
					Character c = (Character) stack.pop();
					if (!match(c.charValue(), s.charAt(i))) return false;
			break;
			case ']':
				
					c = (Character) stack.pop();
					if (!match(c.charValue(), s.charAt(i))) return false;
			break;
			case '}':
					c = (Character) stack.pop();
					if (!match(c.charValue(), s.charAt(i))) return false;
			break;
			default:
			break;
		}
       }
   
       if ( stack.isEmpty())
		return true;
	else 
		return false ;
    
     }
   

     public static boolean match(char lpar, char rpar) {
       switch (lpar) {
       case '(': return rpar == ')';
       case '[': return rpar == ']';
       case '{': return rpar == '}';
       default: return false;
       }
     }
   
   
     public static void main(String[] args) throws IOException 
     {
	BufferedReader stdr;  
	stdr = new BufferedReader(new InputStreamReader(System.in));
   
	String line = stdr.readLine();   
	while (line != null) {
         if (verificarParen(line))
           System.out.println("well parenthesized");
         else
           System.out.println("parenthesis mismatch");
   
         line = stdr.readLine();   
       }
     }
   }

4 Respostas

maschiojv 9 de mai. de 2009

Algumas observações: Já existe uma classe Stack em java (java.util.Stack) que faz a mesma coisa que a tua classe PilhaArray. veja as observações que eu fiz no meio do código

public interface Stack {

  //return void: o retorno não era usado para nada
  //int para Character porque estava dando ClassCastException com o int
  public void push(Character i);

  //character para não ter que ficar fazendo cast
  public Character pop();

  public boolean isEmpty();
}

class PilhaArray implements Stack {

  private Character[] pilha;
  private int inicio;

  public PilhaArray() {
    pilha = new Character[100];
    inicio = -1;
  }

  public boolean isEmpty() {
    return inicio == -1;
  }

  public void push(Character item) {
    //você está apenas colocando, não tem que ter condição para colocar, apenas coloque :)
    pilha[++inicio] = item;
  }

  public Character pop() {
    
    //verificar para evitar IndexO...Exception
    if (!isEmpty()) {
      return pilha[inicio--];
    }
    else {
      return null;
    }
  }
}

import java.io.*;

public class BalenPararenteses {

  public static boolean verificarParen(String s) {

    PilhaArray stack = new PilhaArray();

    for (int i = 0; i < s.length() - 1; i++) {

      switch (s.charAt(i)) {

        case '(':
          stack.push(new Character('('));
          break;
        case '[':
          stack.push(new Character('['));
          break;
        case '{':
          stack.push(new Character('{'));
          break;
        case ')':
          //não precisa mais de cast
          Character c = stack.pop();
          //se for diferente de null eh pq tem mais parenteses fechando doque abrindo
          if (c == null || !match(c.charValue(), s.charAt(i))){
            return false;
          }
          break;
        case ']':
          c = stack.pop();
          if (c == null || !match(c.charValue(), s.charAt(i))){
            return false;
          }
          break;
        case '}':
          c = stack.pop();
          if (c == null || !match(c.charValue(), s.charAt(i))) return false;
          break;
        default:
          break;
      }
    }

    if (stack.isEmpty()) {
      return true;
    }
    else {
      return false;
    }

  }

  public static boolean match(char lpar, char rpar) {

    switch (lpar) {
      case '(':
        return rpar == ')';
      case '[':
        return rpar == ']';
      case '{':
        return rpar == '}';
      default:
        return false;
    }
  }

  public static void main(String[] args) throws IOException {

    BufferedReader stdr = new BufferedReader(new InputStreamReader(System.in));

    String line = stdr.readLine();
    while (line != null) {

      if (verificarParen(line)) {
        System.out.println("well parenthesized");
      }
      else {
        System.out.println("parenthesis mismatch");
      }

      line = stdr.readLine();
    }
  }
}

maschiojv 10 de mai. de 2009

E como eu realmente não tinha o que fazer, eu refiz o teu programinha de uma maneira, digamos, mais java 5

obs: eu tirei as outras classe porque, como eu disse, já existe uma que faz isso.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

public class BalenPararenteses {

  private static final List<Character> abridores = new ArrayList<Character>(Arrays.asList('(', '[', '{'));
  private static final List<Character> fechadores = new ArrayList<Character>(Arrays.asList(')', ']', '}'));

  public static boolean verificarParen(String s) {

    Stack<Character> stack = new Stack<Character>();

    for (char c : s.toCharArray()) {

      //se o caractere esta abrindo
      if (abridores.contains(c)) {
        stack.push(c);
      }
      //se o caractere esta dechando
      else if (fechadores.contains(c)) {

        if(stack.isEmpty()){
          //se está vazio é porque está fechando mais que abrindo
          return false;
        }

        Character abridorCorrespondente = abridores.get(fechadores.indexOf(c));
        if (!abridorCorrespondente.equals(stack.pop())) {
          return false;
        }
      }
    }

    return stack.isEmpty();
  }

  public static void main(String[] args) throws IOException {

    BufferedReader stdr = new BufferedReader(new InputStreamReader(System.in));

    String line;
    do{
      line = stdr.readLine();

      if (verificarParen(line)) {
        System.out.println("well parenthesized");
      } else {
        System.out.println("parenthesis mismatch");
      }
    }
    while (line != null);
  }
}

raqh 10 de mai. de 2009

Olá! Muito obrigado pela ajuda já funciona! :D

Como a classe PilhaArray agora está correcta, pensei que não ia ter mais problemas por exemplo num programa que faça o calculo de uma expressao no formato postfix. Mas ele retorna um erro que não estou a conseguir corrigir. :roll:
Quando na excução ponho 5 9 8 + 4 6 * * 7 + *, ele retorna uma excepção:

Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
at PilhaArray.pop(PilhaArray.java:
at Postfix.CalculPostFix(Postfix.java:
at Postfix.main(Postfix.java:

Aqui vai a minha classe Postfix:

//CLASSE POSTFIX
import java.io.*;

public class Postfix
{
    public static void CalculPostFix(String s2)
    {
        PilhaArray s = new PilhaArray ();  
        
        for (int i = 0; i < s2.length(); i += 2)
        {
            if (s2.charAt(i) == '+')
                s.push(s.pop() + s.pop());
            else if (s2.charAt(i) == '*')
                s.push(s.pop() * s.pop());
            else
            {
                int num = 0;
                do
                {
                    num = num*10 + s2.charAt(i)-'0'; // Constrói número
                    ++i;
                }
                while (s2.charAt(i) != ' ');
                --i;
                s.push(num);
            }
        }
        
        System.out.println(s.pop());
    }
    

      public static void main(String[] args) throws IOException
     {
      BufferedReader stdr = new BufferedReader(new InputStreamReader(System.in));
  
       String line = stdr.readLine();    
       CalculPostFix(line);
     }
}

//INTERFACE STACK
public interface Stack
{
     public void push(int i);
    public int pop();  
    public boolean isEmpty();
}

//CLASSE PILHAARRAY
public class PilhaArray implements Stack
{
    private int[] stack;
    private int n;
    
    public PilhaArray()
    {
        stack = new int[1000000];
        n=-1;
    }
    
    
    public boolean isEmpty()
    {
        return n == -1;
    }
    
    
    public void push(int item)
    {
       
            stack[++n] = item;
        
    }
    

    public int pop() {
        if (!isEmpty()) {
        int item = stack[n--];
        return item;}
    }

}

Obrigado

maschiojv 10 de mai. de 2009

Como eu disse, já existe uma classe que faz isso, e ela funciona direitinho. Veja o ultimo post que eu mandei, nele não é usado a sua PilhaArray. Eu uso java.util.Stack, você deveria usar ela também e esquecer essa PilhaArray.

Criado 9 de maio de 2009

Ultima resposta 10 de mai. de 2009

Respostas 4

Participantes 2

4 Respostas

Topicos relacionados