Calculadora de notación polaca inversa en C
La Notación Polaca Inversa (RPN en inglés, Reverse Polish Notation) es un método de introducción de datos alternativo al algebráico. Fue creada en 1920 por el matemático polaco Jan Lukasiewicz como una forma de escribir expresiones matemáticas sin tener que utilizar paréntesis y corchetes.
En la notación polaca inversa los operadores suceden a sus operandos. Por ejemplo, la expresión algebráica5+((1+2)*4)-3se traduce a la notación polaca inversa como5 1 2 + 4 * + 3 -.
Su principio es el de evaluar los datos directamente cuando se introducen y manejarlos dentro de una estructura LIFO (Last In First Out), lo que optimiza los procesos a la hora de programar.
El siguiente programa es una implementación en C de una calculadora que funciona con notación polaca inversa. El programa es una versión modificada del que figura en el libro “El lenguaje de programación C” de Kernighan y Ritchie.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 | ## ************ ## @file calc.c ## ************ #include <stdio .h> #include <stdlib .h> #define MAXVAL 100 #define NUMBER '0' /** * Variables */ int verbose; int sp = 0; double val[MAXVAL]; /** * Prototypes */ int toi (char const *s); void push (double); double pop (void); /** * Main */ int main (int argc, char const *argv[]) { int offset, i; double op2; if (argc < 2) { fprintf (stderr, "Usage: %s [-v] EXP\n", argv[0]); return 1; } verbose = offset = (strcmp (argv[1], "-v") == 0) ? 1 : 0; for (i = 1 + offset; i < argc; i++) { switch (toi (argv[i])) { case '+' : if (verbose) printf ("operator +\n"); push (pop() + pop()); break; case '-' : if (verbose) printf ("operator -\n"); op2 = pop(); push (pop() - op2); break; case '*' : if (verbose) printf ("operator *\n"); push (pop() * pop()); break; case '/' : if (verbose) printf ("operator /\n"); op2 = pop(); if (op2 != 0.0) push (pop() / op2); else fprintf (stderr, "Error: division by zero\n"); break; case NUMBER : push (atof (argv[i])); break; default : fprintf (stderr, "Error: unknown operator %s\n", argv[i]); break; } } // Result printf ("%f\n", val[0]); return 0; } /** * Toi */ int toi (char const *s) { return (isdigit(s[0])) ? NUMBER : (int) s[0]; } /** * Push */ void push (double e) { if (sp < MAXVAL) { if (verbose) printf ("push %f in %d\n", e, sp); val[sp++] = e; } else fprintf (stderr, "Error: full stack\n"); } /** * Pop */ double pop (void) { if (sp > 0) { --sp; if (verbose) printf ("pop %f from %d\n", val[sp], sp); return val[sp]; } else { fprintf (stderr, "Error: empty stack\n"); return 0.0; } } </stdlib></stdio> |
Para compilarlo ejecutamos
A diferencia del programa original publicado en el libro de C, aquí se utiliza el arrayargv[]como fuente de operandos y operadores. Esto permite que podamos llamar al programa desde línea de comandos de la siguiente manera:
Notar que para el caso especial del operador multiplicación, debemos escaparlo para evitar la expansión propia de bash antes de la llamada efectiva al programa.
El programa admite la opción-v(verbose), que muestra información acerca de uno de los pasos realizados.
Ejemplo I
push 5.000000 in 0
push 1.000000 in 1
push 2.000000 in 2
operator +
pop 2.000000 from 2
pop 1.000000 from 1
push 3.000000 in 1
push 4.000000 in 2
operator *
pop 4.000000 from 2
pop 3.000000 from 1
push 12.000000 in 1
operator +
pop 12.000000 from 1
pop 5.000000 from 0
push 17.000000 in 0
push 3.000000 in 1
operator -
pop 3.000000 from 1
pop 17.000000 from 0
push 14.000000 in 0
14.000000
