Balanceamento de parenteses

[araqh]

Olá pessoal!

Estou a tentar fazer um programa que verifique o balanceamento de parenteses...mas apesar de não ter erros, não funciona bem.... Ele diz sempre que os parenteses da expressão estao correctamente balanceados....

Envio-vos aqui 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();   
       }
     }
   }

 

[blueomega]

so uns reparos

for (int i = 0; i < s.length()-1; i++) não deve ter o -1, ou usas o <=

nos pop tu comparas o símbolo que obtiveste no pop com o da stack, naturalmente que vão ser diferentes

quando verificas ')' supostamente no pop deves ter '(', logo ao fazer match da falso, negado da positivo e assim retorna falso. da falso sempre(independentemente do obtido no pop)

não precisavas de implementar a stack, podes criar uma stack que aceite caracteres

 

[araqh]

Olá! Obrigado pela tua resposta. Pois o -1 inicialmente não tinha posto mas se não puser quando executo há uma excepção: Exception in thread "main" java.lang.ArrayIndexOutOfBoundsException: -1
Assim que ponho o -1....ela já não aparece. Como tem < não precisa do -1, mas entao de onde vem essa excepção?
Em relação ao pop, podes me explicar como posso corrigir isso?

Mais uma vez obrigado.

 

[napalm]

Tens uma série de erros no código:

Pq é que fazes push de inteiros e pop de objectos???
Além disso com a comparação que estavas a fazer nenhum objecto era introduzido.

Correcções:

    public Object push(Object item) {
        if (inicio != pilha.length - 1) {
            pilha[++inicio] = item;
        }

        return item;
    }

    public Object pop() {

        if (!isEmpty()) {
            return pilha[inicio--];
        }
        return null;
    }

No ciclo for não percorres a string toda, fica a faltar o último carácter.
Correcção:

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

De resto está fixe. Não faria da mesma maneira, mas desde que funcione

 

[araqh]

yupiiii, muito obrigada pela ajuda, já está a funcionar