jueves, 17 de noviembre de 2011

Ley Lleras

Preocupante...


viernes, 4 de noviembre de 2011

Pilas C++ !!

Pilas en C++:
Hace poco me llego una "barbacha" (Barbacha: dicese del trabajo freelance, pequeño, temporal en donde el precio es mas regateado que una película en San Bazar..), esta consistía en realizar un programa en C++ que determinara si una palabra es palindrome (palabra que se lee igual al derecho y al revés).
Para desarrollarlo use code::blocks (http://www.codeblocks.org/), un ide para C++ que me ha parecido excelente, ademas de ser multiplataforma.

Una pila es un tipo especial de lista enlazada de la cual solo se puede insertar y eliminar elementos en uno de los extremos de la lista. Imaginemos una lista enlazada como un tren, en donde cada vagón lleva su carga y tiene un enlace al siguiente vagón. Por lo tanto un nodo de la lista tendria un campo de valor y en C++ un puntero hacia el siguiente nodo(vagón).



class nodo{
// metodos publicos: son los que se acceden desde otros objetos
    public:
// inicializamos el constructor del objeto
        nodo(char v, nodo *sig = NULL){
            valor = v;
            siguiente = sig;
        }
    private:
        char valor; // el dato que guardamos en el nodo
        nodo *siguiente; // puntero hacia el siguiente nodo


    friend class pila; // definimos que la clase pila tiene acceso a los metodos
};


typedef nodo *pnodo; // definimos un tipo de dato


Estos nodos irían encapsulados en una clase llamada pila, que es la encargada de aplicar la lógica de sacar y meter datos. Esta clase deberá llevar un contador para saber cuando la pila esta vacia, con el fin de evitar punteros a campos nulos,


/*
Definimos la clase pila que manejara los metodos de sacar y meter
nodos dentro de la pila
*/
class pila{
    public:
        pila() : ultimo(NULL){ contador=0;}
        ~pila();


        void Push(char v); // con Push se ingresa un nuevo nodo con valor
        char Pop(); // con Pop se extrae el ultimo nodo ingresado
        int contador; // contador nos permite determinar si la pila esta vacia o
 // todavia tiene algun dato


    private:
        pnodo ultimo; // nodo que nos indica cual es el ultimo de la pila
};

Para insertar un valor usamos la función Agregar(char), esta funciona de la siguiente manera:

  1. Incrementamos el contador al crear un nodo
  2. Recibimos el valor por parámetro
  3. Guardamos el nuevo nodo como el ultimo de la pila.
void pila::Agregar(char v){
    this->contador++;
    pnodo nuevo;
    // crea nodo nuevo
    nuevo = new nodo(v, ultimo);
    // apuntar el comienzo de la pila alnuevo nodo
    ultimo = nuevo;
    if(!primero) primero = nuevo;
}


Para sacar un valor usamos la función Leer, esta funciona así:


  1. Decrementamos el contador de items
  2. Creamos un nodo auxiliar y una variable para retornar el valor del nodo que vamos a sacar
  3. Guardamos el ultimo nodo en el nodo auxiliar
  4. En el ultimo nodo, guardamos el siguiente del auxiliar
  5. Guardamos en la variable el valor del nodo actual
  6. Borramos el nodo con la función delete
  7. Retornamos el valor del nuevo nodo




char pila::Leer(){
    this->contador--;
    pnodo nodo; // variable auxiliar para manupular el nodo
    char v; // variable auxiliar para retorno
    if(!ultimo) return ' '; // si no hay nodos retorna vacio
    //el nodo apunta al primer elemento de la pila
    nodo = ultimo;
    // asignamos a pila toda la pila menos el primero
    ultimo = nodo->siguiente;
    //guardar el valor a retornar
    v = nodo->valor;
    delete nodo;


// si la cola quedo vacia, el ultimo debe ser NULL tambien
    if (!primero) ultimo = NULL;


    return v;
}


El destructor en C++ es una función que se encarga de limpiar la memoria del sistema cuando el objeto ya no se va a utilizar. Lo único que hace es recorrer toda la lista e ir borrando item por item.


/*
El destructor sirve para finalizar el objeto pila
recorre cada item de la pila y lo elimina con delete
*/
pila::~pila(){
    pnodo aux;


    while(ultimo){
        aux = ultimo;
        ultimo = ultimo->siguiente;
        delete aux;
    }
}

Ahora la lógica para determinar si una palabra es palindrome es sencilla, solamente tienes que comparar la primera letra con la ultima y así sucesivamente hasta comprobar toda la palabra letra por letra. Si alguna letra es diferente a su equivalente ya no es una palindrome.


int main(){


    cola Cola;
char palabra[256];
int i =0;
int longitud = 0;
bool palindrome = true;


cout << "Digite la palabra" << endl;
cin >> palabra;


/*
La idea es ingresar la palabra a la pila, despues recorrer el vector
que contiene la palabra de forma inversa comparandola con la pila
de forma normal; asi comparamos el ultimo termino de la palabra en
el vector contra el primer termino de la pila.
Si llega a existir alguna letra diferente, ya no es palindrome
*/


for (i=0; palabra[i] != '.'; i++){
Cola.Agregar(palabra[i]);
longitud++;
}


for (i=longitud-1; i>0; i--){
char caracter;
char caracter_pila;
caracter = palabra[i];
caracter_pila = Cola.Leer();
if (caracter != caracter_pila || caracter == ' '){
palindrome = false;
break;
}
}
if (palindrome){
        cout << " Es palindrome" << endl;
}else{
        cout << " No es palindrome" << endl;
}


    return 0;
}


No es el mejor algoritmo, pero es para aprender Pilas, ademas mi lenguaje es Java, y este ya trae estas funciones y estructuras de serie. C++ también con templates, pero es un lenguaje que hasta ahora estoy tomando en serio.
Se reciben comentarios de optimizacion y correcciones.

Fuente:
http://c.conclase.net/edd/index.php?cap=002#inicio