domingo, diciembre 12, 2010

Paréntesis Balanceados - Problema UVA 673

Este problema busca identificar si una cadena conformada exclusivamente por paréntesis redondos y cuadrados está correctamente formada. La descripción del problema se encuentra en el sitio de UVA en la dirección: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=8&page=show_problem&problem=614

Para resolver el problema se recurre a una pila como estructura de datos en la que se guardan los paréntesis izquierdos que se van leyendo, y que deben ser extraídos correctamente cuando aparezcan los paréntesis derechos en la expresión a evaluar.

import java.io.*;
import java.util.*;

class Main {
    static BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

    public static void main(String args[]) throws Exception {
        Main myWork = new Main();   // create a dinamic instance
        myWork.Begin();             // the true entry point
    }

    void Begin() throws Exception {
        // En la primera línea de la entrada se lee el número de casos a evaluar
        int numeroCasos = Integer.parseInt(in.readLine());

        // Cada caso se evalúa en forma individual
        for(int i=0; i<numeroCasos; i++) {
            boolean respuesta = evaluarCadena(in.readLine().toCharArray());
            if(respuesta==true) System.out.println("Yes");
            if(respuesta==false) System.out.println("No");
        }
    }

    boolean evaluarCadena(char[] cadena) {
        // Una pila es la estructura ideal para la evaluación de cadenas balanceadas
        Stack<Character> cola = new Stack<Character>();
        for(char c: cadena) {
            // los paréntesis izquierdos se agregan a la pila, mientras que los derechos
            // requieren sacar el elemento opuesto de la pila, de lo contrario hay error.
            if(c=='[' || c=='(') { cola.push(c); continue; }
            if(cola.isEmpty()) return false;
            if(c==')' && cola.pop()!='(') return false;
            if(c==']' && cola.pop()!='[') return false;
        }
        if(!cola.isEmpty()) return false;
        else return true;
    }
}

0 comentarios:

Publicar un comentario

LinkWithin

Related Posts Plugin for WordPress, Blogger...

Calificar