elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Como proteger una cartera - billetera de Bitcoin


  Mostrar Temas
Páginas: [1] 2
1  Programación / Programación C/C++ / Algoritmo de Dijkstra paso a paso en: 2 Enero 2015, 23:00 pm
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:



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:
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:
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:
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:
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:
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:
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:
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:
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:
================================================================

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
  1. #include <iostream>
  2. #include <iomanip>
  3. #include <list>
  4.  
  5. /* Definiendo la estructura etiqueta de nodo. Sus campos incluyen
  6.  * el número de nodo, el coste total del nodo, y su precedente. */
  7. struct label {
  8.   int nro; /* numero del nodo */
  9.   int prev; /* nodo precedente (-1 para el nodo inicial )*/
  10.   int peso; /* peso o coste total de la trayectoria que
  11. * conduce al nodo, i.e., el coste total desde
  12. * el nodo inicial hasta el actual. Un valor
  13. * de -1 denota el infinito */
  14.   int marca; /* si el nodo ha sido marcado o no */
  15. };
  16. typedef struct label label_t;
  17.  
  18. using namespace std;
  19.  
  20. void dijkstra( int, int **, int, int );
  21.  
  22. int main () {
  23.  
  24.   /* cantidad total de nodos */
  25.   int numNodos = 8;
  26.  
  27.   /* Definiendo la matriz de adyacencia */
  28.   int i, j, **A;
  29.  
  30.   if ( ( A = new int*[numNodos] ) == NULL ) return 1;
  31.   for ( i = 0; i < numNodos; i++ )
  32.      if ( ( A[i] = new int[numNodos] ) == NULL ) return 1;
  33.  
  34.   for ( i = 0; i < 8; i++ )
  35.      for ( j = 0; j < 8; j++ )
  36.         A[i][j] = 0;
  37.  
  38.   /* por simplicidad, completamos solo los pares de nodos conectados */
  39.   A[0][1] = 16;
  40.   A[0][2] = 10;
  41.   A[0][3] = 5;
  42.  
  43.   A[1][0] = 16;
  44.   A[1][2] = 2;
  45.   A[1][5] = 4;
  46.   A[1][6] = 6;
  47.  
  48.   A[2][0] = 10;
  49.   A[2][1] = 2;
  50.   A[2][3] = 4;
  51.   A[2][4] = 10;
  52.   A[2][5] = 12;
  53.  
  54.   A[3][0] = 5;
  55.   A[3][2] = 4;
  56.   A[3][4] = 15;
  57.  
  58.   A[4][2] = 10;
  59.   A[4][3] = 15;
  60.   A[4][5] = 3;
  61.   A[4][7] = 5;
  62.  
  63.   A[5][1] = 4;
  64.   A[5][2] = 12;
  65.   A[5][4] = 3;
  66.   A[5][6] = 8;
  67.   A[5][7] = 16;
  68.  
  69.   A[6][1] = 6;
  70.   A[6][5] = 8;
  71.   A[6][7] = 7;
  72.  
  73.   A[7][4] = 5;
  74.   A[7][5] = 16;
  75.   A[7][6] = 7;
  76.  
  77.   /* Imprimir la matriz de adyacencia */
  78.   cout << "Matriz de adyacencia:" << endl << endl;
  79.   for ( i = 0; i < 8; i++ ) {
  80.      for ( j = 0; j < 8; j++ )
  81.         cout << setw(2) << A[i][j] << "  ";
  82.      cout << endl;
  83.   }
  84.   cout << endl;
  85.  
  86.   /* calcular dijkstra a partir del nodo 0, a partir del nofo 7 */
  87.   dijkstra( numNodos, A, 0, 7 );
  88.  
  89.   /* liberar memoria */
  90.   delete [] A;
  91.   for ( i = 0; i < numNodos; i++ )
  92.      delete A[i];
  93.  
  94.   return 0;
  95. }
  96.  
  97. /* Calcula el coste minimo de alcanzar un nodo final 'b'
  98.  * grafo no dirigido con N nodos, a partir del nodo inicial 'a',
  99.  * dada su matriz de adyacencia A */
  100. void dijkstra( int N, int **A, int a, int b ) {
  101.  
  102.   label_t *Labels;
  103.   int i, i0, j, peso;
  104.   int *ruta; /* array de nodos de la ruta minima */
  105.  
  106.   /* Crea din'amicamente el arreglo de etiquetas de nodo */
  107.   if ( ( Labels = new label_t[N] ) == NULL ) return;
  108.  
  109.   /* nodo inicial 'a' entre 0 y N - 1 */
  110.   if ( a < 0 || a > N - 1 ) return;
  111.   /* nodo final 'a' entre 0 y N - 1 */
  112.   if ( b < 0 || b > N - 1 ) return;
  113.  
  114.   /* inicializar las etiquetas de nodo */
  115.   for ( i = 0; i < N; i++ ) {
  116.      Labels[i].nro = i;
  117.      if ( i != a ) {
  118.         Labels[i].prev = -1; /* a'un no se ha definido predecesor */
  119.         Labels[i].peso = -1; /* infinito */
  120.         Labels[i].marca = 0;
  121.      }
  122.      else {
  123.         Labels[i].prev = -1; /* a'un no se ha definido predecesor */
  124.         Labels[i].peso = 0; /* coste del nodo inicial a s'i mismo es cero */
  125.         Labels[i].marca = 0;
  126.      }
  127.   }
  128.  
  129.   /* continuamos este ciclo mientras existan nodos no marcados */
  130.   while ( 1 ) {
  131.      /* busca entre todos los nodos no marcados el de menor peso, descartando los
  132.        * de peso infinito (-1) */
  133.      peso = -1;
  134.      i0 = -1;
  135.      for ( i = 0; i < N; i++ ) {
  136.         if ( Labels[i].marca == 0 && Labels[i].peso >= 0 )
  137.            if ( peso == -1 ) {
  138.               peso = Labels[i].peso;
  139.               i0 = i;
  140.            }
  141.            else if ( Labels[i].peso <= peso ) {
  142.               peso = Labels[i].peso;
  143.               i0 = i;
  144.            }
  145.      }
  146.      if ( i0 == -1 ) { /* termina si no encuentra */
  147.         cout << "Ya no quedan nodos por analizar." << endl;
  148.         break;
  149.      }
  150.  
  151.      cout << "*** Analizando nodo " << i0 << " ***" << endl;
  152.  
  153.      /* actualiza el peso de todos los sucesores (si los hay) del nodo
  154.        * encontrado y luego se~nala dicho nodo como marcado */
  155.      for ( i = 0; i < N; i++ ) {
  156.         if ( A[i0][i] > 0 ) {
  157.            /* si el coste acumulado sumado al coste del enlace del nodo i0 al nodo i
  158.              * es menor al coste del nodo i (o si el coste del nodo i es infinito),
  159.              * debemos actualizar */
  160.            if ( Labels[i].peso == -1 || Labels[i0].peso + A[i0][i] < Labels[i].peso ) {
  161.               if ( Labels[i0].peso + A[i0][i] < Labels[i].peso )
  162.                  cout << "   [ mejorando coste de nodo " << i << " ]" << endl;
  163.               Labels[i].peso = Labels[i0].peso + A[i0][i];
  164.               Labels[i].prev = i0;
  165.               cout << "   coste de nodo " << i << " desde nodo " << i0 << ": " << Labels[i].peso << endl;
  166.            }
  167.         }
  168.      }
  169.      Labels[i0].marca = 1;
  170.      cout << "   [ nodo " << i0 << " marcado ]" << endl;
  171.  
  172.      /* para verificar, imprime los costes calculados hasta el momento */
  173.      for ( i = 0; i < N; i++ ) {
  174.         cout << i << ": [";
  175.         if ( Labels[i].peso == -1 ) cout << "Inf";
  176.         else cout << Labels[i].peso;
  177.         cout << ", " << Labels[i].prev ;
  178.         if ( Labels[i].marca == 1 ) cout <<  ", x]" << endl;
  179.         else cout << "]" << endl;
  180.      }
  181.      cout << endl;
  182.  
  183.      /* pausa (opcional) */
  184.      cout << "presione ENTER para continuar ...";
  185.      cin.get();
  186.   }
  187.  
  188.   /* Ruta desde el nodo 'a' hasta el nodo 'b' */
  189.   int longitud = 2;
  190.   i = b;
  191.   while ( ( i = Labels[i].prev ) != a ) longitud++; /* primero estimamos la longitud de la ruta */
  192.   if ( ( ruta = new int[longitud] ) == NULL ) return;
  193.  
  194.   ruta[longitud - 1] = b; /* luego rellenamos */
  195.   i = b;
  196.   j = 0;
  197.   for ( j = 1; j < longitud; j++ ) {
  198.      i = Labels[i].prev;
  199.      ruta[longitud - j - 1] = i;
  200.   }
  201.  
  202.   cout << "================================================================" << endl;
  203.   cout << endl << "Ruta mas economica entre nodo " << a << " y nodo " << b << ":" << endl << endl;
  204.   for ( i = 0; i < longitud; i++ ) {
  205.      cout << ruta[i];
  206.      if ( i < longitud - 1 ) cout << " - ";
  207.   }
  208.   cout << endl << endl << "Costo total: " << Labels[b].peso << endl << endl;
  209.  
  210.   delete ruta;
  211.   delete [] Labels;
  212. }
2  Programación / Programación C/C++ / Promoción de los parámetros numéricos pasados a función ? en: 27 Marzo 2014, 19:03 pm
Leyendo en internet encontré la cita:

Citar
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?
3  Sistemas Operativos / GNU/Linux / Arrancar con gnome por defecto en lugar de kde en: 23 Marzo 2014, 15:16 pm
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?
4  Programación / Programación C/C++ / Proyecto calculadora: Convertir infijo a posfijo. en: 22 Marzo 2014, 23:56 pm
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:
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:
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
  1. #include <cstdlib>
  2. #include <iostream>
  3. #include <string>
  4. #include <stack>
  5. #include <cmath>
  6.  
  7. using namespace std;
  8.  
  9. /* Operadores matematicos */
  10. #define N_operators 6
  11. const string operators[N_operators] = {"+", "-", "*", "/", "%", "^"};
  12. int precedences[N_operators] = {1, 1, 2, 2, 2, 3};
  13.  
  14. bool is_operator( const string );
  15. int precedence( const string );
  16.  
  17. /* Mis sugerencias personales a este programa:
  18.  *
  19.  * - Considerar el cambio del nombre standby por aux_stack, u otro.
  20.  * - Incorporar el analizador lexico para expresiones numericas de punto
  21.  *   flotante, o que ocupen mas de un caracter.
  22.  * - Eliminar la cadena intermedia postfix, pasando directamente los
  23.  *   resultados de la pila de operadores extraidos de infix, a una pila
  24.  *   de evaluacion.
  25.  * - Incorporar operadores unarios, como sin(), cos(), exp(), log(), etc.
  26.  * - Detectar errores de sintaxis en la expresion infija.
  27.  * - Otros que sean recomendados.
  28.  */
  29.  
  30. int main() {
  31.  
  32. string infix, postfix, token;
  33. stack <string> standby;
  34. stack <double> result;
  35. size_t i;
  36. char c;
  37. double A, B;
  38.  
  39. /* Cadena de entrada */
  40. cout << "Intro expresion infija: ">
  41. getline( cin, infix );
  42. cout << endl;
  43.  
  44. /*************************************************************
  45.  PRIMERA PARTE: Procesar la cadena infijo, y crear posfijo
  46. *************************************************************/
  47. for ( i = 0; i < infix.size(); i++ ) {
  48. /* esto debe cambiar luego a un token o palabra devuelta por
  49. * el analizador léxico */
  50. c = infix[i];
  51. token.clear();
  52. token += c; /* parece burdo, pero no conozco mejor manera de
  53. * crear un string a partir de un unico caracter */
  54.  
  55. /* es un espacio: despreciar */
  56. if ( c == ' ' ) continue;
  57.  
  58. cout << "Analizando token: '" << c << "'" << endl;
  59.  
  60. /* es un carácter numérico: pasar al posfijo */
  61. if ( c >= '0' && c <= '9' ) {
  62. cout << "\tes numero: pasado a posfijo" << endl << endl;
  63. postfix = postfix + " " + c;
  64. continue;
  65. }
  66.  
  67. /* si se lee un operador: sacar de la pila y pasar al postfijo
  68. * todos los operadores con una precedencia mayor o igual a la
  69. * suya, y depositar el mismo en la pila */
  70. if ( is_operator( token ) ) {
  71. cout << "\tes operador:" << endl;
  72. while ( !standby.empty() && precedence( standby.top() )
  73. >= precedence( token ) ) {
  74. cout << "\tpasado operador '" + standby.top() +
  75. "' de la pila a posfijo" << endl;
  76. postfix = postfix + " " + standby.top();
  77. standby.pop();
  78. }
  79. standby.push( token );
  80. cout << "\tcolocar '" << token << "' en la pila" << endl << endl;
  81. continue;
  82. }
  83.  
  84. /* si se lee "(": colocar en la pila */
  85. if ( token == "(" ) {
  86. cout << "pasado a posfijo" << endl << endl;
  87. standby.push( token );
  88. continue;
  89. }
  90.  
  91. /* si se lee ")": retirar de la pila hasta encontrar '(', y pasar
  92. * los elementos retirados a posfijo, luego descartar el "(" */
  93. if ( token == ")" ) {
  94. while ( !standby.empty() && standby.top() != "(" ) {
  95. cout << "\tpasado operador '" + standby.top() +
  96. "' de la pila a posfijo" << endl << endl;
  97. postfix = postfix + " " + standby.top();
  98. standby.pop();
  99. }
  100. if ( !standby.empty() )
  101. standby.pop(); /* descartar el "(" */
  102. }
  103. }
  104.  
  105. /* extraer de la pila cualquier operador restante y pasarlo a la cadena posfijo */
  106. while ( !standby.empty() ) {
  107. cout << "Pasado operador '" + standby.top() +
  108. "' de la pila a posfijo" << endl << endl;
  109. postfix = postfix + " " + standby.top();
  110. standby.pop();
  111. }
  112.  
  113. /* Imprimir el posfijo */
  114. cout << "Posfijo es: \n\t" << postfix << endl << endl;
  115.  
  116. /****************************************************************
  117.  SEGUNDA PARTE: Procesar la cadena posfijo, y devolver resultado
  118. ****************************************************************/
  119.  
  120. A = 0;
  121. cout << "Evaluando la expresion ..." << endl;
  122. for ( i = 0; i < postfix.size(); i++ ) {
  123.  
  124. c = postfix[i];
  125. token.clear();
  126. token += c;
  127.  
  128. /* si se lee un operando (caracter numerico), depositar en la pila */
  129. if ( c >= '0' && c <= '9' ) {
  130. result.push( c - '0' );
  131. continue;
  132. }
  133.  
  134. /* si se lee un operador binario, poner en A y B los últimos dos argumentos
  135. * de la pila y operarlos, guardando el resultado en la pila */
  136. if ( is_operator( token ) ) {
  137. if ( !result.empty() ) {
  138. B = result.top();
  139. result.pop();
  140. }
  141. else {
  142. cout << "Argumentos insuficientes para '" << c << "'" << endl;
  143. return -1;
  144. }
  145.  
  146. if ( !result.empty() ) {
  147. A = result.top();
  148. result.pop();
  149. }
  150. else {
  151. cout << "Argumentos insuficientes para '" << c << "'" << endl;
  152. return -1;
  153. }
  154.  
  155. cout << "\toperar " << A << token << B << " = ";
  156. if ( token == "+" ) {
  157. A += B;
  158. result.push( A );
  159. }
  160. else if ( token == "-" ) {
  161. A -= B;
  162. result.push( A );
  163. }
  164. else if ( token == "*" ) {
  165. A *= B;
  166. result.push( A );
  167. }
  168. else if ( token == "/" ) {
  169. A /= B;
  170. result.push( A );
  171. }
  172. else if ( token == "%" ) {
  173. A = (int )A % (int )B;
  174. result.push( A );
  175. }
  176. else if ( token == "^" ) {
  177. A = pow(A, B);
  178. result.push( A );
  179. }
  180. cout << A << endl;
  181. }
  182. }
  183.  
  184. if ( !result.empty() )
  185. cout << endl << "El resultado es: " << result.top() << endl;
  186.  
  187. return 0;
  188. }
  189.  
  190. /* Verdadero si el token corresponde a un operador. */
  191. bool is_operator( const string token ) {
  192.  
  193. for ( int i = 0; i < N_operators; i++ )
  194. if ( operators[i] == token )
  195. return true;
  196.  
  197. return false;
  198. }
  199.  
  200. /* Devuelve la precedencia del operador descrito por el
  201.  * string token (-1 si no es un operador) */
  202. int precedence( const string token ) {
  203.  
  204. for ( int i = 0; i < N_operators; i++ )
  205. if ( operators[i] == token )
  206. return precedences[i];
  207.  
  208. return -1;
  209. }
5  Programación / Programación C/C++ / ¿Cómo crear procesos hijos en C para Windows? en: 22 Marzo 2014, 22:55 pm
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.
6  Foros Generales / Sugerencias y dudas sobre el Foro / Propuesta para foro, cartelera destacada y/o "salón de la fama". en: 21 Marzo 2014, 15:40 pm
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.
7  Programación / Programación C/C++ / Binomio de Newton, y triángulo de Pascal en: 15 Marzo 2014, 21:21 pm
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  :D. 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
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3. #include <string.h>
  4.  
  5. int ** pascal( const int );
  6. int ** tartaglia( const int );
  7. void destroy_pascal( int **, const int );
  8. void destroy_tartaglia( int **, const int );
  9. int digits( int );
  10.  
  11. int main(int argc, char* argv[]) {
  12.  
  13.   int **A, N;
  14.   int i;
  15.   int width, col;
  16.   char *board[2];
  17.  
  18.   /* Verificando integridad de los datos */
  19.   if ( argc < 2 )
  20.      return -1;
  21.   N = atoi( argv[1] );
  22.  
  23.   if ( N < 0 ) {
  24.      printf("Solo para N >= 0\n");
  25.      return -1;
  26.   }
  27.   if ( N == 0 ) {
  28.      printf("a + b\n");
  29.      return -1;
  30.   }
  31.  
  32.   /* Coeficientes de pascal */
  33.   A = pascal( N );
  34.  
  35.   /* Calculamos el ancho total de la cadena */
  36.   width = 0;
  37.   for ( i = 0; i <= (float)N/2; i++ ) {
  38.      if ( i == 0 ) /* terminos a^N, y b^N */
  39.         width += 2 * ( 1 + digits(N) );
  40.      if ( i == 1 ) /* terminos a^(N-1)*b, y a*b^(N-1) */
  41.         width += 2 * ( 2 + digits(A[N][i]) + digits(N-1) );
  42.      if ( i > 1 ) /* terminos a^(N-i)*b^i */
  43.         if ( !(N % 2) && i == (float)N/2 )
  44.            /* termino central se suma solo una vez */
  45.            width += 2 + digits(A[N][i]) + digits(N-1) + digits(i);
  46.         else
  47.            /* y los restantes, dos veces */
  48.            width += 2 * ( 2 + digits(A[N][i]) + digits(N-1) + digits(i) );
  49.   }
  50.   /* cadenas " + " */
  51.   width += 3 * N;
  52.  
  53.   /* Representacion final */
  54.   if ( ( board[0] = malloc( (width + 1) * sizeof(char) ) ) == NULL )
  55.      return -1;
  56.   if ( ( board[1] = malloc( (width + 1) * sizeof(char) ) ) == NULL )
  57.      return -1;
  58.  
  59.   memset( board[0], ' ', width + 1);
  60.   memset( board[1], ' ', width + 1);
  61.   col = 0;
  62.   for ( i = 0; i <= N; i++) {
  63.      if ( A[N][i] != 1 ) { /* binomial N sobre i */
  64.         col += sprintf( board[1] + col, "%d", A[N][i] );
  65.         board[1][col] = ' ';
  66.      }
  67.      if ( N - i > 0 ) /* base 'a' */
  68.         board[1][col++] = 'a';
  69.      if ( N - i > 1 ) { /* exponente N - i */
  70.         col += sprintf( board[0] + col, "%d", N - i);
  71.         board[0][col] = ' ';
  72.      }
  73.      if ( i > 0 ) /* base 'b' */
  74.         board[1][col++] = 'b';
  75.      if ( i > 1 ) { /* exponente i */
  76.         col += sprintf( board[0] + col, "%d", i);
  77.         board[0][col] = ' ';
  78.      }
  79.      if ( i < N ) {
  80.         col += sprintf( board[1] + col, " + ");
  81.         board[1][col] = ' ';
  82.      }
  83.   }
  84.   board[0][width] = '\0';
  85.   board[1][width] = '\0';
  86.   printf( "(a + b)^%d es:\n\n%s\n%s\n", N, board[0], board[1] );
  87.  
  88.   /* Liberando memoria, y saliendo */
  89.   free( board[0] );
  90.   free( board[1] );
  91.   destroy_pascal( A, N);
  92.   return 0;
  93. }
  94.  
  95. /* Construye una matriz que contiene los numeros del triangulo
  96.  * de Pascal o Tartaglia de orden N > = 0, con N + 1 filas.
  97.  * La matriz es tal que A[i][j] corresponde al binomial (i : j).
  98.  * Se devolverá NULL si N < 0, o si no se pudo asignar memoria
  99.  * para construir la matriz.
  100.  */
  101. int ** pascal( const int N ) {
  102.  
  103.   int **A;
  104.   int i, j;
  105.  
  106.   if ( N < 0 ) return NULL;
  107.  
  108.   if ( ( A = malloc( (N + 1) * sizeof(int *) ) ) == NULL ) return NULL;
  109.   for ( i = 0; i < N + 1; i++ )
  110.      if ( ( A[i] = malloc( (i + 1) * sizeof(int) ) ) == NULL ) return NULL;
  111.  
  112.   for ( i = 0; i < N + 1; i++ ) {
  113.      A[i][0] = 1;
  114.      A[i][i] = 1;
  115.      /* solo se ejecuta si i > 1 */
  116.      for ( j = 1; j < i; j++ )
  117.         A[i][j] = A[i-1][j-1] + A[i-1][j];
  118.   }
  119.  
  120.   return A;
  121. }
  122.  
  123. /* Destruye el objeto creado por la función pascal() */
  124. void destroy_pascal( int ** A, const int N ) {
  125.  
  126.   int i;
  127.  
  128.   if ( N < 0 ) return;
  129.  
  130.   for ( i = N; i >= 0; i-- ) {
  131.      free( A[i] );
  132.      A[i] = NULL;
  133.   }
  134.   free( A );
  135.   A = NULL;
  136. }
  137.  
  138. /* Un sinónimo de pascal( N ) */
  139. int ** tartaglia( const int N ) {
  140.  
  141.   return pascal( N );
  142. }
  143.  
  144. /* Un sinónimo de destroy_pascal( N ) */
  145. void destroy_tartaglia( int ** A, const int N ) {
  146.  
  147.   return destroy_pascal( A, N );
  148. }
  149.  
  150. /* Calcula la cantidad de cifras o digitos que conforman un
  151.  * numero entero no negativo;
  152.  */
  153. int digits( int N ) {
  154.  
  155.   int count = 1;
  156.  
  157.   if ( N < 0 ) return 0;
  158.   if ( N == 0 ) return 1;
  159.  
  160.   while ( ( N = (N / 10) ) > 0 )
  161.      count++;
  162.  
  163.   return count;
  164. }
8  Programación / Programación C/C++ / Utilería, reemplazar TAB por " " en: 11 Marzo 2014, 04:15 am
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
  1. #include <stdlib.h>
  2. #include <stdio.h>
  3.  
  4. /* Este programa reemplaza los caracteres TAB del fichero de texto
  5.  * pasado como primer argumento por una cantidad determinada de espacios,
  6.  * y escribe su salida en el fichero pasado como segundo argumento.
  7.  * El tercer argumento (opcional) especifica cuántos caracteres ' '
  8.  * reemplazarán el TAB, y si no se indica, se tomará una cantidad de tres.
  9.  */
  10.  
  11. int main( int argc, char *argv[]) {
  12.  
  13.   int i, N_spaces;
  14.   char c;
  15.   char * in_fname, * out_fname;
  16.   FILE * in_fptr = NULL, * out_fptr = NULL;
  17.  
  18.   if ( argc < 2 ) {
  19.      printf("Use:\n tab in_file out_file\n tab in_file out_file N_spaces\n");
  20.      goto failure;
  21.   }
  22.  
  23.   in_fname = argv[1];
  24.  
  25.   if ( argc > 3 ) {
  26.      N_spaces = atoi( argv[3] );
  27.      if ( N_spaces < 1 )
  28.         N_spaces = 3;
  29.      }
  30.   else
  31.      N_spaces = 3;
  32.  
  33.   if ( ( in_fptr = fopen( in_fname, "r" ) ) == NULL ) {
  34.      printf( "No existe o no se pudo abrir '%s'\n", in_fname );
  35.      goto failure;
  36.   }
  37.  
  38.   /* toma stdout si falta fichero de salida */
  39.   if ( argc < 3 )
  40.      out_fptr = stdout;
  41.   else   {
  42.      out_fname = argv[2];
  43.      if ( ( out_fptr = fopen( out_fname, "w" ) ) == NULL ) {
  44.         printf( "Imposible crear, abrir o escribir en '%s'\n", out_fname );
  45.         goto failure;
  46.      }
  47.   }
  48.  
  49.   /* reemplazando TAB por N_spaces caracteres ' ' */
  50.   while ( ( c = fgetc( in_fptr ) ) != EOF ) {
  51.      if ( c != '\t' )
  52.         fputc( c, out_fptr );
  53.      else
  54.         for ( i = 0; i < N_spaces; i++ )
  55.            fputc( ' ', out_fptr );
  56.   }
  57.  
  58.   if ( in_fptr != NULL ) fclose( in_fptr);
  59.   if ( out_fptr != NULL ) fclose( out_fptr);
  60.   return 0;
  61.  
  62. failure:
  63.   if ( in_fptr != NULL ) fclose( in_fptr);
  64.   if ( out_fptr != NULL ) fclose( out_fptr);
  65.   return -1;
  66. }

NOTA. Una alternativa es la utilería "sed" (UNIX), pero no se si tiene alternativa Windows.
9  Programación / Programación C/C++ / No funciona timer en Linux en: 9 Marzo 2014, 17:34 pm
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
  1. #include <stdio.h>
  2. #include <time.h>
  3.  
  4. int main( ) {
  5.  
  6. clock_t t1, t2;
  7.  
  8. t1 = clock();
  9. getchar();
  10. t2 = clock();
  11. printf("Han transcurrido %.2lf s\n", (double)(t2 - t1)/CLOCKS_PER_SEC );
  12.  
  13. }
10  Programación / Programación C/C++ / Para entender el algoritmo de inserción en: 4 Marzo 2014, 19:02 pm
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
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. #define N 5
  5.  
  6. int main(void) {
  7.  
  8. int x[N] = {7, 3, 11, 5, 1};
  9. int i, j, k;
  10. int aux;
  11.  
  12. printf("Arreglo original: \n");
  13. for (k = 0; k < N; k++)
  14. printf(" %d", x[k]);
  15. printf("\n");
  16.  
  17. for (i = 1; i < N; i++) {
  18.  
  19. /* buscamos desde 0 hasta i - 1, el primer elemento que sea
  20. * mayor que x[i] */
  21. printf("ubicando %d ...", x[i]);
  22. j = 0;
  23. while (j < i && x[j] <= x[i])
  24. j++;
  25.  
  26. if ( j < i ) {
  27.  
  28. /* insertar x[i] en la posición j, y desplazar los
  29. * restantes elementos hacia la derecha */
  30. printf(" poner en posicion %d\n", j);
  31.  
  32. for (k = 0; k < N; k++)
  33. printf(" %d", x[k]);
  34. printf("  -> ");
  35.  
  36. aux = x[i];
  37. for (k = i; k > j; k--)
  38. x[k] = x[k-1];
  39. x[j] = aux;
  40.  
  41. for (k = 0; k < N; k++)
  42. printf(" %d", x[k]);
  43. printf("\n");
  44. }
  45. else
  46. printf(" sin cambios\n");
  47. }
  48. printf("El arreglo final ordenado es:\n");
  49. for (i = 0; i < N; i++)
  50. printf(" %d", x[i]);
  51. printf("\n");
  52.  
  53. return 0;
  54. }
Páginas: [1] 2
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines