Una calculadora aritmética simple en SuperBASIC

¿Cuánto tiempo tardaríamos en resolver una expresión aritmética como la siguiente?

(((3+7)*5)*7)*((((((2+6-1)*5)+(((3+5)*9)+4))*7)-(4+3-6-7+9+8))*6)

Seguro que con ayuda de lápiz y papel lo resolveríamos sin problemas pero tardaríamos un buen “ratito”. Sin ayuda alguna (de papel y lápiz) seguramente tardáramos un rato más y con un esfuerzo mental más exigente. Desde luego, él cálculo de la solución no es algo que la mente humana pueda realizar de forma automática

Las estrategias para resolver este tipo de problemas es algo que ya está muy estudiado por los diseñadores de lenguajes de programación y por los ingenieros que los implementan en compiladores reales. Se emplean para ello algoritmos muy ingeniosos y poderosos, desarrollados por los científicos e ingenieros de esta materia a lo largo de los años.

Aprovechando este tema, vamos “a jugar” un poco con SuperBASIC. El “juego” consistiría en implementar una solución que resolviera este tipo de expresiones de forma inmediata y sin errores. Nuestro programa pedirá al usuario que teclee una expresión aritmética y deberá darnos el resultado sin importar cuán compleja sea dicha expresión. Para ello elegiremos un algoritmo llamado “análisis sintáctico descendente recursivo”. Es uno de los algoritmos más simples para resolver este tipo de problemas y fue uno de los primeros que se descubrieron para implementar compiladores de lenguajes de alto nivel. (El algoritmo lo he extraído del libro “Construcción de Compiladores” de K.C. Louden).

Este sería el resultado final.

Calculadora simple en SuperBASIC

 

Esta calculadora es muy simplista, en realidad sólo es capaz de sumar, restar y multiplicar números de un sólo dígito. La ventaja es que el programa se mantiene corto y más comprensible.

El punto de partida es elegir una gramática que define una serie de derivaciones de forma recursiva, esto es muy útil ya que éstas son las que luego guían la implementación en el código.

La gramática para nuestra calculadora es la siguiente:

expresion -> expresion operadorSuma termino | termino
operadorSuma -> + | -
termino -> termino operadorMult factor | factor
operadorMul -> *
factor -> ( expresion ) | numero
numero -> 0|1|2|3|4|5|6|7|8|9

El código en SuperBASIC de nuestro “juego” está aquí:

100 REMark ===============================
110 REMark = Calculadora artimƒtica simple
120 REMark ===============================
130 :
140 MODE 8:CLS
145 Instructions
150 :
160 REPeat loopMain
170   expIn$ = ""
180   token$ = ""
190   result = 0
200   idx% = 1
210   :
220   PRINT "Introduce una expresi–n: "
230   INPUT ">> "; expIn$
240   IF expIn$ = "" THEN
250     EXIT loopMain
260   END IF
270   expIn$ = expIn$ & " "
280   token$ = getchar$
290   :
300   result = exp%
310   :
320   PRINT
330   PRINT "El resultado es "; result
340   PRINT:PRINT
350 END REPeat loopMain
360 :
370 STOP
380 :
390 REMark --- Fun, Proc -----------------
400 :
410 DEFine FuNction getchar$
420   LOCal c$
430   c$ = expIn$(idx%)
440   idx% = idx% + 1
450   RETurn c$
460 END DEFine
470 :
480 DEFine PROCedure match (expectedToken$)
490   IF token$ = expectedToken$ THEN
500     token$ = getchar$(v$)
510   ELSE
520     errorExp
530   END IF
540 END DEFine
550 :
560 DEFine PROCedure errorExp
570   PRINT#0, "error en expresi–n"
580   STOP
590 END DEFine
600 :
610 DEFine FuNction exp%
620   LOCal temp%, k
630   temp% = term%
640   REPeat loopExp
650     IF token$ <> "+" AND token$ <> "-" THEN
660       EXIT loopExp
670     END IF
680     k = CODE(token$)
690     SELect ON k
700       = 43:
710         match "+"
720         temp% = temp% + term%
730       = 45:
740         match "-"
750         temp% = temp% - term%
760     END SELect
770   END REPeat loopExp
780   RETurn temp%
790 END DEFine
800 :
810 DEFine FuNction term%
820   LOCal temp%, k%
830   temp% = factor%
840   REPeat loopTerm
850     IF token$ <> "*" THEN
860       EXIT loopTerm
870     END IF
880     match "*"
890     temp% = temp% * factor%
900   END REPeat loopTerm
910   RETurn temp%
920 END DEFine
930 :
940 DEFine FuNction factor%
950   LOCal temp%
960   IF token$ = "(" THEN
970     match "("
980     temp% = exp%
990     match ")"
1000   ELSE IF IsDigit%(token$) = 1 THEN
1010     temp% = ValDigit% (token$)
1020     token$ = getchar$
1030   ELSE
1040     errorExp
1050   END IF
1055   END IF
1060   RETurn temp%
1070 END DEFine
1080 :
1090 DEFine FuNction IsDigit% (val$)
1100   LOCal t%, res%
1110   t% = CODE(val$)
1120   IF t% < 48 OR t% > 57 THEN
1130     res% = 0
1140   ELSE
1150     res% = 1
1160   END IF
1170   RETurn res%
1180 END DEFine
1190 :
1200 DEFine FuNction ValDigit% (val$)
1210   LOCal v%
1220   v% = CODE(val$)
1230   v% = v% - 48
1240   RETurn v%
1250 END DEFine
1260 :
1270 DEFine PROCedure Instructions
1275   INK 4
1280   PRINT "Calculadora aritmƒtica simple."
1290   PRINT "------------------------------"
1300   PRINT "Calculadora minimalista que realiza"
1310   PRINT "operaciones de suma, resta y "
1312   PRINT "multiplicaci–n con n™meros de un s–lo"
1320   PRINT "d“gito."
1330   PRINT
1340   PRINT
1345   INK 7
1350 END DEFine


Bibliografía:
Contrucción de Compiladores
Kenneth C. Louden
Ed. Thomson

Edito: Corregido Bug y adaptado código a SBASIC.

Anuncios

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s