Temas

[Etiquetado de los nodos]

Recientemente vi una pregunta de un usuario del foro sobre grafos no dirigidos y distancia mínima entre nodos del mismo. Me puse a invetigar el tema, el cual me pareció realmente interesante y decidí escribir un post al respecto.

El algoritmo de Dijkstra permite encontrar la distancia mínima entre un vértice dado de un grafo no dirigido, y cualquiera otro de sus vértices. No funciona sin embargo si la ponderación entre dos elementos es negativa, es sólo para grafos donde el coste de unir dos nodos cualesquiera es siempre mayor o igual que cero.

http://es.wikipedia.org/wiki/Algoritmo_de_Dijkstra
http://es.wikipedia.org/wiki/Anexo:Ejemplo_de_Algoritmo_de_Dijkstra

Un video de youtube que nos explica este tema de una manera excelente es:

[youtube=640,360] https://www.youtube.com/watch?v=yrNAtAIUhJA [/youtube]

A modo de ejemplo, consideremos el grafo (me disculpan la presentación simplemente me puse a escribir sobre una hoja de papel y le tomé fotografías)

En esta imagen, los valores sobre las aristas representan los pesos o costes de transitar los caminos que unen un nodo con el otro. El algoritmo comienza eligiendo un nodo inicial, en este caso digamos que el nodo 0.

Etiquetado de los nodos

Junto con cada nodo asociaremos una etiqueta o label que se compone de un par de valores:

( peso_acumulado, antecesor )

esto es, como primer elemento el peso total acumulado del nodo actual (la suma de los pesos de las aristas recorridas para llegar desde el nodo inicial hasta el nodo actual), y como segundo elemento denotamos el nodo previo al nodo actual. Esto último es importante para reconstruir la ruta seguida para llegar al nodo.

El nodo inicial tiene un peso de 0 (la distancia que lo separa de sí mismo es lógicamente cero), y no tiene antecesor, por lo que se asigna el par compuesto de un "cero" seguido de una "rayita": (0, -)

Vale decir que los restantes nodos comienzan con un peso o coste "infinito", pues aún no hemos calculado su coste.

Cálculo del coste hasta los nodos sucesivos

El siguiente paso es observar todos los nodos que están directamente conectados con este nodo inicial. En nuestro caso, los nodos 1, 2 y 3. El coste de cada nodo será el coste acumulado de su nodo antecesor, sumado al coste del camino que une al antecesor con el nodo actual:

Código [Seleccionar] Expandir


coste de nodo 1: (coste acumulado nodo 0) + (coste camino que une nodos 0 y 1) = 0 + 16 = 16
coste de nodo 2: (coste acumulado nodo 0) + (coste camino que une nodos 0 y 2) = 0 + 10 = 10
coste de nodo 3: (coste acumulado nodo 0) + (coste camino que une nodos 0 y 3) = 0 + 5 = 5

por lo tanto etiquetamos estos nodos sucesores del nodo 0 de la siguiente manera:

Código [Seleccionar] Expandir


nodo 1 ---> ( 16, 0 )     [ pues, su coste acumulado es 16, y procede del nodo 0 ]
nodo 2 ---> ( 10, 0 )     [ ídem ]
nodo 2 ---> ( 5, 0 )     [ ídem ]

Seguidamente, "tachamos" o "marcamos" el nodo 0 como definitivo, y con ellos hemos terminado el primer ciclio de la ejecución de nuestro algoritmo. Queda resaltar que un nodo "tachado" es un nodo que no se vuelve a revisar. El algoritmo terminará cuando todos los nodos estén "tachados".
Hasta ahora vamos así:

Continuación del algoritmo

El algoritmo continúa inspeccionando entre todos los nodos que no han sido tachados o marcados como definiitivos, pero tienen un peso total ya calculado menor a infinito. Esto es, los nodos 1, 2 y 3. De ellos, seleccionamos el de menor coste, que sería el nodo 3 y repetimos el proceso considerándolo como nodo inicial.

Al nodo 3 le suceden, exceptuando el propio nodo 0 que ya fue tachado (repito, los nodos tachados no se vuelven a revisar), los nodos 2 y 4. Sus costes totales se calcularían como:

Código [Seleccionar] Expandir


coste de nodo 2: (coste acumulado nodo 3) + (coste camino que une nodos 3 y 2) = 5 + 4 = 9
coste de nodo 4: (coste acumulado nodo 3) + (coste camino que une nodos 3 y 4) = 5 + 15 = 20

por lo tanto etiquetamos estos nodos sucesores del nodo 3 de la siguiente manera:

Código [Seleccionar] Expandir


nodo 2 ---> ( 9,  3 )     [ costo 9, procediendo del nodo 3 ]
nodo 4 ---> ( 20, 3 )     [ costo 20, procediendo del nodo 3 ]

Mejoramiento del coste

Obsérvese en la última etapa que hasta ahora llevamos del algoritmo, que el coste del nodo 2 mejoró de un valor 10 a un valor 9, al cambiar su antecesor y por lo tanto la ruta seguida.

Para ser más claros, el coste del nodo 2 al tomar la ruta que procede directamente desde el nodo 0 fue de 10. Pero al considerar la ruta que alcanza el nodo 2 desde el nodo 3, o sea la ruta 0-3-2, el coste total acumulado fue 5+4=9. Cuando esto ocurre tachamos la anterior etiqueta del nodo 2 que era (10,0), y la cambiamos por la etiqueta (9,3). Y esto lo debemos hacer cada vez que alcancemos un nodo que habíamos computado, pero esta vez desde una nueva ruta y con un costo menor.

El grafo nos va quedando así, y nótese como se mejora el coste del nodo 2. También nótese que tachamos el nodo 3, es decir lo marcamos como definitivo por eso no lo volveremos a revisar.

Siguiente paso

Revisamos ahora todos los nodos que tienen un coste calculado menor a infinito, en este caso los nodos 1,2  y 4. El de menor coste es el nodo 2, por lo tanto es el nodo que vamos a tomar como inicial.

Los sucesores del nodo 2 son los nodos 1, 4 y 5. Calculamos sus costes:

Código [Seleccionar] Expandir


nodo 1, a partir de 2: 9 + 2 = 11   (mejora el coste)
nodo 5, a partir de 2: 9 + 12 = 21
nodo 4, a partir de 2: 9 + 10 = 19 (mejora el coste)

Marcamos el nodo 2 como definitivo, y continuamos.

Siguiente paso

De los nodos no definitivos que quedan (1, 4 y 5) el de menor coste es el 1. Inspeccionamos sus sucesores, los nodos 5 y 6, al calcular los costes de estos resulta:

Código [Seleccionar] Expandir


nodo 5, a partir de 1: 11 + 4 = 15   (mejora el coste)
nodo 6, a partir de 1: 11 + 6 = 17

Tachamos el nodo 1 y continuamos.

b] Siguiente paso [/b]

De los nodos no definitivos que quedan (4, 5 y 6) el de menor coste es el 5. Inspeccionamos sus sucesores, los nodos 6, 7 y 4, al calcular los costes de estos resulta:

Código [Seleccionar] Expandir


nodo 6, a partir de 5: 15 + 8 = 23   (empeora el coste)
nodo 7, a partir de 5: 15 + 16 = 31
nodo 7, a partir de 5: 15 + 3 = 18

Nótese que al recalcular el nodo 6 desde el nodo 5 se obtiene más bien un costo peor, por lo cual se mantiene su costo anterior que era 17, desde el nodo 1.

Tachamos el nodo 5 y continuamos, nos debe quedar así:

Pasos finales

El algoritmo se continúa repitiendo los pasos anteriores, hasta que no queden nodos sin tachar, es decir, hasta que todos queden como definitivos.

Reconstrucción de la ruta más económica

Una vez terminado, podemos calcular la ruta del coste mínimo desde el nodo inicial 0, hasta cualquiera otro de nuestros nodos. Por ejemplo, desde el nodo 0 hasta el nodo 7, vemos que el coste total es 23 y la ruta se forma regresivamente de la siguiente manera

Código [Seleccionar] Expandir


el nodo 7, procede del nodo 4
el nodo 4, procede del nodo 5
el nodo 5, procede del nodo 1
el nodo 1, procede del nodo 2

etcétera, hasta llegar al nodo inicial. La ruta por lo tanto sería:

0 - 3 - 2 - 1 - 5 - 4 - 7

===================================================================
   PROGRAMA EN C++ PARA EL CALCULO DE LA RUTA MINIMA

Este es un pequeño programa que hice en C++ para computar el grafo anteriormente explicado usando el algoritmo de Dijkstra. Al cambiar la matriz de adyacencia por otra, se puede modificar el programa para trabajar con un grafo diferente. Claro, está un poco rudimentario, lo ideal sería poder pedir al usuario la matriz de adyacencia del grafo de forma interactica a través del teclado, pero hasta ahí no llegué por hoy jeje.

Codifiqué algunos "cout" para que el programa fuese imprimiendo los resultados de las distintas etapas del análisis, de modo que sea más explicativo o pedagógico. Por supuesto, el programa está dado a mejorar ya que esta es una versión muy básica pero es completamente funcional, sólo compilar y probar.

Para nuestro caso la salida final es (luego de imprimir información etapas previas del análisis, jeje)

Código [Seleccionar] Expandir


================================================================

Ruta mas economica entre nodo 0 y nodo 7:

0 - 3 - 2 - 1 - 5 - 4 - 7

Costo total: 23

Por otra parte, creo que el programa no está mal, no es demasiado extenso porque la parte que calcula el Dijkstra sólo llevó 113 líneas de código, el resto del código es inicializando la matriz, declarando los structs, etc.

Código (cpp) [Seleccionar] Expandir


#include <iostream>
#include <iomanip>
#include <list>

/* Definiendo la estructura etiqueta de nodo. Sus campos incluyen
* el número de nodo, el coste total del nodo, y su precedente. */
struct label {
   int nro; /* numero del nodo */
   int prev; /* nodo precedente (-1 para el nodo inicial )*/
   int peso; /* peso o coste total de la trayectoria que
* conduce al nodo, i.e., el coste total desde
* el nodo inicial hasta el actual. Un valor
* de -1 denota el infinito */
   int marca; /* si el nodo ha sido marcado o no */
};
typedef struct label label_t;

using namespace std;

void dijkstra( int, int **, int, int );

int main () {

   /* cantidad total de nodos */
   int numNodos = 8;

   /* Definiendo la matriz de adyacencia */
   int i, j, **A;

   if ( ( A = new int*[numNodos] ) == NULL ) return 1;
   for ( i = 0; i < numNodos; i++ )
      if ( ( A[i] = new int[numNodos] ) == NULL ) return 1;

   for ( i = 0; i < 8; i++ )
      for ( j = 0; j < 8; j++ )
         A[i][j] = 0;

   /* por simplicidad, completamos solo los pares de nodos conectados */
   A[0][1] = 16;
   A[0][2] = 10;
   A[0][3] = 5;

   A[1][0] = 16;
   A[1][2] = 2;
   A[1][5] = 4;
   A[1][6] = 6;

   A[2][0] = 10;
   A[2][1] = 2;
   A[2][3] = 4;
   A[2][4] = 10;
   A[2][5] = 12;

   A[3][0] = 5;
   A[3][2] = 4;
   A[3][4] = 15;

   A[4][2] = 10;
   A[4][3] = 15;
   A[4][5] = 3;
   A[4][7] = 5;

   A[5][1] = 4;
   A[5][2] = 12;
   A[5][4] = 3;
   A[5][6] = 8;
   A[5][7] = 16;

   A[6][1] = 6;
   A[6][5] = 8;
   A[6][7] = 7;

   A[7][4] = 5;
   A[7][5] = 16;
   A[7][6] = 7;

   /* Imprimir la matriz de adyacencia */
   cout << "Matriz de adyacencia:" << endl << endl;
   for ( i = 0; i < 8; i++ ) {
      for ( j = 0; j < 8; j++ )
         cout << setw(2) << A[i][j] << "  ";
      cout << endl;
   }
   cout << endl;

   /* calcular dijkstra a partir del nodo 0, a partir del nofo 7 */
   dijkstra( numNodos, A, 0, 7 );

   /* liberar memoria */
   delete [] A;
   for ( i = 0; i < numNodos; i++ )
      delete A[i];

   return 0;
}

/* Calcula el coste minimo de alcanzar un nodo final 'b'
* grafo no dirigido con N nodos, a partir del nodo inicial 'a',
* dada su matriz de adyacencia A */
void dijkstra( int N, int **A, int a, int b ) {

   label_t *Labels;
   int i, i0, j, peso;
   int *ruta; /* array de nodos de la ruta minima */

   /* Crea din'amicamente el arreglo de etiquetas de nodo */
   if ( ( Labels = new label_t[N] ) == NULL ) return;

   /* nodo inicial 'a' entre 0 y N - 1 */
   if ( a < 0 || a > N - 1 ) return;
   /* nodo final 'a' entre 0 y N - 1 */
   if ( b < 0 || b > N - 1 ) return;

   /* inicializar las etiquetas de nodo */
   for ( i = 0; i < N; i++ ) {
      Labels[i].nro = i;
      if ( i != a ) {
         Labels[i].prev = -1; /* a'un no se ha definido predecesor */
         Labels[i].peso = -1; /* infinito */
         Labels[i].marca = 0;
      }
      else {
         Labels[i].prev = -1; /* a'un no se ha definido predecesor */
         Labels[i].peso = 0; /* coste del nodo inicial a s'i mismo es cero */
         Labels[i].marca = 0;
      }
   }

   /* continuamos este ciclo mientras existan nodos no marcados */
   while ( 1 ) {
      /* busca entre todos los nodos no marcados el de menor peso, descartando los
       * de peso infinito (-1) */
      peso = -1;
      i0 = -1;
      for ( i = 0; i < N; i++ ) {
         if ( Labels[i].marca == 0 && Labels[i].peso >= 0 )
            if ( peso == -1 ) {
               peso = Labels[i].peso;
               i0 = i;
            }
            else if ( Labels[i].peso <= peso ) {
               peso = Labels[i].peso;
               i0 = i;
            }
      }
      if ( i0 == -1 ) { /* termina si no encuentra */
         cout << "Ya no quedan nodos por analizar." << endl;
         break;
      }

      cout << "*** Analizando nodo " << i0 << " ***" << endl;

      /* actualiza el peso de todos los sucesores (si los hay) del nodo
       * encontrado y luego se~nala dicho nodo como marcado */
      for ( i = 0; i < N; i++ ) {
         if ( A[i0][i] > 0 ) {
            /* si el coste acumulado sumado al coste del enlace del nodo i0 al nodo i
             * es menor al coste del nodo i (o si el coste del nodo i es infinito),
             * debemos actualizar */
            if ( Labels[i].peso == -1 || Labels[i0].peso + A[i0][i] < Labels[i].peso ) {
               if ( Labels[i0].peso + A[i0][i] < Labels[i].peso )
                  cout << "   [ mejorando coste de nodo " << i << " ]" << endl;
               Labels[i].peso = Labels[i0].peso + A[i0][i];
               Labels[i].prev = i0;
               cout << "   coste de nodo " << i << " desde nodo " << i0 << ": " << Labels[i].peso << endl;
            }
         }
      }
      Labels[i0].marca = 1;
      cout << "   [ nodo " << i0 << " marcado ]" << endl;

      /* para verificar, imprime los costes calculados hasta el momento */
      for ( i = 0; i < N; i++ ) {
         cout << i << ": [";
         if ( Labels[i].peso == -1 ) cout << "Inf";
         else cout << Labels[i].peso;
         cout << ", " << Labels[i].prev ;
         if ( Labels[i].marca == 1 ) cout <<  ", x]" << endl;
         else cout << "]" << endl;
      }
      cout << endl;

      /* pausa (opcional) */
      cout << "presione ENTER para continuar ...";
      cin.get();
   }

   /* Ruta desde el nodo 'a' hasta el nodo 'b' */
   int longitud = 2;
   i = b;
   while ( ( i = Labels[i].prev ) != a ) longitud++; /* primero estimamos la longitud de la ruta */
   if ( ( ruta = new int[longitud] ) == NULL ) return;

   ruta[longitud - 1] = b; /* luego rellenamos */
   i = b;
   j = 0;
   for ( j = 1; j < longitud; j++ ) {
      i = Labels[i].prev;
      ruta[longitud - j - 1] = i;
   }

   cout << "================================================================" << endl;
   cout << endl << "Ruta mas economica entre nodo " << a << " y nodo " << b << ":" << endl << endl;
   for ( i = 0; i < longitud; i++ ) {
      cout << ruta[i];
      if ( i < longitud - 1 ) cout << " - ";
   }
   cout << endl << endl << "Costo total: " << Labels[b].peso << endl << endl;

   delete ruta;
   delete [] Labels;
}

Leyendo en internet encontré la cita:

Cuidado con los tipos. Tengan en cuenta que por defecto C hace promoción de los parámetros pasados, así, si pasan un float, este será promovido a double y la sentencia va_arg(pa,float) será incorrecta. Lo mismo con shorts, etc. Normalmente el compilador nos avisará de esto.

El tema se refiere a funciones con número variable argumentos, donde lógicamente debemos avisar a la macro va_arg sobre el tipo esperado del siguiente argumento de la función. La verdad nunca antes había leído de ésto, pero según entiendo de la cita si se pasa un float a la función, de alguna manera promueve el argumento a double, i.e., reserva en la pila de argumentos, en el lugar asignado para el mismo, el espacio que ocupa un double en lugar del espacio que ocupa un float. En este caso desreferenciar el argumento (usando va_arg) como float dará un error, como es de suponer.

Tengo dos inquietudes: (1) ¿Cuándo ocurren dichas "promociones", y cómo podemos hacer entonces para trabajar de manera segura?

(2) Se me ocurre que una forma de controlar dichas promociones es hacer cast explícito de los argumentos pasados, ejemplo: f( (float) x, (float) y ), así invocará la función reservando en la pila de argumentos el espacio justo para argumentos de tipo float. ¿Es correcto?

Hola a todos. Hace tiempo instalé el escritorio kde pero no me agradó. Mi pregunta es ¿qué ficheros de configuración de inicio debo modificar en Ubuntu, para que arranque con escritorio gnome por defecto, en lugar de kde?

Hola a todos. Mi idea a mediano plazo es construir una calculadora "en linea", o sea por consola. No funcionaría con botones, sino que el usuario debe escribir una expresión algebraica, e.g. 2 + 3*(3-6)^2 la cual será evaluada. En el futuro, incluir funciones trigonométricas, exponenciales, etc., lo cual no debe ser difícil una vez se tenga la estructura básica funcionando. Quizá hasta con la opción de graficar. Es un proyecto bonito, porque al estar desarrollado en C estándar, se pudiera incluso compilar en un microprocesador de bajo costo (compatible con C) y hacer así una calculadora científica. Claro, esto sería bien en el futuro pero con algo hay que comenzar.

El primer reto a que debemos enfrentarnos es el tema de conversión de la notación "infija a posfija". Explico a continuación (es un poco extenso, los impacientes favor ir a dar una vuelta, jeje):

Para los humanos es natural la notación 'infija', donde el operador va en medio de los operandos: "5 + 2*3". En cambio para la máquina es natural la notación 'posfija' donde primero van los operandos y luego el operador. Esto es así porque a nivel de máquina primero deben copiarse los argumentos en los registros adecuados del procesador, y luego invocar la instrucción de suma (binaria).  En posfijo, la anterior expresión se escribiría como:

5 2 3 * +

y obśervese como primero debe ejecutarse el operador de mayor prioridad *, y luego +, para cumplir adecuadamente con la asociatividad implícita 5 + (2 * 3).

Ya encontré un algoritmo que explica cómo hacer el paso de una notación a la otra usando pilas, pero más que repetirlo textualmente quisiera encontrarle la lógica. Supóngase que tenemos una expresión del tipo:

A op1 B op2 C

donde A, B, C son los operandos, mientras op1 y op2 son operadores. A menos que existan paréntesis explícitos, la asociatividad viene determinada por la precedencia de dichos operadores. Ahora, disponemos de uns string para la notación infija, un string para la posfija (que debemos ir rellenando) y una pila para ir depositando algunos elementos transitorimente.

Caso 1.  Si op1 tiene mayor precedencia que op2, ejemplo "A * B + C", primero debe evaluarse el resultado de op1, luego el de op2. Entonces, copiamos A al string de posfijo, metemos op1 en la pila, copiamos B al string posfijo, sacamos op1 de la pila y lo pasamos al posfijo, metemos op2 en la pila, copiamos C al string posfijo, sacamos op2 de la pila y lo pasamos al string. Para explicarlo más claramente en forma de tabla.

Paso    |    Pila    |    Posfijo
-------------------------------------
1      |            |    A
2      |     op1    |   
3      |            |    A B
4      |     op2    |    A B op1         <-- sacamos op1 de la pila y lo pasamos al string
5      |     op2    |    A B op1 C       
6      |            |    A B op1 C op2

Caso 2.  Cuando op1 y op2 tienen igual precedencia, ejemplo "A + B + C". En este caso, la asociatividad debe ser de izquierda a derecha "(A + B) + C", por lo que se evalúa primero op1 y luego op2. Se procede exactamente de la misma manera que en el caso 1.

Caso 3.  Cuando op1 es de menor prioridad que op2, ejemplo "A + B * C". Aquí debe evaluarse "A + (B * C)". Esto significa que op1 debe esperar por el resultado de op2, el string posfijo deberá quedar "A B C op2 op1". En forma de tabla:

Paso    |    Pila    |    Posfijo
-------------------------------------
1      |            |    A
2      |     op1    |   
3      |            |    A B
4      |  op1, op2  |    A B           <-- no se saca op1 al momento de colocar op2
5      |            |    A B op2 op1   <-- vaciamos la pila

La diferencia con el caso 1 es que al momento de introducir op2 en la pila, no se saca antes op1. Esto es porque op2 tiene mayor precedencia que op1 entonces debe evaluarse primero, es decir, debe quitarse primero op2 de la pila y luego op1.

Uno puede resumir diciendo que al momento de colocar un nuevo operador en la pila, se sacan todos los operadores anteriormente depositados y que tengan mayor o igual jerarquía a la suya (y que deben evaluarse antes), estos operadores son pasados al string posfijo y el nuevo operador es depositado en la pila.

Con esta explicación precedente, se puede presentar el algoritmo para convertir infijo a posfijo. Debemos leer la expresión infija de izquierda a derecha y luego

* Los espacios son despreciados.
* Si el argumento leido es un operando (número), pasarlo al string posfijo.
* Si el argumento leido es un operador entonces:
  - Si la pila no está vacía, retirar todos los operadores con una precedencia
    mayor o igual al operador actual y pasarlos al posfijo, en el orden en que son retirados.
  - Colocar el nuevo operador en la pila.
* Si se lee un paréntesis izquierdo '(', depositarlo en la pila.
* Si se lee un paréntesis derecho ')', retirar de la pila todos los elementos hasta encontrar
  un '('. Dichos elementos son pasados al posfijo, menos el paréntesis '(' que es descartado.
* Al finalizar el proceso, pasar al posfijo cualquier elemento que haya quedado en la pila.

Entonces me puse manos a la obra. El programa está hecho en C++, que al usar clases STL se simplifica bastante (estoy pensando una versión en C puro, con código más elemental, útil quizás si se piensa migrar a un hardware más básico como un uC).

El programa recibe una cadena de notación infija y la convierte a posfija. Para propósitos de depuración se dan mensajes en pantalla sobre los pasos que van efectuando (funcionalidad que se debe quitar más adelante). Al final, evalúa el resultado y lo imprime. Por ejemplo, una cadena sencilla como:

5 + 2 * 3

produce la salida:

Código [Seleccionar] Expandir


Intro expresion infija: 5 + 2 * 3

Analizando token: '5'
es numero: pasado a posfijo

Analizando token: '+'
es operador:
colocar '+' en la pila

Analizando token: '2'
es numero: pasado a posfijo

Analizando token: '*'
es operador:
colocar '*' en la pila

Analizando token: '3'
es numero: pasado a posfijo

Pasado operador '*' de la pila a posfijo

Pasado operador '+' de la pila a posfijo

Posfijo es:
5 2 3 * +

Evaluando la expresion ...
operar 2*3 = 6
operar 5+6 = 11
El resultado es: 11


y un caso más complicado:

5 + 3*(4 - 7)^2 - 1

produce:

Código [Seleccionar] Expandir


Analizando token: '5'
es numero: pasado a posfijo

Analizando token: '+'
es operador:
colocar '+' en la pila

Analizando token: '3'
es numero: pasado a posfijo

Analizando token: '*'
es operador:
colocar '*' en la pila

Analizando token: '('
pasado a posfijo

Analizando token: '4'
es numero: pasado a posfijo

Analizando token: '-'
es operador:
colocar '-' en la pila

Analizando token: '7'
es numero: pasado a posfijo

Analizando token: ')'
pasado operador '-' de la pila a posfijo

Analizando token: '^'
es operador:
colocar '^' en la pila

Analizando token: '2'
es numero: pasado a posfijo

Analizando token: '-'
es operador:
pasado operador '^' de la pila a posfijo
pasado operador '*' de la pila a posfijo
pasado operador '+' de la pila a posfijo
colocar '-' en la pila

Analizando token: '1'
es numero: pasado a posfijo

Pasado operador '-' de la pila a posfijo

Posfijo es:
5 3 4 7 - 2 ^ * + 1 -

Evaluando la expresion ...
operar 4-7 = -3
operar -3^2 = 9
operar 3*9 = 27
operar 5+27 = 32
operar 32-1 = 31
El resultado es: 31


A continuación el código fuente, que es el trabajo de unas horas repartidas entre ayer y hoy:

Código (cpp) [Seleccionar] Expandir


#include <cstdlib>
#include <iostream>
#include <string>
#include <stack>
#include <cmath>

using namespace std;

/* Operadores matematicos */
#define N_operators 6
const string operators[N_operators] = {"+", "-", "*", "/", "%", "^"};
int precedences[N_operators] = {1, 1, 2, 2, 2, 3};

bool is_operator( const string );
int precedence( const string );

/* Mis sugerencias personales a este programa:
*
* - Considerar el cambio del nombre standby por aux_stack, u otro.
* - Incorporar el analizador lexico para expresiones numericas de punto
*   flotante, o que ocupen mas de un caracter.
* - Eliminar la cadena intermedia postfix, pasando directamente los
*   resultados de la pila de operadores extraidos de infix, a una pila
*   de evaluacion.
* - Incorporar operadores unarios, como sin(), cos(), exp(), log(), etc.
* - Detectar errores de sintaxis en la expresion infija.
* - Otros que sean recomendados.
*/

int main() {

string infix, postfix, token;
stack <string> standby;
stack <double> result;
size_t i;
char c;
double A, B;

/* Cadena de entrada */
cout << "Intro expresion infija: ">
getline( cin, infix );
cout << endl;

/*************************************************************
  PRIMERA PARTE: Procesar la cadena infijo, y crear posfijo
*************************************************************/
for ( i = 0; i < infix.size(); i++ ) {
/* esto debe cambiar luego a un token o palabra devuelta por
* el analizador léxico */
c = infix[i];
token.clear();
token += c; /* parece burdo, pero no conozco mejor manera de
* crear un string a partir de un unico caracter */

/* es un espacio: despreciar */
if ( c == ' ' ) continue;

cout << "Analizando token: '" << c << "'" << endl;

/* es un carácter numérico: pasar al posfijo */
if ( c >= '0' && c <= '9' ) {
cout << "\tes numero: pasado a posfijo" << endl << endl;
postfix = postfix + " " + c;
continue;
}

/* si se lee un operador: sacar de la pila y pasar al postfijo
* todos los operadores con una precedencia mayor o igual a la
* suya, y depositar el mismo en la pila */
if ( is_operator( token ) ) {
cout << "\tes operador:" << endl;
while ( !standby.empty() && precedence( standby.top() )
>= precedence( token ) ) {
cout << "\tpasado operador '" + standby.top() +
"' de la pila a posfijo" << endl;
postfix = postfix + " " + standby.top();
standby.pop();
}
standby.push( token );
cout << "\tcolocar '" << token << "' en la pila" << endl << endl;
continue;
}

/* si se lee "(": colocar en la pila */
if ( token == "(" ) {
cout << "pasado a posfijo" << endl << endl;
standby.push( token );
continue;
}

/* si se lee ")": retirar de la pila hasta encontrar '(', y pasar
* los elementos retirados a posfijo, luego descartar el "(" */
if ( token == ")" ) {
while ( !standby.empty() && standby.top() != "(" ) {
cout << "\tpasado operador '" + standby.top() +
"' de la pila a posfijo" << endl << endl;
postfix = postfix + " " + standby.top();
standby.pop();
}
if ( !standby.empty() )
standby.pop(); /* descartar el "(" */
}
}

/* extraer de la pila cualquier operador restante y pasarlo a la cadena posfijo */
while ( !standby.empty() ) {
cout << "Pasado operador '" + standby.top() +
"' de la pila a posfijo" << endl << endl;
postfix = postfix + " " + standby.top();
standby.pop();
}

/* Imprimir el posfijo */
cout << "Posfijo es: \n\t" << postfix << endl << endl;

/****************************************************************
  SEGUNDA PARTE: Procesar la cadena posfijo, y devolver resultado
****************************************************************/

A = 0;
cout << "Evaluando la expresion ..." << endl;
for ( i = 0; i < postfix.size(); i++ ) {

c = postfix[i];
token.clear();
token += c;

/* si se lee un operando (caracter numerico), depositar en la pila */
if ( c >= '0' && c <= '9' ) {
result.push( c - '0' );
continue;
}

/* si se lee un operador binario, poner en A y B los últimos dos argumentos
* de la pila y operarlos, guardando el resultado en la pila */
if ( is_operator( token ) ) {
if ( !result.empty() ) {
B = result.top();
result.pop();
}
else {
cout << "Argumentos insuficientes para '" << c << "'" << endl;
return -1;
}

if ( !result.empty() ) {
A = result.top();
result.pop();
}
else {
cout << "Argumentos insuficientes para '" << c << "'" << endl;
return -1;
}

cout << "\toperar " << A << token << B << " = ";
if ( token == "+" ) {
A += B;
result.push( A );
}
else if ( token == "-" ) {
A -= B;
result.push( A );
}
else if ( token == "*" ) {
A *= B;
result.push( A );
}
else if ( token == "/" ) {
A /= B;
result.push( A );
}
else if ( token == "%" ) {
A = (int )A % (int )B;
result.push( A );
}
else if ( token == "^" ) {
A = pow(A, B);
result.push( A );
}
cout << A << endl;
}
}

if ( !result.empty() )
cout << endl << "El resultado es: " << result.top() << endl;

return 0;
}

/* Verdadero si el token corresponde a un operador. */
bool is_operator( const string token ) {

for ( int i = 0; i < N_operators; i++ )
if ( operators[i] == token )
return true;

return false;
}

/* Devuelve la precedencia del operador descrito por el
* string token (-1 si no es un operador) */
int precedence( const string token ) {

for ( int i = 0; i < N_operators; i++ )
if ( operators[i] == token )
return precedences[i];

return -1;
}

Una pregunta a la comunidad. Como sabemos, el estándar POSIX provee un conjunto de métodos para interacción con el sistema operativo (crear o ejecutar procesos, conocer estados y permisos de ficheros, etc). En implementaciones de C para Linux (e UNIX en general) estas funciones están definidas en <unistd.h>. Y sabemos también que Windows es el campeón en desobedecer los estándares.

Mi pregunta es cómo hacer algo similar, por ejemplo crear un proceso hijo con fork(), a través de un programa elaborado en C para el sistema operativo Windows. Y así por ejemplo crear demonios personalizados para tareas de sistema. O también podría ser crear tuberías, comunicar procesos, etc.

La distribucion MinGW para Windows contempla algunas funciones de este tipo, por ejemplo en <dirent.h> está la función de leer directorios readdir(), y en <unistd.h> tenemos chdir() para cambiarnos de directorio. Pero no vi nada de procesos hijos, tuberías, etc.

Buenos días moderadores, la presente es para proponer la siguiente idea para el foro. Habilitar una especie de Salón de la Fama para los temas más destacados. Por ejemplo he visto varios aquí en el foro de C/C++ que merecerían estar allí.

Temas que sobrepasen una simple duda o consulta, y más bien sean aplicaciones desarrolladas entre los distintos miembros de la comunidad, funcionales, depuradas y libres de errores, con sus respectivos y debidos comentarios, ficheros de cabecera, su código claro y legible, macros #define para hacerlo configurable e incluso capacidad para compilarse en varios sistemas, quizá su Makefile, etc., .... en fin algo completo y refinado.

Sería una manera de recompensar a los autores por tan prolijo trabajo, que no tiene que ser extenso, pero sí bien pulido y acabado, y por otra parte enriquecería considerablemente el foro con esos aportes.

Sería bonito, nos repartimos el trabajo entre varios del foro, cada quién hace una parte y luego la ensamblamos. Sería como para abrir una sección de temas y proyectos abiertos en el foro.

Es sólo una propuesta para ser considerada ..... Yoel.

Hace un tiempo un usuario me rcomendó escribir y compartir un programa que trabaje sobre el triángulo de Pascal. La verdad no es difícil generar el triángulo, así que para añadir más gusto decidí ir más allá y generar el binomio de Newton de un exponente arbitario. Pero antes de proseguir en este tema vamos a señalar algunas consideraciones teóricas (tal vez para quiénes ya olvidaron sus clases de mate, jeje).

En álgebra, al desarrollar (a+b)^2, obtenemos:

a^2 + 2ab + b^2

y para (a+b)^3:

a^3 + 3a^2b + 3ab^2 + b^3

Pues bien, lo que se quiere es el desarrollo para una potencia entera positiva cualquiera, y que lo imprima "con formato". Es decir, una línea para la base y otra para los exponentes:

3     2       2    3
a  + 3a b + 3ab  + b


Para obtener el desarrollo general necesitamos el triángulo de Pascal (http://es.wikipedia.org/wiki/Tri%C3%A1ngulo_de_Pascal). Las tres primeras líneas del triángulo son:

  1
1 1
1 2 1

y se construye de esta manera: todas las filas empiezan y terminan con 1, además de la tercera filas en adelante cada elemento se obtiene sumando los dos que tiene directamente arriba, uno a la derecha y otro a la izquierda. En la tercera fila, el "2" se obtuvo sumando 1 + 1 de este modo. Vamos con 4 filas:

   1
  1 1
1 2 1
1 3 3 1

y ahora el primer "3" de la 4ta fila es la suma 1 + 2 de los elementos que tiene arriba suyo, el otro "3" es la suma 2 + 1, y así sucesivamente.

Pues bien, el j-ésimo elemento de la i-ésima fila del triángulo (empezando los índices en cero) se llama coeficiente binomial que por falta de una mejor simbología en este portal representaré como <i,j>. Con ésto, el binomio (a + b)^N se desarrolla como la suma desde i=0 hasta i=N de los términos de la forma <N,i> * a^(N-i) * b^i. O sea, por ejemplo:

(a + b)^3 = <3,0>*a^3 + <3,1>*a^2*b + <3,2>*a*b^2 + <3,3>*b^3

los coeficientes binomiales <3,j> no son más que los elementos de la cuarta fila del triángulo:

   1
  1 1
1 2 1
1 3 3 1

por tanto

(a + b)^3 = 1*a^3 + 3*a^2*b + 3*a*b^2 + 1*b^3
          = a^3 + 3a^2b + 3ab^2 + b^3

y por supuesto, para desarrollar el binomio de orden N necesitamos construir el triángulo de N+1 filas.

Bueno, y ya  . La parte de hacer todos los cálculos no encierra nada que no se pueda comprender leyendo el código fuente, y sus respectivos comentarios. Lo más desafiante (para mí) fue hacer la presentación "formateada" que expliqué antes. Usando algúun tipo de función gotoxy() o su equivalente es fácil, pues nos movemos a la línea de arriba para escribir los exponentes, y a la de abajo para el resto de la expresión. Sin embargo esta función no es portable por lo que decidí no usarla.

En su lugar pensé hacer algo similar a cómo las pantallas LCD que los aparatitos electrónicos. Una matriz de celdas donde cada celda permite representar un carácter. Un programa debe calcular todas las letras y mandar a imprimirlas. Bueno, ..... creo que la idea quedó clara, se debe disponer una matriz "board" o tablero de dos filas, e ir rellenando los caracteres adecuados. Luego que se tenga toda la expresión formada, se imprimen con funciones estándares.

El problema es que se debe calcular en tiempo de ejecución el ancho total de las líneas, dependiendo de la potencia del binomio que se quiera. Tomar en cuenta también que los números ocupan un ancho fijo, porque para potencias grandes pueden ser de una, dos, tres cifras, etc. También tener presente que los coeficientes iguales a 1 no se imprimen, como tampoco los exponentes iguales a 1. Este programa, tal como está desarrollado, está limitado a expresiones cuyo ancho sea menor o igual que la pantall (no hace "salto" de línea).

Otra dificultad fue hacerlo enteramente en C (sin usar clases), por eso malloc() y free() por varias partes, jeje. El argumento (potencia del binomio) está pasado como argumento de la línea de comandos. Así que probándolo con potencia 3:

./binomio 3

nos da:

(a + b)^3 es:

3     2       2    3
a  + 3a b + 3ab  + b

y para divertirnos un poco, con potencia 7:

(a + b)^7 es:

7     6       5 2      4 3      3 4      2 5      6    7
a  + 7a b + 21a b  + 35a b  + 35a b  + 21a b  + 7ab  + b


Vamos con el código:

Código (cpp) [Seleccionar] Expandir


#include <stdlib.h>
#include <stdio.h>
#include <string.h>

int ** pascal( const int );
int ** tartaglia( const int );
void destroy_pascal( int **, const int );
void destroy_tartaglia( int **, const int );
int digits( int );

int main(int argc, char* argv[]) {

   int **A, N;
   int i;
   int width, col;
   char *board[2];

   /* Verificando integridad de los datos */
   if ( argc < 2 )
      return -1;
   N = atoi( argv[1] );

   if ( N < 0 ) {
      printf("Solo para N >= 0\n");
      return -1;
   }
   if ( N == 0 ) {
      printf("a + b\n");
      return -1;
   }

   /* Coeficientes de pascal */
   A = pascal( N );

   /* Calculamos el ancho total de la cadena */
   width = 0;
   for ( i = 0; i <= (float)N/2; i++ ) {
      if ( i == 0 ) /* terminos a^N, y b^N */
         width += 2 * ( 1 + digits(N) );
      if ( i == 1 ) /* terminos a^(N-1)*b, y a*b^(N-1) */
         width += 2 * ( 2 + digits(A[N][i]) + digits(N-1) );
      if ( i > 1 ) /* terminos a^(N-i)*b^i */
         if ( !(N % 2) && i == (float)N/2 )
            /* termino central se suma solo una vez */
            width += 2 + digits(A[N][i]) + digits(N-1) + digits(i);
         else
            /* y los restantes, dos veces */
            width += 2 * ( 2 + digits(A[N][i]) + digits(N-1) + digits(i) );
   }
   /* cadenas " + " */
   width += 3 * N;

   /* Representacion final */
   if ( ( board[0] = malloc( (width + 1) * sizeof(char) ) ) == NULL )
      return -1;
   if ( ( board[1] = malloc( (width + 1) * sizeof(char) ) ) == NULL )
      return -1;

   memset( board[0], ' ', width + 1);
   memset( board[1], ' ', width + 1);
   col = 0;
   for ( i = 0; i <= N; i++) {
      if ( A[N][i] != 1 ) { /* binomial N sobre i */
         col += sprintf( board[1] + col, "%d", A[N][i] );
         board[1][col] = ' ';
      }
      if ( N - i > 0 ) /* base 'a' */
         board[1][col++] = 'a';
      if ( N - i > 1 ) { /* exponente N - i */
         col += sprintf( board[0] + col, "%d", N - i);
         board[0][col] = ' ';
      }
      if ( i > 0 ) /* base 'b' */
         board[1][col++] = 'b';
      if ( i > 1 ) { /* exponente i */
         col += sprintf( board[0] + col, "%d", i);
         board[0][col] = ' ';
      }
      if ( i < N ) {
         col += sprintf( board[1] + col, " + ");
         board[1][col] = ' ';
      }
   }
   board[0][width] = '\0';
   board[1][width] = '\0';
   printf( "(a + b)^%d es:\n\n%s\n%s\n", N, board[0], board[1] );

   /* Liberando memoria, y saliendo */
   free( board[0] );
   free( board[1] );
   destroy_pascal( A, N);
   return 0;
}

/* Construye una matriz que contiene los numeros del triangulo
* de Pascal o Tartaglia de orden N > = 0, con N + 1 filas.
* La matriz es tal que A[i][j] corresponde al binomial (i : j).
* Se devolverá NULL si N < 0, o si no se pudo asignar memoria
* para construir la matriz.
*/
int ** pascal( const int N ) {

   int **A;
   int i, j;

   if ( N < 0 ) return NULL;

   if ( ( A = malloc( (N + 1) * sizeof(int *) ) ) == NULL ) return NULL;
   for ( i = 0; i < N + 1; i++ )
      if ( ( A[i] = malloc( (i + 1) * sizeof(int) ) ) == NULL ) return NULL;

   for ( i = 0; i < N + 1; i++ ) {
      A[i][0] = 1;
      A[i][i] = 1;
      /* solo se ejecuta si i > 1 */
      for ( j = 1; j < i; j++ )
         A[i][j] = A[i-1][j-1] + A[i-1][j];
   }

   return A;
}

/* Destruye el objeto creado por la función pascal() */
void destroy_pascal( int ** A, const int N ) {

   int i;

   if ( N < 0 ) return;

   for ( i = N; i >= 0; i-- ) {
      free( A[i] );
      A[i] = NULL;
   }
   free( A );
   A = NULL;
}

/* Un sinónimo de pascal( N ) */
int ** tartaglia( const int N ) {

   return pascal( N );
}

/* Un sinónimo de destroy_pascal( N ) */
void destroy_tartaglia( int ** A, const int N ) {

   return destroy_pascal( A, N );
}

/* Calcula la cantidad de cifras o digitos que conforman un
* numero entero no negativo;
*/
int digits( int N ) {

   int count = 1;

   if ( N < 0 ) return 0;
   if ( N == 0 ) return 1;

   while ( ( N = (N / 10) ) > 0 )
      count++;

   return count;
}

Hola, comparto un programilla que puede ser útil en este mismo foro. Encuentro que al subir código con la etiqueta code, los tabuladores son reemplazados por una cantidad de espacios que a mi entender son demasiados (son como 8). El código entonces toma una aparienci anti-estética  . Se me ocurrió hacer un programa llamado "tab" que reemplace todos los TAB en el fichero .c original por una cantidad de espacios determinada, y vuelque su salida a un fichero auxiliar, cuyo contenido copiaré dentro de la etiqueta code.

La sintaxis (UNIX)

./tab fichero_entrada fichero_salida N_spaces

y en DOS quitar el "./" que antecede a tab. Por ejemplo, "tab code.c code2.c 3". Si no se indica N_spaces se toman 3, y si no se indica fichero de salida toma la salida estándar.

Código (cpp) [Seleccionar] Expandir


#include <stdlib.h>
#include <stdio.h>

/* Este programa reemplaza los caracteres TAB del fichero de texto
* pasado como primer argumento por una cantidad determinada de espacios,
* y escribe su salida en el fichero pasado como segundo argumento.
* El tercer argumento (opcional) especifica cuántos caracteres ' '
* reemplazarán el TAB, y si no se indica, se tomará una cantidad de tres.
*/

int main( int argc, char *argv[]) {
   
   int i, N_spaces;
   char c;
   char * in_fname, * out_fname;
   FILE * in_fptr = NULL, * out_fptr = NULL;
   
   if ( argc < 2 ) {
      printf("Use:\n tab in_file out_file\n tab in_file out_file N_spaces\n");
      goto failure;
   }
   
   in_fname = argv[1];
   
   if ( argc > 3 ) {
      N_spaces = atoi( argv[3] );
      if ( N_spaces < 1 )
         N_spaces = 3;
      }
   else
      N_spaces = 3;
   
   if ( ( in_fptr = fopen( in_fname, "r" ) ) == NULL ) {
      printf( "No existe o no se pudo abrir '%s'\n", in_fname );
      goto failure;
   }
   
   /* toma stdout si falta fichero de salida */
   if ( argc < 3 )
      out_fptr = stdout;
   else   {
      out_fname = argv[2];
      if ( ( out_fptr = fopen( out_fname, "w" ) ) == NULL ) {
         printf( "Imposible crear, abrir o escribir en '%s'\n", out_fname );
         goto failure;
      }
   }
   
   /* reemplazando TAB por N_spaces caracteres ' ' */
   while ( ( c = fgetc( in_fptr ) ) != EOF ) {
      if ( c != '\t' )
         fputc( c, out_fptr );
      else
         for ( i = 0; i < N_spaces; i++ )
            fputc( ' ', out_fptr );
   }
   
   if ( in_fptr != NULL ) fclose( in_fptr);
   if ( out_fptr != NULL ) fclose( out_fptr);
   return 0;
   
failure:
   if ( in_fptr != NULL ) fclose( in_fptr);
   if ( out_fptr != NULL ) fclose( out_fptr);
   return -1;
}

NOTA. Una alternativa es la utilería "sed" (UNIX), pero no se si tiene alternativa Windows.

Hola, preciso ayuda de los Linuxeros. Este sencillo código (que mide el tiempo transcurrido entre el inicio del programa y la pulsación de ENTER) no funciona como debe en Linux. En Windows lo probé y está Ok.

El problema es que clock() devuelve siempre cero (0), tanto para t1 como para t2, y por eso no mide el tiempo. ¿Qué es lo que le falta "ajustar" para que funcione en plataformas Linux y/ similares?

Código (cpp) [Seleccionar] Expandir


#include <stdio.h>
#include <time.h>

int main( ) {

clock_t t1, t2;

t1 = clock();
getchar();
t2 = clock();
printf("Han transcurrido %.2lf s\n", (double)(t2 - t1)/CLOCKS_PER_SEC );

}

En esta ocasión quiero compartir un programita divertido que muestra de manera interactiva la ejecución del algoritmo de ordenamiento por inserción. Básicamente va ordenando el arreglo e indicando por pantalla lo que va haciendo: cómo se mueven los elementos y cómo va quedando el vector tras cada paso ....

Un programita amigable y con un propósito bien didáctivo .... enjoy it!!

Código (cpp) [Seleccionar] Expandir


#include <stdio.h>
#include <stdlib.h>
 
#define N 5
 
int main(void) {

int x[N] = {7, 3, 11, 5, 1};
int i, j, k;
int aux;

printf("Arreglo original: \n");
for (k = 0; k < N; k++)
printf(" %d", x[k]);
printf("\n");

for (i = 1; i < N; i++) {

/* buscamos desde 0 hasta i - 1, el primer elemento que sea
* mayor que x[i] */
printf("ubicando %d ...", x[i]);
j = 0;
while (j < i && x[j] <= x[i])
j++;

if ( j < i ) {

/* insertar x[i] en la posición j, y desplazar los
* restantes elementos hacia la derecha */
printf(" poner en posicion %d\n", j);

for (k = 0; k < N; k++)
printf(" %d", x[k]);
printf("  -> ");

aux = x[i];
for (k = i; k > j; k--)
x[k] = x[k-1];
x[j] = aux;

for (k = 0; k < N; k++)
printf(" %d", x[k]);
printf("\n");
}
else
printf(" sin cambios\n");
}
printf("El arreglo final ordenado es:\n");
for (i = 0; i < N; i++)
printf(" %d", x[i]);
printf("\n");

return 0;
}

A veces cuando colocamos fragmentos de código muy grandes en nuestros posts, los mismos se hacen de una extensión inmensa. Imagínense si se trata de un proyecto grande con varias cabecera, y fuentes ...

Me gustaría saber si ustedes recomienda un sitio externo especializado en subir archivos fuentes de C, y colocar en nuestros post sólo el link a dichos sitios

.......... 

[Ojo:]

Hola a todos. En esta ocasión quiero compartir un trabajo con la comunidad. También se aceptan críticas (de buena fe), sugerencias, etc ...

A veces queremos leer texto organizado en forma de tabla, con filas y columas. Por ejemplo, a partir de un fichero de texto formateado en columnas, o en el resultado de convertir una hoja de cálculo a un .txt
En tales ocasiones es común crear una matriz bidimensional de cadenas para almacenar los datos.

Como es una tarea rutinaria y repetitiva, quise desarrollar una clase "StringMatrix" de matriz de cadenas. Dicha clase posee su respectivo constructor por defecto, un constructor de copia (para obtener un objeto nuevo como copia idéntica del contenido de otro), un operador de asignación (para hacer el contenido de un StringMatrix idéntido al de otro), así como los tradicionales getElement y putElement para obtener y colocar elementos desde y en la matriz. Funcionan así:

Código (cpp) [Seleccionar] Expandir


putElement(i, j, str);
escribe el contenido del string str en la posición (i,j) de la matriz (los valores de los índices empiezan en cero). Es de hacer notar que trabaja "por copia", esto es, el elemento (i,j) reserva su espacio de memoria propio donde copia el contenido de str, luego el propio str puede alterado luego sin afectar el contenido de la matriz. Por otra parte, si se pide asignar en una posición que excede el tamaño de la matriz, se intenta dimensionar la misma previamente. Devuelve -1 en caso de error (por ejemplo, si falla la asignación de memoria), y 0 en caso de éxito.

Código (cpp) [Seleccionar] Expandir


str = getElement(i, j);
devuelve en str una copia del contenido del elemento (i,j) de la matriz. Es importante que devuelva un valor "por copia", pues así podemos alterar el string str devuelto sin afectar la matriz original.

Los métodos NRows() y NCols(), que no toman argumentos, devuelven la cantidad de filas y columnas, respectivamente, de la matriz (al crear el objeto, estos números valen cero). Por su parte, los métodos addRow() y addColumn() sirven para añadir una fila o una columna a la matriz.

Finalmente el destructor como era de esperarse libera toda la memoria dinámicamente asignada y retorna. Se cuenta con un método peculiar Reinitialize() el cual también libera la memoria asignada y pone las dimensiones de la matriz a cero. Es similar al destructor, excepto que no destruye al objeto (éste sigue vivo) sino que lo pone en las mismas condiciones de cuándo fue creado. Es como "vaciar" la matriz para poder llenarla de nuevo.

CONDICIONES DE PRECAUCIÓN: Es de hacer notar que si el objeto no se crea con éxito (falla la petición de memoria realizada), sus dimensiones se ponen en -1. Los métodos getElement() y putElement() inspeccionan primero si existe esta condición de error y en dicho caso no se ejecutan. De un modo similar los métodos addRow() y addColumn() inspecionan si la petición de memoria fue exitosa y sólo en ese caso incrementan el contador de filas o de columnas. En caso contrario, no se añade ninguna fila o columna, y las dimensiones de la matriz permanecen iguales.

En mi opinión pueden mejorarse algunas cosas, como los nombres de los métodos (quizá addCol() en lugar de addColumn()), y añadir la posibilidad de eliminar una fila o columna solamente. También incorporar un método para redimensionar, que automáticamente añada las filas o columnas que hagan falta si se pasa de una dimensión menor a una mayor, o elimine las que sobren en caso contrario.

Aquí el fichero de cabecera de la clase. Ojo: el que algunos comentarios están en inglés no significa que me lo haya copiado de internet , sino que los puse en ese idioma por si navegando por el inmenso mundo que es la web, este código llega a ser leído fuera de fronteras hispanas (jeje, aunque eso requeriría mucha suerte  )

Código (cpp) [Seleccionar] Expandir


/* SMATRIX.H
* Declaración de la clase sMatrix
* Las funciones miembro están definidas en smatrix.cpp
*
* Por Yoel Monsalve.
*/

#ifndef SMATRIX_H
#define SMATRIX_H

/*** Definición de la clase StringMatrix ***/
class StringMatrix { // matriz de cadenas de caracteres
public:
StringMatrix(); /* constructor por defecto */
StringMatrix( StringMatrix & ); /* constructor de copia */
~StringMatrix(); /* destructor */
void ReInitialize(void);
char *getElement(int, int);
int putElement(int, int, const char *);
int NRows();
int NCols();
int addRow(); /* añadir una fila: devuelve 0 si tuvo éxito, -1 si no tuvo */
int addColumn(); /* añadir una columna: devuelve 0 si tuvo éxito, -1 si no tuvo */s

StringMatrix &operator = (StringMatrix &);
private:
char ***Matrix; /* para almacenar físicamente los elementos de la matriz */
int _NRows; /* cantidad de filas */
int _NCols; /* cantidad de columnas */
};

#endif

y ahora el código fuente de la clase:

Código (cpp) [Seleccionar] Expandir


/* SMATRIX.CPP
* Definiciones de funciones miembro de la clase sMatrix.
*
* Por Yoel Monsalve.
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include "smatrix.h"

/* Default constructor.
* Constructor por defecto. */
StringMatrix :: StringMatrix( ) {

Matrix = (char ***) malloc( sizeof(char **) );

if (Matrix != NULL)
_NRows = _NCols = 0; /* success */
else
_NRows = _NCols = -1; /* constructor failed !!! */
}

/* Copy constructor. Creates a new object as a copy of other object.
* Constructor de copia. Crea un nuevo objeto como una copia de otro objeto. */
StringMatrix :: StringMatrix ( StringMatrix &S ) {

int i, j;

Matrix = (char ***) malloc( sizeof(char **) );
if (Matrix != NULL)
_NRows = _NCols = 0; /* success */
else {
_NRows = _NCols = -1; /* constructor failed !!! */
return;
}

/* resize at the same size of S */
if ( S.NRows() < 0 || S.NCols() < 0 ) return;
while ( _NRows < S.NRows() )
addRow();
while ( _NCols < S.NCols() )
addColumn();

printf("%d, %d\n", S.NRows(), S.NCols());
/* and copy here the content of S */
for ( i = 0; i < _NRows; i++ )
for ( j = 0; j < _NCols; j++ )
Matrix[i][j] = S.getElement(i, j);
}

/* Assignment operator, from other StringMatrix object.
* Operador de asignacióm, a partir de otro objeto StringMatrix. */
StringMatrix & StringMatrix :: operator = (StringMatrix &S) {

int i, j;

/* avoid self-assignment */
if ( &S == this ) return *this;

/* caution if matrix creation failed */
if ( _NRows < 0 || _NCols < 0 )
return *this;

/* resize at the same size of S */
if ( S.NRows() < 0 || S.NCols() < 0 ) return *this;
while ( _NRows < S.NRows() )
addRow();
while ( _NCols < S.NCols() )
addColumn();

/* and copy here the content of S */
for ( i = 0; i < _NRows; i++ )
for ( j = 0; j < _NCols; j++ )
Matrix[i][j] = S.getElement(i, j);
}

/* "Re-initializes" the object. Frees the dinamic allocated memory, and
* it puts the dimensions to zero. This is, returns he object to the original
* state like it was created.
*
* "Re-inicializa" el objeto. Libera la memoria dinámicamente asignada,
* y pone las dimensiones a cero. Es decir, devuelve el objeto al estado
* original como fue creado */
void StringMatrix :: ReInitialize( ) {

int i, j;

/* if matrix creation failed, try create it again */
if ( _NRows < 0 || _NCols < 0 ) {
Matrix = (char ***) malloc( sizeof(char **) );
if (Matrix != NULL)
_NRows = _NCols = 0; /* success */
else {
_NRows = _NCols = -1; /* constructor failed !!! */
return;
}
}

/* frees the allocated memory space */
if (_NRows > 0) {
for (i = 0; i < _NRows; i++) {
if (_NCols > 0) {
for (j = 0; j < _NCols-1; j++)
free(Matrix[i][j]);
Matrix[i][j] = NULL;
}
free(Matrix[i]);
Matrix[i] = NULL;
}
}
_NRows = _NCols = 0;
}

/* Class destructor /
* Destructor de la clase */
StringMatrix :: ~StringMatrix( ) {
int i, j;

/* frees the allocated memory assigned to the objects /
* libera el espacio de memoria asignado a los objetos */
for (i=0; i<_NRows; i++) {
for (j=0; j<_NCols; j++) {
free( Matrix[i][j] );
Matrix[i][j] = NULL;
}
free( Matrix[i] );
Matrix[i] = NULL;
}
free( Matrix );
Matrix = NULL;

_NRows = -1;
_NCols = -1;
}

/* Get the number of rows of the matriz /
* Obtener el numero de filas de la matriz */
int StringMatrix :: NRows( ) {

return _NRows;
}

/* Get the number of columns of the matriz /
* Obtener el numero de columnas de la matriz */
int StringMatrix :: NCols( ) {

return _NCols;
}

/* Get an specific element in the matrix. Warning: the indexes start in zero.
* On success is returned a copy of the string stored in such element of
* the matrix. On error, returns NULL.

/* Obtener un elemento especifico de la matriz. Cuidado: los índices empiezan
* en cero. En caso exitoso devuelve una copia de la cadena almacenada en
* dicho elemento de la matriz. En caso de error, devuelve NULL. */
char * StringMatrix :: getElement( int i, int j ) {

char *s;

/* caution if matrix creation failed */
if ( _NRows < 0 || _NCols < 0 )
return NULL;

/* must be 0 <= i <= _N_Rows - 1, and 0 <= j <= _NCols - 1 */
if (i < 0 || i >= _NRows || j < 0 || j >= _NCols)
return NULL;

if ( ( s = (char *) malloc ( (strlen(Matrix[i][j]) + 1) * sizeof(char) ) ) == NULL )
return NULL;

strcpy(s, Matrix[i][j]);
return s;
}

/* Puts an element in a specified position of the matrix. If the position
* exceed the size of matrix, the same is automatically resized.
* On success returns 0, and -1 otherwise.
*
* Pone un elemento en una posicion especificada de la matriz. Si la posicion
* excede el tamano de la matriz, la misma es redimensionada automaticamente.
* Devuelve 0 si tuvo exito, -1 si no tuvo. */
int StringMatrix :: putElement( int i, int j, const char * s ) {

char *cPtr;

/* caution if matrix creation failed */
if ( _NRows < 0 || _NCols < 0 )
return -1;

/* fail if i < 0, or j < 0 */
if ( i < 0 | j < 0 )
return -1;

/* if i > _NRows - 1, completed rows that are needed */
while ( i >= _NRows )
addRow();

/* if j > _NCols - 1, completed columns that are needed */
while ( j >= _NCols )
addColumn();

/* now, copies the s string in the (i,j) element of the matrix (allocates
* memory before) */
if ( ( cPtr = (char *) realloc( Matrix[i][j], (strlen(s) + 1) * sizeof(char) ) ) != NULL ) {
strcpy(cPtr, s);
Matrix[i][j] = cPtr;
return 0;
}
else
return -1;

}

/* Add a row to the matrix. On success returs 0, and -1 otherwise.
*
* Anade una fila a la matriz. Devuelve 0 si tuvo éxito, -1 si no tuvo. */
int StringMatrix :: addRow() {

char ***xPtr;
char **yPtr;
char *zPtr;
int j;

/* caution if matrix creation was failed */
if ( _NRows < 0 ) return -1;

/* allocate memory for one more row */
if ( ( xPtr = (char ***) realloc( Matrix, (_NRows + 1) * sizeof(char **) ) ) != NULL ) {
Matrix = xPtr;

/* if matrix already has columns added */
if ( _NCols > 0 ) {
/* complete the new row with empty elements */
if ( ( yPtr = (char **) malloc( _NCols * sizeof(char *) ) ) != NULL ) {
Matrix[_NRows] = yPtr;
for (j = 0; j < _NCols; j++) {
if ( ( zPtr = (char *) malloc( sizeof(char) ) ) != NULL ) {
Matrix[_NRows][j] = zPtr;
*zPtr = '\0';
}
else
return -1;
}
}
else
return -1;
}
/* otherwise */
else {
/* complete the new row with empty elements */
if ( ( yPtr = (char **) malloc( 1 * sizeof(char *) ) ) != NULL ) {
Matrix[_NRows] = yPtr;
if ( ( zPtr = (char *) malloc( sizeof(char) ) ) != NULL ) {
Matrix[_NRows][0] = zPtr;
*zPtr = '\0';
}
else
return -1;
}
else
return -1;
}
}
else
return -1;

/* Success, then increase _NRows and return. */
_NRows++;
return 0;
}

/* Add a column to the matrix. On success returs 0, and -1 otherwise.
*
/* Anade una columna a la matriz. Devuelve 0 si tuvo éxito, -1 si no tuvo. */
int StringMatrix :: addColumn() {

char **yPtr;
char *zPtr;
int i;

/* return if matrix creation was failed */
if (_NRows <= 0 || _NCols < 0) return -1;

for (i = 0; i < _NRows; i++) {
/* allocate memory for one more column */
if ((yPtr = (char **) realloc( Matrix[i], (_NCols + 1) * sizeof(char *) ) ) != NULL ) {
Matrix[i] = yPtr;
if ( ( zPtr = (char *) malloc( sizeof(char) ) ) != NULL ) {
Matrix[i][_NCols] = zPtr;
*zPtr = '\0';
}
else
return -1;
}
else
return -1;
}

/* Success, then increase _NCols and return. */
_NCols++;
return 0;
}

Podemos ver ahora su funcionamiento, en el sencillo archivo de prueba que crea dos matrices, llena una con cuatro cadenas. Luego, en la segunda matriz se copia el contenido de la primera, y éste se imprime por la pantalla ¡Fácil!

Código (cpp) [Seleccionar] Expandir


#include <stdio.h>
#include <smatrix.h>       /* fichero de cabecera de la clase */

int main() {

StringMatrix S, M;
int i, j;

S.putElement(0, 0, "hugo");
S.putElement(0, 1, "paco");
S.putElement(1, 0, "maria");
S.putElement(1, 1, "luisa");

/* copia contenido de S en M */
M = S;
/* y lo imprime en pantalla */
for (i = 0; i < 2; i++) {
for (j = 0; j < 2; j++)
printf("%s\t", M.getElement(i, j) );
fputs("\n", stdout);
}

return 0;
}

NOTA: para compilar el fichero de prueba, llamado por ejemplo test.cpp, enlazado con el fichero smatrix.cpp que define la clase StringMatrix, usar la orden:

g++ -o test test.cpp smatrix.cpp

y suponiendo que los tres archivos test.cpp, smatrix.cpp y smatrix.h están en el mismo directorio. Para un proyecto grande valdría la pena crear directorios src, include, lib donde poner los ficheros apropiados y compilar adecuadamente según el caso. Se puede también hacer una biblioteca con esta y otras clases de utilería, ustedes ya saben ...

Sugerencias, comentarios ?????