Las computadoras están diseñadas de fábrica para poder realizar las operaciones que se necesitan para hacer una calculadora simple, de ahí que puede ser buena idea que uno de los primero programas para alguien que quiere empezar sea una calculadora, ya que no es necesario implementar tantas otras cosas como en otros proyectos. Desde luego, pueden usarse librerías para no tener que implementar todo en tales casos, pero al principio puede dejarse para después el tema de las librerías.
Y cuando se me ocurrió este posteo lo primero que hice fue buscar en google para ver si no era algo demasiado hecho. Lo que me llamó la atención es que si bien hay varias páginas que muestran cómo hacer una calculadora, las que se trae como primero resultados muestran que nada cómo hacer una interfáz para que un usuario escriba dos números y una operación para después pedirle a la computadora el resultado y mostrarlo en la pantalla.
En el otro extremo hay una página que muestra lo siguiente código (en python):
print(eval(input()))
Ese ejemplo incluye una calculadora, pero también mucho más, porque la función eval lo que hace es justamente pasarle al intérprete de python lo que sea para que lo evalúe. Y si es una expresión artmética lo va a calcular, pero puede eveluar cualquier expresión de python. Eso puede implicar riesgos para la seguridad del sistema, asi que no es aconsejable tampoco… (imagínense pasarle a eval cosas como exec('import os; print(os.listdir(os.getenv("HOME")))') o peor, que borren archivos, etc.
La idea entonces es hacer algo que no es ni una cosa ni la otra, tratando en el camino de entender qué vamos haciendo, hasta cierto punto al menos. Un programa que recibe una expresión aritmética como «7 + 8 * 6» y devuelva como resultado el número que esa expresión denota. O sea, a diferencia del primer ejemplo podemos hacer más de una operación «por cuenta» y a diferencia del segundo sólo vamos a resolver operaciones ariméicas y no cualquier expresión de python.
La interfáz es bien simple: nuestro usuario va a llamar una función que vamos a llamar calcu y a pasarle una string donde esté la expresión, algo como calcu("21 * 24 / (4 + 3)"). Y si la expresión está mal formada directaente vamos a fallar de forma poco amigable (en otro posteo podemos hacer algo mejor en ese aspecto pero en este no vamos a mantener simples).
Las operaciones binarias a soportar son +, -, *, /, ^ y también vamos a poder usar numero negativos que empiecen con - unario (más adelanta más sobre esto). Las prioridade de agrupación son las habituales, o sea + tiene menos prioridad que *, etc., y usamos los préntesis si queremos un orden distinto al de la convención como (3+4)*5. Vamos a evaluar una sola expresión y no vamos a usar variables, cosa que también podríamos ver, quizá, después.
Pero qué es lo que vamos a considerar una expresión válida? Cómo definimos cuáles son las expresiones que están bien y las que no? Bueno quizá si uno de la nada quiere especificar esto puede ser bastante complicado dar con una respuesta (el lector podría intentar dar con alguna forma por su cuenta), pero por suerte es un problema ya resuelto y la solución se llama notación de Backus-Naur.
Puede leerse el artículo de wikipedia para entender mejor pero lo que necesitamos saber por ahora es que cuando usamos un := lo que está a la izquierda puede reemplararse por lo de la derecha y cualquier expresión que pued obtenerse así es válida, siempre que empiece del «símbolo distinguido». Vamos mejor a un ejemplo ya que la idea es simple aunque dificil de resumir en una línea. El ejemplo es justament nuestra gramática de expresiones aritméticas.
E := E + T
| E - T
| T
T := T * F
| T / F
| F
F := (E)
| Num
| -Num
Esta gramática es parecida (pero distinta) a la que está en esta página a la que el lector puede ir a ver por si le sirve para entender cómo se usa. Pero trato de explicar brevemente (ya que en realidad no es el tema de este posteo).
La idea es que una expresión pertenece a nuestra gramática siempre y cuando haya una forma de «generarla» partiendo del símbolo E y llegando a algo done de no haya más que +, -, *, /, (, ) y Num donde Num en realidad significa una número (si el lector sabe de regex, sería algo que matchee ([0-9]*[.])?[0-9]+ por ejemplo).
Cómo se genera una expresión en base a otra? Bueno, siempre podemos reemplaza cualquiera de los símbolos a la izquierda de := (el | es una manera abreviada de decir lo mismo) por lo que aparece a la derecha, ejemplo: E => E - T o (E) => (F). Nótese en el segundo ejemplo que (E) aparece a la derecha también, pero lo que nos importa es que como E := F entonces aplicamos esto a (E) y nos queda (F).
Es decir, usamos los símbolos E, T, F por un lado y los comunes +. -. *, ... etc. Num en realidad se refiere a cualquier número. Los E, T, F se llaman «no terminales» porque en sí mismos nunca están en una expresión, hay que derivarlos, del siguiente modo: para generar una expresión partimos del síbolo E (es nuestro símbolo distinguido) y aplicamos las reglas todas las veces que sea necesario hasta llegar a algo que no tenga más «no terminales». De E tenemos 3 opciones E + T, E - T y T. Y después tenemos que seguir, por ejemplo:
E -> E * T -> T * T -> F * T -> (E) * T -> (E + T) * T -> (T + T) * T ->...-> (Num + Num)
* Num
La definición de esta gramática es importante para el usuario porque una misma expresión puede estar bien o mal según qué gramática sea. No siempre los usuarios están al tanto de estas diferencias. Por ejemplo, si buscamos «calculadora» en google el mismo google nos da una calculadora en la cual no podemos escribir por ejemplo - -2. En python, por el contrario, - -2 es una expresión válida, a saber -(-2) que equivale a 2. Incluso podemos escribir --2 y es igual. Pero esto no ocurre así en todos los lenguajes. Por ejemplo, el shell de java interpreta esto como un error:
jshell> --2
| Error:
| unexpected type
| required: variable
| found: value
| --2
| ^
#
Algo similar ocurre con la calculadora bc:
bc 1.07.1
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006, 2008, 2012-2017 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'.
--2
(standard_in) 1: syntax error
En haskell es más particular, pues se ignora la expresión dado que -- es la forma de inicial un comentario…
En nuestro caso vamos a adotar la decisión de no admitir más de un - consecutivo para ivnertir el signo de un número (tal como especifica nuestra gramática): después de todo no hace falta. O sea hacemos como la calculadora del buscador. Y si el usuario quiere igual puede hacer -(-2).
Estas diferencias provienen de la ambigüedad de usar un mismo símbolo - para dos cosas: sumar, cambiar el signo. Y demás de que en realidad el usuario no escribe directamente en nuestra gramática. Él escribe caracteres, eso es lo que leemos, y tenemos que hacer una pimera traducción de los caracteres a nuestr a gramática. Es decir, nosotros leemos el símbolo - que por sí mismo no nos dice cuál de los dos significados tiene. Por suerte es facir saberlo por el contexto, an particular, por lo que hay antes. Observando nuestra gramática vemos que es una resta binaria sólo si viene inmediatamente después de una E y es el cambio unario de signo si empieza un F. Tenemos que mirar un poco más hasta ver qué símbolos terminales pueden estar en ambos contextos, y es fácil llegar a que la última parte de una E puede ser un Num o un ) y entonces si vemos un - después de alguno de estos dos sabemos que es un asuma. Y F tenemos después de *, / o (, con lo cual la ambugüedad se resuelve leyendo sólo lo último que se haya leído antes.
Vamos entonces a hacer dos pasadas: en la primera leemos los caracters de a uno y devolvemos una expresión válida en nuestra gramática donde cada elemento es un «símbolo terminal» de la misma, es decir, alguno de los operadores, paréntesis o un número. Después vamos a leer esta cadena resultante y hacer la cuenta.
Un último comentario. Dije ya que si la entrada no corresponde a la gramática no nos interesa dar un resultado útil. Por ejemplo «1 1» no tiene sentido así que no nos ocupamos de dar alguna respuesta en tales casos. Pero puede ocurrir que la entrada sea correcta desde el punto de vista sintáctico y así y todo no tenga sentido. Es el caso de entradas como «1 / 0». En ese caso se obtiene correctamente E -> T -> T / F -> F / F -> 1 / F -> 1 / 0. Pero matemáticamente no tiene sentido. Hacer una gramática que no acepte ese conjunto de entradas y sí el resto no valdría la pena. Lo que vamos a hacer es pasarle a python la cuenta y python nos va a tirar una excepción que vamos a dejar pasar.
Ahora sí, entonces, podemos pasar al algoritmo. En primer lugar, el traductor de caracteres a tokens. La idea es simplemente leer salteando los espacios. Si es una operación, entonces agregarla como token, si es el primer caracter de un número, leer todo el número y agregarlo. El único detalle a tener en cuenta es la ambigúedad de - que se maneja como se dice arriba. El resultado es una lista de string, cada elemento de la lista es un token (o un lexema) de nuestra gramática:
def read_number(s, i):
return next((k for k,e in enumerate(s[i+1:]) if e in " +-*/^()"), len(s[i:]) - 1) + i + 1
def read_expression(s):
tokens = []
last = "^"
i = 0
while i < len(s):
if s[i] == " ":
i = i + 1
pass
elif s[i] in "+*/^()" or (s[i] == "-" and last in "0123456789)"):
tokens.append(s[i])
last = s[i]
i = i + 1
else:
ix = read_number(s,i)
tokens.append(s[i:ix])
last = s[ix-1]
i = ix
return tokens
La segunda parte es un poco más complicada. Usamos dos pilas, una con las operaciones y otra con los «valores». Estos valores son o bien los número que vamos leyendo o aplicaciones parciales de la cuenta que queremos hacer. El tema es que para aplicar una operación necesitamos comparar la prioridad del operador con los que estén a ambos lados, y por eso los guardamos para hacer hasta que podemos comparar. Ahi entonces «reducimos» lo cual significa hacer la operación y su resultado se va guardandod en la pila de los valores:
priority = {
'+': 1,
'-': 1,
'*': 2,
'/': 2,
'^': 3,
'(': 0
}
opsfun = {
"+" : lambda x, y: x + y,
"-" : lambda x, y: x - y,
"*" : lambda x, y: x * y,
"/" : lambda x, y: x / y,
"^" : lambda x, y: x ** y
}
def reduceWhile(ops, vals, condition):
while ops and condition(ops[-1]):
vals[-1] = opsfun[ops.pop()](vals[-2], vals.pop())
def calcu(tokens):
ops, vals = [], []
expr = read_expression(tokens.strip())
for c in expr:
if (c == '('):
ops.append(c)
elif (c == ')'):
reduceWhile(ops, vals, lambda last: last != '(')
ops.pop()
elif c not in ["+", "-", "*", "/", "^"]:
vals.append(float(c))
else:
reduceWhile(ops, vals, lambda last: priority[c] <= priority[last])
ops.append(c)
reduceWhile(ops, vals, lambda x: True)
return vals[-1]
Y nuevamente, el posteo me quedó más largo de lo que imaginé en un principio y se extendería por ende demasiado si sigo. Por eso lo dejo acá y eventualmente lo continuaremos en comentario u otros posts (probablemente quiera hacer alguno con un enfoque completamente distinto, menos «machine-oriented» y más teórico usando las teorías sobre parsing.
El código de este post puede verse mejor en este gist.
Funciones que funcionan 