Sistemas

Sistemas

lunes, 9 de julio de 2012

14-12. Colaboración de clases

Normalmente un problema resuelto con la metodología de programación orientada a objetos no interviene una sola clase, sino que hay muchas clases que interactúan y se comunican.

Plantearemos un problema separando las actividades en dos clases.

Problema 1:

Un banco tiene 3 clientes que pueden hacer depósitos y extracciones. También el banco requiere que al final del día calcule la cantidad de dinero que hay depositada.
Lo primero que hacemos es identificar las clases:
Podemos identificar la clase Cliente y la clase Banco.
Luego debemos definir los atributos y los métodos de cada clase:
Cliente  
    atributos
        nombre
        monto
    métodos
        constructor
        depositar
        extraer
        retornarMonto

Banco
    atributos
        3 Cliente (3 objetos de la clase Cliente)
        1 Scanner (Para poder hacer la entrada de datos por teclado)
    métodos
        constructor
        operar
        depositosTotales
 
Creamos un proyecto en Eclipse llamado: Proyecto1 y dentro del proyecto creamos dos clases llamadas: Cliente y Banco.

Programa:

public class Cliente {
    private String nombre;
    private int monto;
    
    public Cliente(String nom) {
        nombre=nom;
        monto=0;
    }
    
    public void depositar(int m) {
        monto=monto+m;
    }
    
    public void extraer(int m) {
        monto=monto-m;
    }
    
    public int retornarMonto() {
        return monto;
    }
    
    public void imprimir() {
        System.out.println(nombre+" tiene depositado la suma de "
        +monto);
    }
}





public class Banco {
    private Cliente cliente1,cliente2,cliente3;
 
    public Banco() {
        cliente1=new Cliente("Juan");
        cliente2=new Cliente("Ana");
        cliente3=new Cliente("Pedro"); 
    }

    public void operar() {
        cliente1.depositar (100);
        cliente2.depositar (150);
        cliente3.depositar (200);
        cliente3.extraer (150);
    }
 
    public void depositosTotales ()
    {
        int t = cliente1.retornarMonto () + cliente2.retornarMonto () + 
        cliente3.retornarMonto ();
        System.out.println ("El total de dinero en el banco es:" + t);
        cliente1.imprimir();
        cliente2.imprimir();
        cliente3.imprimir();
    }

    public static void main(String[] ar) {
        Banco banco1=new Banco();
        banco1.operar();
        banco1.depositosTotales();
    }
} 
 
Analicemos la implementación del problema.


Los atributos de una clase normalmente son privados para que no se tenga acceso directamente desde otra clase, los atributos son modificados por los métodos de la misma clase:

    private String nombre;
    private int monto;
 
El constructor recibe como parámetro el nombre del cliente y lo almacena en el atributo respectivo e inicializa el atributo monto en cero:

    public Cliente(String nom) {
        nombre=nom;
        monto=0;
    }
 
Los métodos depositar y extraer actualizan el atributo monto con el dinero que llega como parámetro (para simplificar el problema no hemos validado que cuando se extrae dinero el atributo monto quede con un valor negativo):

    public void depositar(int m) {
        monto=monto+m;
    }
    
    public void extraer(int m) {
        monto=monto-m;
    }
 
El método retornarMonto tiene por objetivo comunicar al Banco la cantidad de dinero que tiene el cliente (recordemos que como el atributo monto es privado de la clase, debemos tener un método que lo retorne):

    public int retornarMonto() {
        return monto;
    }
 
Por último el método imprimir muestra nombre y el monto de dinero del cliente:

    public void imprimir() {
        System.out.println(nombre+" tiene depositado la suma de "+monto);
    }
 
Como podemos observar la clase Cliente no tiene función main. Entonces donde definimos objetos de la clase Cliente?

La respuesta a esta pregunta es que en la clase Banco definimos tres objetos de la clase Cliente.

Veamos ahora la clase Banco que requiere la colaboración de la clase Cliente.

Primero definimos tres atributos de tipo Cliente:

public class Banco {
    private Cliente cliente1,cliente2,cliente3;

En le constructor creamos los tres objetos (cada vez que creamos un objeto de la clase Cliente debemos pasar a su constructor el nombre del cliente, recordemos que su monto de depósito se inicializa con cero):

    public Banco() {
        cliente1=new Cliente("Juan");
        cliente2=new Cliente("Ana");
        cliente3=new Cliente("Pedro"); 
    }
 
El método operar del banco (llamamos a los métodos depositar y extraer de los clientes):

    public void operar() {
        cliente1.depositar (100);
        cliente2.depositar (150);
        cliente3.depositar (200);
        cliente3.extraer (150);
    }
 
El método depositosTotales obtiene el monto depositado de cada uno de los tres clientes, procede a mostrarlos y llama al método imprimir de cada cliente para poder mostrar el nombre y depósito:

    public void depositosTotales ()
    {
        int t = cliente1.retornarMonto () + cliente2.retornarMonto () 
        + cliente3.retornarMonto ();
        System.out.println ("El total de dinero en el banco es:" + t);
        cliente1.imprimir();
        cliente2.imprimir();
        cliente3.imprimir();
    } 
 
 
Por último en la main definimos un objeto de la clase Banco (la clase Banco es la clase principal en nuestro problema):

public static void main(String[] ar) { Banco banco1=new Banco(); banco1.operar(); banco1.depositosTotales(); }

Problema 2:

Plantear un programa que permita jugar a los dados. Las reglas de juego son: se tiran tres dados si los tres salen con el mismo valor mostrar un mensaje que "gano", sino "perdió".

Lo primero que hacemos es identificar las clases:

Podemos identificar la clase Dado y la clase JuegoDeDados.

Luego los atributos y los métodos de cada clase:

Dado atributos valor métodos tirar imprimir retornarValor JuegoDeDados atributos 3 Dado (3 objetos de la clase Dado) métodos constructor jugar Creamos un proyecto en Eclipse llamado: Proyecto2 y dentro del proyecto creamos dos clases llamadas: Dado y JuegoDeDados.


Programa:

public class Dado {
    private int valor;
    
    public void tirar() {
        valor=1+(int)(Math.random()*6);
    }
    
    public void imprimir() {
        System.out.println("El valor del dado es:"+valor);
    }
    
    public int retornarValor() {
        return valor;
    }
}




public class JuegoDeDados {
    private Dado dado1,dado2,dado3;
    
    public JuegoDeDados() {
        dado1=new Dado();
        dado2=new Dado();
        dado3=new Dado();         
    }
    
    public void jugar() {
        dado1.tirar();
        dado1.imprimir();
        dado2.tirar();
        dado2.imprimir();
        dado3.tirar();
        dado3.imprimir();
        if (dado1.retornarValor()==dado2.retornarValor() && 
            dado1.retornarValor()==dado3.retornarValor()) {
            System.out.println("Ganó");
        } else {
            System.out.println("Perdió");
        }         
    }
    
    public static void main(String[] ar){
        JuegoDeDados j=new JuegoDeDados();
        j.jugar();
    }
}
 
La clase dado define el atributo "valor" donde almacenamos un valor aleatorio que representa el número que sale al tirarlo.


public class Dado {
    private int valor;
 
El método tirar almacena el valor aleatorio (para generar un valor aleatorio utilizamos el método random de la clase Math, el mismo genera un valor real comprendido entre 0 y 1, pero nunca 0 o 1. Puede ser un valor tan pequeño como 0.0001 o tan grando como 0.9999. Luego este valor generado multiplicado por 6 y antecediendo (int) obtenemos la parte entera de dicho producto):

    public void tirar() {
        valor=1+(int)(Math.random()*6);
    }
 
Como vemos le sumamos uno ya que el producto del valor aleatorio con seis puede generar números enteros entre 0 y 5.

El método imprimir de la clase Dado muestra por pantalla el valor del dado:

    public void imprimir() {
        System.out.println("El valor del dado es:"+valor);
    }
 
Por último el método que retorna el valor del dado (se utiliza en la otra clase para ver si los tres dados generaron el mismo valor):

    public int retornarValor() {
        return valor;
    }
 
La clase JuegoDeDatos define tres atributos de la clase Dado (con esto decimos que la clase Dado colabora con la clase JuegoDeDados):

public class JuegoDeDados {
    private Dado dado1,dado2,dado3;
 
En el constructor procedemos a crear los tres objetos de la clase Dado:

    public JuegoDeDados() {
        dado1=new Dado();
        dado2=new Dado();
        dado3=new Dado();         
    }
 
En el método jugar llamamos al método tirar de cada dado, pedimos que se imprima el valor generado y finalmente procedemos a verificar si se ganó o no:

    public void jugar() {
        dado1.tirar();
        dado1.imprimir();
        dado2.tirar();
        dado2.imprimir();
        dado3.tirar();
        dado3.imprimir();
        if (dado1.retornarValor()==dado2.retornarValor() && 
            dado1.retornarValor()==dado3.retornarValor()) {
            System.out.println("Ganó");
        } else {
            System.out.println("Perdió");
        }         
    }
 
En la main creamos solo un objeto de la clase principal (en este caso la clase principal es el JuegoDeDados):

    public static void main(String[] ar){
        JuegoDeDados j=new JuegoDeDados();
        j.jugar();
    }

Problemas propuestos

Plantear una clase Club y otra clase Socio.
La clase Socio debe tener los siguientes atributos privados: nombre y la antigüedad en el club (en años). En el constructor pedir la carga del nombre y su antigüedad. La clase Club debe tener como atributos 3 objetos de la clase Socio. Definir una responsabilidad para imprimir el nombre del socio con mayor antigüedad en el club.

14-11B. Clase String

La clase String está orientada a manejar cadenas de caracteres. Hasta este momento hemos utilizado algunos métodos de la clase String (equals, compareTo)
Ahora veremos otro conjunto de métodos de uso común de la clase String:

Métodos

  • boolean equals(String s1)
    
    Como vimos el método equals retorna true si el contenido de caracteres del parámetro s1 es exactamente igual a la cadena de caracteres del objeto que llama al método equals.
  • boolean equalsIgnoreCase(String s1)
    
    El funcionamiento es casi exactamente igual que el método equals con la diferencia que no tiene en cuenta mayúsculas y minúsculas (si comparamos 'Ana' y 'ana' luego el método equalsIgnoreCase retorna true)
  • int compareTo(String s1)
    
    Este método retorna un 0 si el contenido de s1 es exactamente igual al String contenido por el objeto que llama al método compareTo. Retorna un valor >0 si el contenido del String que llama al método compareTo es mayor alfabéticamente al parámetro s1.
  • char charAt(int pos)
    
    Retorna un caracter del String, llega al método la posición del caracter a extraer.
  • int length()
    
    Retorna la cantidad de caracteres almacenados en el String.
  • String substring(int pos1,int pos2)
    
    Retorna un substring a partir de la posición indicada en el parámetro pos1 hasta la posición pos2 sin incluir dicha posición.
  • int indexOf(String s1)
    
    Retorna -1 si el String que le pasamos como parámetro no está contenida en la cadena del objeto que llama al método. En caso que se encuentre contenido el String s1 retorna la posición donde comienza a repetirse.
  • String toUpperCase()
    
    Retorna un String con el contenido convertido todo a mayúsculas.
  • String toLowerCase()
    
    Retorna un String con el contenido convertido todo a minúsculas.

Problema 1:

Confeccionar una clase que solicite el ingreso de dos String y luego emplee los métodos más comunes de la clase String.

Programa:

import java.util.Scanner;
public class Cadena1 {
    public static void main(String[] ar) {
        Scanner teclado=new Scanner(System.in);
        String cad1;
        String cad2;
        System.out.print("Ingrese la primer cadena:");
        cad1=teclado.nextLine();
        System.out.print("Ingrese la segunda cadena:");
        cad2=teclado.nextLine();
        if (cad1.equals(cad2)==true) {
            System.out.println(cad1+" es exactamente igual a "+cad2);
        } else {
            System.out.println(cad1+" no es exactamente igual a "+cad2);        
        }
        if (cad1.equalsIgnoreCase(cad2)==true) {
            System.out.println(cad1+" es igual a "+cad2+" sin tener en 
            cuenta mayúsculas/minúsculas");
        } else {
            System.out.println(cad1+" no es igual a "+cad2+" sin tener en 
            cuenta mayúsculas/minúsculas");        
        }
        if (cad1.compareTo(cad2)==0) {
            System.out.println(cad1+" es exactamente igual a "+cad2);
        } else {
            if (cad1.compareTo(cad2)>0) {
                System.out.println(cad1+ " es mayor alfabéticamente que "+cad2);
            } else {
                System.out.println(cad2+ " es mayor alfabéticamente que "+cad1);            
            }
        }        
        char carac1=cad1.charAt(0);
        System.out.println("El primer caracter de "+cad1+" es "+carac1);
        int largo=cad1.length();
        System.out.println("El largo del String "+cad1+" es "+largo);
        String cad3=cad1.substring(0,3);
        System.out.println("Los primeros tres caracteres de "+cad1+" son "+cad3);
        int posi=cad1.indexOf(cad2);
        if (posi==-1) {
            System.out.println(cad2+" no está contenido en "+cad1);
        } else {
            System.out.println(cad2+" está contenido en "+cad1+" a partir de la 
            posición "+posi);
        }
        System.out.println(cad1+ " convertido a mayúsculas es "+cad1.toUpperCase());
        System.out.println(cad1+ " convertido a minúsculas es "+cad1.toLowerCase());        
    }
}
Para cargar los dos String utilizamos en este caso el método nextLine para permitir ingresar espacios en blanco:
        System.out.print("Ingrese la primer cadena:");
        cad1=teclado.nextLine();
        System.out.print("Ingrese la segunda cadena:");
        cad2=teclado.nextLine();

Problemas propuestos

  1. Realizar una clase, que permita cargar una dirección de mail en el constructor, luego en otro método mostrar un mensaje si contiene el caracter '@'.
  2. Cargar un String por teclado e implementar los siguientes métodos:
    a) Imprimir la primera mitad de los caracteres de la cadena.
    b) Imprimir el último caracter.
    c) Imprimirlo en forma inversa.
    d) Imprimir cada caracter del String separado con un guión.
    e) Imprimir la cantidad de vocales almacenadas.
    f) Implementar un método que verifique si la cadena se lee igual de izquierda a derecha tanto como de derecha a izquierda (ej. neuquen se lee igual en las dos direcciones)
  3. Desarrollar un programa que solicite la carga de una clave. La clase debe tener dos métodos uno para la carga y otro que muestre si la clave es la correcta (la clave a comparar es "123abc")
  4. Confeccionar un programa que permita cargar los nombres de 5 personas y sus mail, luego implementar los siguientes métodos:
    a) Mostrar por pantalla los datos.
    b) Consulta del mail ingresando su nombre.
    c) Mostrar los mail que no tienen el carácter @.
  5. Codifique un programa que permita cargar una oración por teclado, luego mostrar cada palabra ingresada en una línea distinta.
     
    Por ejemplo si cargo: 
      La mañana está fría. 
    Debe aparecer: 
     
    La 
    mañana 
    está 
    fría. 
    

14-11. Constructor de la clase

En Java podemos definir un método que se ejecute inicialmente y en forma automática. Este método se lo llama constructor.
El constructor tiene las siguientes características:
  • Tiene el mismo nombre de la clase.
  • Es el primer método que se ejecuta.
  • Se ejecuta en forma automática.
  • No puede retornar datos.
  • Se ejecuta una única vez.
  • Un constructor tiene por objetivo inicializar atributos.

Problema 1:

Se desea guardar los sueldos de 5 operarios en un vector. Realizar la creación y carga del vector en el constructor.

Programa:

import java.util.Scanner;
public class Operarios {
    private Scanner teclado;
    private int[] sueldos;
 
    public Operarios()
    {
        teclado=new Scanner(System.in);
        sueldos=new int[5];
        for(int f=0;f<5;f++) {
            System.out.print("Ingrese valor de la componente:");
            sueldos[f]=teclado.nextInt();
        } 
    }
 
    public void imprimir() {
        for(int f=0;f<5;f++) {
            System.out.println(sueldos[f]);
        }
    }
 
    public static void main(String[] ar) {
        Operarios op=new Operarios();
        op.imprimir();
    }
}
Como podemos ver es el mismo problema que resolvimos cuando vimos vectores. La diferencia es que hemos sustituido el método cargar con el constructor:
    public Operarios()
    {
        teclado=new Scanner(System.in);
        sueldos=new int[5];
        for(int f=0;f<5;f++) {
            System.out.print("Ingrese valor de la componente:");
            sueldos[f]=teclado.nextInt();
        } 
    }
Como la clase se llama Operarios el constructor tiene el mismo nombre, no disponemos la palabra clave void ya que el constructor no puede retornar datos.
La ventaja de plantear un constructor en lugar de definir un método con cualquier nombre es que se llamará en forma automática cuando se crea un objeto de esta clase:
    public static void main(String[] ar) {
        Operarios op=new Operarios();
Cuando se crea el objeto op se llama al método constructor.
Finalmente llamamos al método imprimir:
        op.imprimir();

Problema 2:

Plantear una clase llamada Alumno y definir como atributos su nombre y su edad. En el constructor realizar la carga de datos. Definir otros dos métodos para imprimir los datos ingresados y un mensaje si es mayor o no de edad (edad >=18)

Programa:

import java.util.Scanner;
public class Alumno {
    private Scanner teclado;
    private String nombre;
    private int edad;
    
    public Alumno() {
        teclado=new Scanner(System.in);
        System.out.print("Ingrese nombre:");
        nombre=teclado.next();
        System.out.print("Ingrese edad:");
        edad=teclado.nextInt();
    }
    
    public void imprimir() {
        System.out.println("Nombre:"+nombre);
        System.out.println("Edad:"+edad);
    }
    
    public void esMayorEdad() {
        if (edad>=18) {
            System.out.print(nombre+" es mayor de edad.");
        } else {
            System.out.print(nombre+" no es mayor de edad.");
        }
    }
    
    public static void main(String[] ar) {
        Alumno alumno1=new Alumno();
        alumno1.imprimir();
        alumno1.esMayorEdad();
    }
}
Declaramos la clase Persona, sus tres atributos y definimos el constructor con el mismo nombre de la clase:
public class Alumno {
    private Scanner teclado;
    private String nombre;
    private int edad;
    
    public Alumno() {
        teclado=new Scanner(System.in);
        System.out.print("Ingrese nombre:");
        nombre=teclado.next();
        System.out.print("Ingrese edad:");
        edad=teclado.nextInt();
    }
En la main el constructor se llama en forma automática cuando creamos un objeto de la clase Alumno:
    public static void main(String[] ar) {
        Alumno alumno1=new Alumno();
Los otros dos métodos deben llamarse por su nombre y en el orden que necesitemos:
        alumno1.imprimir();
        alumno1.esMayorEdad();

miércoles, 4 de julio de 2012

JAVA 35. Estructuras dinámicas: Listas tipo Pila - Problema de aplicación

Hasta ahora hemos visto como desarrollar los algoritmos para administrar una lista tipo Pila, hemos visto que hay bastante complejidad en el manejo de punteros pero todo esto acarrea ventajas en la solución de problemas que requieren una estructura de tipo Pila.

Planteo del problema:

Este práctico tiene por objetivo mostrar la importancia de las pilas en las Ciencias de la Computación y más precisamente en la programación de software de bajo nivel.

Todo compilador o intérprete de un lenguaje tiene un módulo dedicado a analizar si una expresión está correctamente codificada, es decir que los paréntesis estén abiertos y cerrados en un orden lógico y bien balanceados.

Se debe desarrollar una clase que tenga las siguientes responsabilidades (clase Formula):



- Ingresar una fórmula que contenga paréntesis, corchetes y llaves.
- Validar que los ( ) [] y {} estén correctamente balanceados. 


Para la solución de este problema la clase formula tendrá un atributo de la clase Pila.

Veamos como nos puede ayudar el empleo de una pila para solucionar este problema.

Primero cargaremos la fórmula en un JTextField.

Ejemplo de fórmula: (2+[3-12]*{8/3})

El algoritmo de validación es el siguiente:

Analizamos caracter a caracter la presencia de los paréntesis, corchetes y llaves.

Si vienen símbolos de apertura los almacenamos en la pila.

Si vienen símbolos de cerrado extraemos de la pila y verificamos si está el mismo símbolo pero de apertura: en caso negativo podemos inferir que la fórmula no está correctamente balanceada.

Si al finalizar el análisis del último caracter de la fórmula la pila está vacía podemos concluir que está correctamente balanceada.

Ejemplos de fórmulas no balanceadas:

}(2+[3-12]*{8/3})
Incorrecta: llega una } de cerrado y la pila está vacía.
{[2+4}]
Incorrecta: llega una llave } y en el tope de la pila hay un corchete [.
{[2+4]
Incorrecta: al finalizar el análisis del último caracter en la pila queda 

pendiente una llave {.


Pila

Programa:

public class Pila {
 
 class Nodo {
     char simbolo;
     Nodo sig;
 }
 
    private Nodo raiz;
    
    Pila () {
        raiz=null;
    }
    
    public void insertar(char x) {
     Nodo nuevo;
        nuevo = new Nodo();
        nuevo.simbolo = x;
        if (raiz==null)
        {
            nuevo.sig = null;
            raiz = nuevo;
        }
        else
        {
            nuevo.sig = raiz;
            raiz = nuevo;
        }
    }
    
    public char extraer ()
    {
        if (raiz!=null)
        {
            char informacion = raiz.simbolo;
            raiz = raiz.sig;
            return informacion;
        }
        else
        {
            return Character.MAX_VALUE;
        }
    }  
    
    public boolean vacia() {
        if (raiz==null) {
            return true;
        } else {
            return false;
        }
    }
}





import javax.swing.*;
import java.awt.event.*;
public class Formula extends JFrame implements ActionListener {
    private JTextField tf1;
    private JButton boton1;
    public Formula() {
        setLayout(null);
        tf1=new JTextField("{2*(4-5)-{3*4}-[4-5]}");
        tf1.setBounds(10,10,230,30);
        add(tf1);
        boton1=new JButton("Verificar fórmula.");
        boton1.setBounds(10,70,180,30);
        add(boton1);
        boton1.addActionListener(this);
    }
    
    public void actionPerformed(ActionEvent e) {
        if (e.getSource()==boton1) {
           if (balanceada()) {
               setTitle("Está correctamente balanceada.");
           } else {
               setTitle("No está correctamente balanceada.");
           }
        }
    }

    public boolean balanceada() {
        Pila pila1;  
     pila1 = new Pila ();    
     String cadena=tf1.getText();
     for (int f = 0 ; f < cadena.length() ; f++)
     {
         if (cadena.charAt(f) == '(' || cadena.charAt(f) == '[' || cadena.charAt(f) == '{') {
          pila1.insertar(cadena.charAt(f));
         } else {
          if (cadena.charAt(f)==')') {
              if (pila1.extraer()!='(') {
                  return false;
              }
           } else {
              if (cadena.charAt(f)==']') {
                  if (pila1.extraer()!='[') {
                      return false;
                  }
              } else {
                  if (cadena.charAt(f)=='}') {
                      if (pila1.extraer()!='{') {
                          return false;
                      }
                  }
              }
             }
        }   
        }
     if (pila1.vacia()) {
         return true;
     } else {
        return false;
     }
    } 
    
    
    public static void main(String[] ar) {
        Formula formula1=new Formula();
        formula1.setBounds(0,0,350,140);
        formula1.setVisible(true);
    }
    
}


Primero declaramos y definimos la clase Pila. Almacenamos en cada nodo un caracter y llamamos al campo de información símbolo.

No es necesario implementar los métodos imprimir, cantidad, etc. Porque no se requieren para este problema.

La clase Formula tiene como atributos:

    private JTextField tf1;
    private JButton boton1;

En el constructor creamos los dos objetos y los ubicamos:

        setLayout(null);
        tf1=new JTextField("{2*(4-5)-{3*4}-[4-5]}");
        tf1.setBounds(10,10,230,30);
        add(tf1);
        boton1=new JButton("Verificar fórmula.");
        boton1.setBounds(10,70,180,30);
        add(boton1);
        boton1.addActionListener(this);
En el método actionPerformed llamamos al método balanceada que debe retornar si la fórmula están correctos los parentesis, corchetes y llaves:
        if (e.getSource()==boton1) {
           if (balanceada()) {
               setTitle("Está correctamente balanceada.");
           } else {
               setTitle("No está correctamente balanceada.");
           }
        }

El método más importante es el balanceada.

En este analizamos la fórmula para verificar si está correctamente balanceada.
En este método es donde está gran parte del algoritmo de este problema. Retorna true en caso de ser correcta y false en caso contrario.

Definimos una pila y extraemos el contenido del JTextField:

        Pila pila1;  
     pila1 = new Pila ();    
     String cadena=tf1.getText();

El for se repite tantas veces como caracteres tenga el JTextField.
Se deben procesar sólo los símbolos ( [ { y ) ] }.

Si el símbolo es un ( [ { de apertura procedemos a cargarlo en la pila:

         if (cadena.charAt(f) == '(' || cadena.charAt(f) == '[' || cadena.charAt(f) == '{') {
          pila1.insertar(cadena.charAt(f));

En caso de ser un ) cerrado debemos extraer un carácter de la pila y verificar si no coincide con el paréntesis de apertura ( la fórmula está incorrecta:

          if (cadena.charAt(f)==')') {
              if (pila1.extraer()!='(') {
                  return false;
              }

El mismo proceso es para los símbolos ] }.

Al finalizar el análisis de toda la cadena si la pila está vacía podemos afirmar que la fórmula está correctamente balanceada, en caso contrario quiere decir que faltan símbolos de cerrado y es incorrecta:

     if (pila1.vacia()) {
         return true;
     } else {
        return false;
     }


Es importante entender que la clase Formula utiliza un objeto de la clase Pila para resolver el algoritmo de verificar el balanceo de la fórmula, pero no accede directamente a los nodos de la lista.

JAVA 34. Estructuras dinámicas: Listas tipo Pila

Una lista se comporta como una pila si las inserciones y extracciones las hacemos por un mismo lado de la lista. También se las llama listas LIFO (Last In First Out - último en entrar primero en salir)

Importante: Una pila al ser una lista puede almacenar en el campo de información cualquier tipo de valor (int, char, float, vector de caracteres, un objeto, etc)

Para estudiar el mecanismo de utilización de una pila supondremos que en el campo de información almacena un entero (para una fácil interpretación y codificación)

Inicialmente la PILA está vacía y decimos que el puntero raiz apunta a null (Si apunta a null decimos que no tiene una dirección de memoria):

pila vacía

Insertamos un valor entero en la pila: insertar(10)

pila

Luego de realizar la inserción la lista tipo pila queda de esta manera: un nodo con el valor 10 y raiz apunta a dicho nodo. El puntero del nodo apunta a null ya que no hay otro nodo después de este.

Insertamos luego el valor 4: insertar(4)

pila

Ahora el primer nodo de la pila es el que almacena el valor cuatro.

raiz apunta a dicho nodo. Recordemos que raiz es el puntero externo a la lista que almacena la dirección del primer nodo.

El nodo que acabamos de insertar en el campo puntero guarda la dirección del nodo que almacena el valor 10.

Ahora qué sucede si extraemos un nodo de la pila. ¿Cuál se extrae? Como sabemos en una pila se extrae el último en entrar.

Al extraer de la pila tenemos: extraer()

pila

La pila ha quedado con un nodo.

Hay que tener cuidado que si se extrae un nuevo nodo la pila quedará vacía y no se podrá extraer otros valores (avisar que la pila está vacía)

Problema 1:

Confeccionar una clase que administre una lista tipo pila (se debe poder insertar, extraer e imprimir los datos de la pila)

Programa:

public class Pila {
 
    class Nodo {
        int info;
        Nodo sig;
    }
 
    private Nodo raiz;
    
    public Pila () {
        raiz=null;
    }
    
    public void insertar(int x) {
     Nodo nuevo;
        nuevo = new Nodo();
        nuevo.info = x;
        if (raiz==null)
        {
            nuevo.sig = null;
            raiz = nuevo;
        }
        else
        {
            nuevo.sig = raiz;
            raiz = nuevo;
        }
    }
    
    public int extraer ()
    {
        if (raiz!=null)
        {
            int informacion = raiz.info;
            raiz = raiz.sig;
            return informacion;
        }
        else
        {
            return Integer.MAX_VALUE;
        }
    }
    
    public void imprimir() {
        Nodo reco=raiz;
        System.out.println("Listado de todos los elementos de la pila.");
        while (reco!=null) {
            System.out.print(reco.info+"-");
            reco=reco.sig;
        }
        System.out.println();
    }
    
    public static void main(String[] ar) {
        Pila pila1=new Pila();
        pila1.insertar(10);
        pila1.insertar(40);
        pila1.insertar(3);
        pila1.imprimir();
        System.out.println("Extraemos de la pila:"+pila1.extraer());
        pila1.imprimir();        
    }
}
Analicemos las distintas partes de este programa:

    class Nodo {
        int info;
        Nodo sig;
    }
 
    private Nodo raiz;


Para declarar un nodo debemos utilizar una clase. En este caso la información del nodo (info) es un entero y siempre el nodo tendrá una referencia de tipo Nodo, que le llamamos sig.

El puntero sig apunta al siguiente nodo o a null en caso que no exista otro nodo. Este puntero es interno a la lista.

También definimos un puntero de tipo Nodo llamado raiz. Este puntero tiene la dirección del primer nodo de la lista. En caso de estar vacía la lista, raiz apunta a null (es decir no tiene dirección)

El puntero raiz es fundamental porque al tener la dirección del primer nodo de la lista nos permite acceder a los demás nodos.

    public Pila () {
        raiz=null;
    }
En el constructor de la clase hacemos que raiz guarde el valor null. Tengamos en cuenta que si raiz tiene almacenado null la lista está vacía, en caso contrario tiene la dirección del primer nodo de la lista.

    public void insertar(int x) {
     Nodo nuevo;
        nuevo = new Nodo();
        nuevo.info = x;
        if (raiz==null)
        {
            nuevo.sig = null;
            raiz = nuevo;
        }
        else
        {
            nuevo.sig = raiz;
            raiz = nuevo;
        }
    }
Uno de los métodos más importantes que debemos entender en una pila es el de insertar un elemento en la pila.
Al método llega la información a insertar, en este caso en particular es un valor entero.
La creación de un nodo requiere dos pasos:

- Definición de un puntero o referencia a un tipo de dato Nodo:

     Nodo nuevo;
- Creación del nodo (creación de un objeto):
        nuevo = new Nodo();
Cuando se ejecuta el operador new se reserva espacio para el nodo. Realmente se crea el nodo cuando se ejecuta el new.

pila

Paso seguido debemos guardar la información del nodo:

        nuevo.info = x;

En el campo info almacenamos lo que llega en el parámetro x. Por ejemplo si llega un 5 el nodo queda:

pila

Por último queda enlazar el nodo que acabamos de crear al principio de la lista.

Si la lista está vacía debemos guardar en el campo sig del nodo el valor null para indicar que no hay otro nodo después de este, y hacer que raiz apunte al nodo creado (sabemos si una lista esta vacía si raiz almacena un null)

        if (raiz==null)
        {
            nuevo.sig = null;
            raiz = nuevo;
        }

pila

Gráficamente podemos observar que cuando indicamos raiz=nuevo, el puntero raiz guarda la dirección del nodo apuntado por nuevo.

Tener en cuenta que cuando finaliza la ejecución del método el puntero nuevo desaparece, pero no el nodo creado con el operador new.

En caso que la lista no esté vacía, el puntero sig del nodo que acabamos de crear debe apuntar al que es hasta este momento el primer nodo, es decir al nodo que apunta raiz actualmente.

        else
        {
            nuevo.sig = raiz;
            raiz = nuevo;
        }

Como primera actividad cargamos en el puntero sig del nodo apuntado por nuevo la dirección de raiz, y posteriormente raiz apunta al nodo que acabamos de crear, que será ahora el primero de la lista.

Antes de los enlaces tenemos:

pila

Luego de ejecutar la línea:

            nuevo.sig = raiz;

Ahora tenemos:

pila

Por último asignamos a raiz la dirección que almacena el puntero nuevo.

            raiz = nuevo;

La lista queda:

pila

El método extraer:

    public int extraer ()
    {
        if (raiz!=null)
        {
            int informacion = raiz.info;
            raiz = raiz.sig;
            return informacion;
        }
        else
        {
            return Integer.MAX_VALUE;
        }
    }

El objetivo del método extraer es retornar la información del primer nodo y además borrarlo de la lista.

Si la lista no está vacía guardamos en una variable local la información del primer nodo:

            int informacion = raiz.info;

Avanzamos raiz al segundo nodo de la lista, ya que borraremos el primero:

            raiz = raiz.sig;

el nodo que previamente estaba apuntado por raiz es eliminado automáticamente por la máquina virtual de Java, al no tener ninguna referencia.

Retornamos la información:

            return informacion;

En caso de estar vacía la pila retornamos el número entero máximo y lo tomamos como código de error (es decir nunca debemos guardar el entero mayor en la pila)

            return Integer.MAX_VALUE;

Es muy importante entender gráficamente el manejo de las listas. La interpretación gráfica nos permitirá plantear inicialmente las soluciones para el manejo de listas.

pila

Por último expliquemos el método para recorrer una lista en forma completa e imprimir la información de cada nodo:

    public void imprimir() {
        Nodo reco=raiz;
        System.out.println("Listado de todos los elementos de la pila.");
        while (reco!=null) {
            System.out.print(reco.info+"-");
            reco=reco.sig;
        }
        System.out.println();
    }

Definimos un puntero auxiliar reco y hacemos que apunte al primer nodo de la lista:

        Nodo reco=raiz;

Disponemos una estructura repetitiva que se repetirá mientras reco sea distinto a null. Dentro de la estructura repetitiva hacemos que reco avance al siguiente nodo:

        while (reco!=null) {
            System.out.print(reco.info+"-");
            reco=reco.sig;
        }

Es muy importante entender la línea:

            reco=reco.sig;

Estamos diciendo que reco almacena la dirección que tiene el puntero sig del nodo apuntado actualmente por reco.

Gráficamente:

pila

Al analizarse la condición:

        while (reco!=null) {

se valúa en verdadero ya que reco apunta a un nodo y se vuelve a ejecutar la línea:

            reco=reco.sig;

Ahora reco apunta al siguiente nodo:

pila

La condición del while nuevamente se valúa en verdadera y avanza el puntero reco al siguiente nodo:

            reco=reco.sig;

pila

Ahora sí reco apunta a null y ha llegado el final de la lista (Recordar que el último nodo de la lista tiene almacenado en el puntero sig el valor null, con el objetivo de saber que es el último nodo)

Para poder probar esta clase recordemos que debemos definir un objeto de la misma y llamar a sus métodos:

    public static void main(String[] ar) {
        Pila pila1=new Pila();
        pila1.insertar(10);
        pila1.insertar(40);
        pila1.insertar(3);
        pila1.imprimir();
        System.out.println("Extraemos de la pila:"+pila1.extraer());
        pila1.imprimir();        
    }

Insertamos 3 enteros, luego imprimimos la pila, extraemos uno de la pila y finalmente imprimimos nuevamente la pila.

Problema 2:

Agregar a la clase Pila un método que retorne la cantidad de nodos y otro que indique si esta vacía.

Programa:

public class Pila {
 
 class Nodo {
     int info;
     Nodo sig;
 }
 
    private Nodo raiz;
    
    Pila () {
        raiz=null;
    }
    
    public void insertar(int x) {
     Nodo nuevo;
        nuevo = new Nodo();
        nuevo.info = x;
        if (raiz==null)
        {
            nuevo.sig = null;
            raiz = nuevo;
        }
        else
        {
            nuevo.sig = raiz;
            raiz = nuevo;
        }
    }
    
    public int extraer ()
    {
        if (raiz!=null)
        {
            int informacion = raiz.info;
            raiz = raiz.sig;
            return informacion;
        }
        else
        {
            return Integer.MAX_VALUE;
        }
    }
    
    public void imprimir() {
        Nodo reco=raiz;
        System.out.println("Listado de todos los elementos de la pila.");
        while (reco!=null) {
            System.out.print(reco.info+"-");
            reco=reco.sig;
        }
        System.out.println();
    }
    
    public boolean vacia() {
        if (raiz==null) {
            return true;
        } else {
         return false; 
        }
    }
    
    public int cantidad() {
        int cant=0;
        Nodo reco=raiz;
        while (reco!=null) {
            cant++;
            reco=reco.sig;
        }
        return cant;
    }
    
    public static void main(String[] ar) {
        Pila pila1=new Pila();
        pila1.insertar(10);
        pila1.insertar(40);
        pila1.insertar(3);
        pila1.imprimir();
        System.out.println("La cantidad de nodos de la lista es:"+pila1.cantidad());
        while (pila1.vacia()==false) {
            System.out.println(pila1.extraer());
        }
    }
}


Para verificar si la pila esta vacía verificamos el contenido de la variable raiz, si tiene null luego la lista esta vacía y por lo tanto retornamos un true:

    public boolean vacia() {
        if (raiz==null) {
            return true;
        } else {
         return false; 
        }
    }


El algoritmo para saber la cantidad de nodos es similar al imprimir, pero en lugar de mostrar la información del nodo procedemos a incrementar un contador:

    public int cantidad() {
        int cant=0;
        Nodo reco=raiz;
        while (reco!=null) {
            cant++;
            reco=reco.sig;
        }
        return cant;
    }

Para probar esta clase en la main creamos un objeto de la clase Pila insertamos tres enteros:

        Pila pila1=new Pila();
        pila1.insertar(10);
        pila1.insertar(40);
        pila1.insertar(3);

Imprimimos la pila (nos muestra los tres datos):

        pila1.imprimir();

Llamamos al método cantidad (nos retorna un 3):

        System.out.println("La cantidad de nodos de la lista es:"+pila1.cantidad());

Luego mientras el método vacía nos retorne un false (lista no vacía) procedemos a llamar al método extraer:

        while (pila1.vacia()==false) {
            System.out.println(pila1.extraer());
        }

Problemas propuestos

  1. Agregar un método a la clase Pila que retorne la información del primer nodo de la Pila sin borrarlo.

JAVA 33. Estructuras dinámicas: Listas

Una lista es un conjunto de nodos, cada uno de los cuales tiene dos campos: uno de información y un apuntador al siguiente nodo de la lista. Además un apuntador externo señala el primer nodo de la lista.

Representación gráfica de un nodo:



La información puede ser cualquier tipo de dato simple, estructura de datos o inclusive uno o más objetos.

La dirección al siguiente nodo es un puntero.

Representación gráfica de una lista:


Como decíamos, una lista es una secuencia de nodos (en este caso cuatro nodos). La información de los nodos en este caso es un entero y siempre contiene un puntero que guarda la dirección del siguiente nodo.

raiz es otro puntero externo a la lista que contiene la dirección del primer nodo.

El estado de una lista varía durante la ejecución del programa:



De esta forma representamos gráficamente una lista vacía.

Si insertamos un nodo en la lista quedaría luego:



Si insertamos otro nodo al principio con el valor 9 tenemos:



Lo mismo podemos borrar nodos de cualquier parte de la lista.

Esto nos trae a la mente el primer problema planteado: el desarrollo del procesador de texto. Podríamos utilizar una lista que inicialmente estuviera vacía e introdujéramos un nuevo nodo con cada línea que tipea el operador. Con esta estructura haremos un uso muy eficiente de la memoria. Tipos de listas.

Según el mecanismo de inserción y extracción de nodos en la lista tenemos los siguientes tipos:

* Listas tipo pila. * Listas tipo cola. * Listas genéricas. Una lista se comporta como una pila si las inserciones y extracciones las hacemos por un mismo lado de la lista. También se las llama listas LIFO (Last In First Out - último en entrar primero en salir)

Una lista se comporta como una cola si las inserciones las hacemos al final y las extracciones las hacemos por el frente de la lista. También se las llama listas FIFO (First In First Out - primero en entrar primero en salir)

Una lista se comporta como genérica cuando las inserciones y extracciones se realizan en cualquier parte de la lista.

Podemos en algún momento insertar un nodo en medio de la lista, en otro momento al final, borrar uno del frente, borrar uno del fondo o uno interior, etc.

JAVA 32. Estructuras dinámicas

Conocemos algunas estructuras de datos como son los vectores y matrices. No son las únicas. Hay muchas situaciones donde utilizar alguna de estas estructuras nos proporcionará una solución muy ineficiente (cantidad de espacio que ocupa en memoria, velocidad de acceso a la información, etc.)

Ejemplo 1. Imaginemos que debemos realizar un procesador de texto, debemos elegir la estructura de datos para almacenar en memoria las distintas líneas que el operador irá tipeando. Una solución factible es utilizar una matriz de caracteres. Pero como sabemos debemos especificar la cantidad de filas y columnas que ocupará de antemano.

Podría ser por ejemplo 2000 filas y 200 columnas. Con esta definición estamos reservando de antemano 800000 bytes de la memoria, no importa si el operador después carga una línea con 20 caracteres, igualmente ya se ha reservado una cantidad de espacio que permanecerá ociosa.

Tiene que existir alguna estructura de datos que pueda hacer más eficiente la solución del problema anterior.

Ejemplo 2. ¿Cómo estarán codificadas las planillas de cálculo? ¿Reservarán espacio para cada casilla de la planilla al principio? Si no la lleno, ¿lo mismo se habrá reservado espacio?

Utilizar una matriz para almacenar todas las casillas de una planilla de cálculo seguro será ineficiente.

Bien, todos estos problemas y muchos más podrán ser resueltos en forma eficiente cuando conozcamos estas nuevas estructuras de datos (Listas, árboles)