Según se deduce del postulado, una expresión LISP consta de un signo de operación seguido de un número indeterminado de valores y/o expresiones, todo rodeado entre paréntesis, como (+ 1 2 3), (* (+ 1 2) (+ 2 3)).
Lo primero es crear un generador que recibe la expresión original y nos devuelva las partes que la componen. Para simplificar el caso, la expresion debe separar cada componente con espacios.
Este generador puede retornar una cadena o un valor numérico, según sea el caso.
def next_token(expresion):
"""
Generador de partes de una expresión LISP
:param expresion: La expresión LISP, con espacios rodeando cada parte.
:return: El siguiente token como valor numérico (si corresponde), o
como string, como "(", ")", "+", ...
"""
for parte in expresion.split():
try:
parte = float(parte)
except ValueError:
pass
yield parte
Con eso podemos construir una función evaluar
recursiva, que reciba este generador y retorne el valor numérico resultante.
Al encontrar la operación en la expresión, la copiamos a operacion
. A continuación leemos el siguiente elemento de la expresión. Si es un valor numérico, lo usamos para inicializar resultado
. Luego continuamos leyendo elementos y aplicando la operación sobre el resultado previo. Si en cualquier etapa nos encontramos con una expresión en lugar de un valor, evaluamos la expresión recursivamente.
def evaluar(generador):
""" Evalua numéricamente una expresión LISP.
:param generador: Un generador
:return: Valor numérico.
"""
resultado = None # El resultado calculado
operacion = None # La operación a realizar.
token = next(generador)
# Descartar el "(" inicial.
if token == '(':
token = next(generador)
# Procesar hasta llegar al final de la expresión.
while token != ')':
if token == '(':
# Convertir expresión LISP es un valor numérico
# Caso (+ 3 (- 1 2)) donde hay dos operandos:
# el valor 3 y la expresión (- 1 2)
token = evaluar(generador)
if type(token) == float:
# Es un valor númerico; aplicar la operación.
if resultado is None:
# Primer valor numérico después de un operador.
resultado = token
elif operacion == '+':
resultado += token
elif operacion == '-':
resultado -= token
elif operacion == '*':
resultado *= token
elif operacion == '/':
resultado /= token
elif token in "+-*/":
operacion = token
token = next(generador)
return resultado
Demo
tests = [
"( + ( + 1 2 ) 3 )",
"( + 1 ( + 3 5 ) )",
"( + 1 4 )",
"( + 1 2 3 4 5 )",
" ( + ( * ( / 8 7 ) 15 ) -2 )",
"( * 1 2 3 4 5 6 7 8 9 10 )"]
for test in tests:
print(test, end=" => ")
generador = next_token(test)
res = evaluar(generador)
print(res)
produce:
( + ( + 1 2 ) 3 ) => 6.0
( + 1 ( + 3 5 ) ) => 9.0
( + 1 4 ) => 5.0
( + 1 2 3 4 5 ) => 15.0
( + ( * ( / 8 7 ) 15 ) -2 ) => 15.142857142857142
( * 1 2 3 4 5 6 7 8 9 10 ) => 3628800.0