Abro este hilo por dos motivos. Primero, el de enseñar algo nuevo a quien desconozca de esto y lo segundo, para que alguien que sepa más que yo me corrija y guíe por un mejor camino.
Cosas necesarias para seguir el hilo:
Lo que voy a desarrollar aquí es como implementar un evaluador de formulas sencillo, simple y para toda la familia. Resumiendo, lo que hará nuestro programa es segun una entrada del tipo "4+2*2" nos devuelva el resultado de esa operación.
** Y no... no es con eval("4+2*2")
jejeje
Maquina de Estado Finito
Definición Wiki: Un autómata finito (AF) o máquina de estado finito es un modelo computacional que realiza cómputos en forma automática sobre una entrada para producir una salida.
Cabe decir, que aquí me voy a quedar muy muy corto.... existen varios subtipos de máquina de estado finito y toda una teoría que lo sustenta. Yo me quedaré con comentaros las dos grandes familias:
** Un apunte, una maquina de este tipo tiene más de una maquina determinista. Se puede ver cada posible camino como una maquina determinista.
Nuestra implementación se basa en una maquina de estados finita determinista. Finita porque se conocen todos sus posibles estados y determinista porque se puede conocer el camino de antemano.
Manos a la obra brother!
Lo primero que necesitamos es un método que nos "corte" la cadena de entrada en pedazos que podamos manejar con más facilidad (tokens). A esta función se le suele llamar "tokenizer":
Para ayudarnos, lo primero que haremos será definir un mapa de las "palabras clave" por las que cortar
La función 'tokenizer' quedaría:
def tokenizer(self, data):
tokens = []
buff = ""
def appendToken(value):
tokens.append(self.lexer(value, tokens[-1] if tokens else None))
for lett in data:
if lett in SYMBOLS['GROUP'] or lett in SYMBOLS['OPER'] or lett in SYMBOLS['IGNORED']:
if buff:
appendToken(buff)
buff = ""
if lett not in SYMBOLS['IGNORED']:
appendToken(lett)
else:
buff += lett
if buff:
appendToken(buff)
return tokens
Básicamente lo que conseguimos con este método es:
- Entrada: "4+2*2"
- Salida: ["4","+","2","*","2"]
Ah... pero claro, el método 'tokenizer' está usando a su vez 'SYMBOLS' y 'lexer'. Veamos porque...
El diccionario 'SYMBOLS' contiene todos los "simbolos" que entiende nuestra máquina, los números no se incluyen porque se entiende que el resto de simbolos, son números.
Mostrar spoiler
Ocultar spoiler
SYMBOLS = {
'GROUP': '()',
'IGNORED': ', ',
'SIGN': '+-',
'OPER': '+-*/',
}
El método 'lexer' se encarga de "catalogar" el token... en nuestro caso dirá si es un número, un operador o una agrupación.
Mostrar spoiler
Ocultar spoiler
def lexer(self, token, prev_token):
lexer_type = 'NAME'
san_token = token.strip()
if self._isNumber(token):
lexer_type = 'NUMBER'
san_token = self._toNumber(san_token)
elif self._isSign(token, prev_token):
lexer_type = 'SIGN_POSITIVE' if token == SYMBOLS['SIGN'][0] else 'SIGN_NEGATIVE'
elif self._isMathOper(token):
if token == SYMBOLS['OPER'][0]:
lexer_type = 'OPER_ADD'
elif token == SYMBOLS['OPER'][1]:
lexer_type = 'OPER_SUBSTRACT'
elif token == SYMBOLS['OPER'][2]:
lexer_type = 'OPER_MULTIPLY'
elif token == SYMBOLS['OPER'][3]:
lexer_type = 'OPER_DIVIDE'
elif self._isGroup(token):
lexer_type = 'LGROUP' if token == SYMBOLS['GROUP'][0] else 'RGROUP'
return [LEXER_TYPES[lexer_type], san_token]
Gracias a esto la salida real del método sería algo como:
- Entrada: "4+2*2"
- Salida:
[
[LEXER_TYPES['NUMBER'], 4], [LEXER_TYPES['MATH_OPER'], '+'], [LEXER_TYPES['NUMBER'], 2], [LEXER_TYPES['MATH_OPER'], '*'], [LEXER_TYPES['NUMBER'], 2]]
Después del proceso de "tokenizar", necesitamos traducir estos tokens en instrucciones para nuestra máquina. Nuestra máquina lo que podrá hacer es:
- LOAD_CONST: Lee una constante y la almacena en el stack
- ADD: Obtiene dos valores del stack y los suma, dejando el valor resultante en el stack
- SUBSTRACT: Obtiene dos valores del stack y los resta, dejando el valor resultante en el stack
- MULTIPLY: Obtiene dos valores del stack y los multiplica, dejando el valor resultante en el stack
- DIVIDE: Obtiene dos valores del stack y los divide, dejando el valor resultante en el stack
- UNITARY_POSITIVE: Básicamente, no se usa nunca.
- UNITARY_NEGATIVE: Hace la operación "*-1"
Este proceso, es el proceso de "compilado"… yo lo he querido llamar "parser" porque realmente no genera un objeto… sino una lista de instrucciones (una especie de byte-code).
Para este proceso usaremos un algoritmo bien conocido llamado "Shunting yard algorithm". Este algoritmo es bien sencillo cuando tienes bien "tokenizada" la entrada. La idea es la de ir moviendo los operandos y operadores en un orden concreto:
def parse(self, tokens):
# Based on 'Shunting yard algorithm'
operator_stack = []
sign_token = None
intructions = []
values = []
def add_instruction(token):
op_code = LEXER_OP_CODES[token[0]]
intructions.append(op_code)
if op_code == OP_CODES['LOAD_CONST'] or op_code == OP_CODES['LOAD_NAME']:
values.append(token[1])
prev_lett = None
for token in tokens:
token_type, token_value = token
if token_type == LEXER_TYPES['NUMBER']:
add_instruction(token)
if sign_token:
add_instruction(sign_token)
sign_token = None
elif token_type == LEXER_TYPES['NAME']:
operator_stack.insert(0, token)
elif token_type in LEXER_SIGN:
sign_token = token
elif token_type == LEXER_TYPES['RGROUP']:
while operator_stack and operator_stack[0][0] != LEXER_TYPES['LGROUP']:
add_instruction(operator_stack.pop(0))
operator_stack.pop(0)
elif token_type in LEXER_OPER:
while operator_stack and operator_stack[0][0] in OPER_PRECEDENCES and OPER_PRECEDENCES[token_type] <= OPER_PRECEDENCES[operator_stack[0][0]]:
add_instruction(operator_stack.pop(0))
operator_stack.insert(0, token)
else:
operator_stack.insert(0, token)
prev_token = token
while len(operator_stack):
token = operator_stack.pop(0)
if token[0] in LEXER_GROUP:
raise Exception("Los parentesis no coinciden")
add_instruction(token)
return {
'instructions': intructions,
'values': values,
}
Al final, lo que nos da este método es un diccionario con la lista de instrucciones para nuestra máquina y una lista de las constantes. Aquí debes tener en cuenta que el alcance de un operador matemático es siempre de dos (ej: 6*8 -> la operación multiplicar alcanza a dos números).
Con esto debes de fijarte que, por ejemplo, si la máquina recibe la instrucción "SUMA" pero no se han cargado los valores… fallará al no poder recuperar las constantes implicadas en la operación SUMA. Para darle todo bien masticado lo que hacemos es alterar el orden las instrucciones. Primero le diremos a la maquina que cargue los valores y luego que haga la operación suma.
- Entrada: 3+4
- Según la entrada lo lógico es pensar: LEE VALOR + SÚMALO CON + LEE VALOR
- Lo que la maquina recibe realmente es: LEE VALOR + LEE VALOR + HAZ LA SUMA
Gracias a este orden no necesitaremos movernos hacia adelante/atrás en la lista de instrucciones… será todo una lista continua. Ha esto se le conoce con el nombre de "Notación Polaca Inversa".
Finalmente solo nos queda implementar nuestra máquina! y verás que es muy simple!
class VirtualMachine(object):
def __init__(self):
self.stack = []
self.OP_CODES_REFS = {
OP_CODES['ADD']: self._oper_add,
OP_CODES['SUBSTRACT']: self._oper_substract,
OP_CODES['MULTIPLY']: self._oper_multiply,
OP_CODES['DIVIDE']: self._oper_divide,
}
self.NAMES_REFS = {
'min': self._min,
'max': self._max,
}
self.parser = Parser()
def eval(self, data):
tokens = self.parser.tokenizer(data)
parse_info = self.parser.parse(tokens)
for instr in parse_info['instructions']:
if instr == OP_CODES['LOAD_CONST']:
self.stack.append(parse_info['values'].pop(0))
elif instr == OP_CODES['LOAD_NAME']:
dname = parse_info['values'].pop(0)
if dname in self.NAMES_REFS:
valB = self.stack.pop()
valA = self.stack.pop()
self.stack.append(self.NAMES_REFS[dname](valA, valB))
else:
raise Exception(f"Nombre '{dname}' no disponible!")
elif instr == OP_CODES['UNITARY_NEGATIVE']:
self.stack.append(self.stack.pop() * -1)
elif (
instr == OP_CODES['ADD'] or
instr == OP_CODES['SUBSTRACT'] or
instr == OP_CODES['MULTIPLY'] or
instr == OP_CODES['DIVIDE']
):
valB = self.stack.pop()
valA = self.stack.pop()
self.stack.append(self.OP_CODES_REFS[instr](valA, valB))
return self.stack.pop()
def _oper_add(self, a, b):
return a + b
def _oper_substract(self, a, b):
return a - b
def _oper_multiply(self, a, b):
return a * b
def _oper_divide(self, a, b):
return a / b
def _min(self, a, b):
return min(a, b)
def _max(self, a, b):
return max(a, b)
Script Final
math_eval.py:
import sys
SYMBOLS = {
'GROUP': '()',
'IGNORED': ', ',
'SIGN': '+-',
'OPER': '+-*/',
}
LEXER_TYPES = {
'NUMBER': 1,
'SIGN_POSITIVE': 2,
'SIGN_NEGATIVE': 3,
'NAME': 4,
'LGROUP': 5,
'RGROUP': 6,
'OPER_ADD': 7,
'OPER_SUBSTRACT': 8,
'OPER_MULTIPLY': 9,
'OPER_DIVIDE': 10,
}
LEXER_GROUP = (LEXER_TYPES['LGROUP'], LEXER_TYPES['RGROUP'])
LEXER_OPER = (
LEXER_TYPES['OPER_ADD'],
LEXER_TYPES['OPER_SUBSTRACT'],
LEXER_TYPES['OPER_MULTIPLY'],
LEXER_TYPES['OPER_DIVIDE'],
)
LEXER_SIGN = (LEXER_TYPES['SIGN_POSITIVE'], LEXER_TYPES['SIGN_NEGATIVE'])
OPER_PRECEDENCES = {
LEXER_TYPES['NAME']: 4,
LEXER_TYPES['OPER_DIVIDE']: 3,
LEXER_TYPES['OPER_MULTIPLY']: 3,
LEXER_TYPES['OPER_ADD']: 2,
LEXER_TYPES['OPER_SUBSTRACT']: 2,
}
OP_CODES = {
'LOAD_CONST': 1,
'LOAD_NAME': 2,
'UNITARY_POSITIVE': 3,
'UNITARY_NEGATIVE': 4,
'ADD': 5,
'SUBSTRACT': 6,
'MULTIPLY': 7,
'DIVIDE': 8,
}
LEXER_OP_CODES = {
LEXER_TYPES['NUMBER']: OP_CODES['LOAD_CONST'],
LEXER_TYPES['SIGN_POSITIVE']: OP_CODES['UNITARY_POSITIVE'],
LEXER_TYPES['SIGN_NEGATIVE']: OP_CODES['UNITARY_NEGATIVE'],
LEXER_TYPES['NAME']: OP_CODES['LOAD_NAME'],
LEXER_TYPES['OPER_ADD']: OP_CODES['ADD'],
LEXER_TYPES['OPER_SUBSTRACT']: OP_CODES['SUBSTRACT'],
LEXER_TYPES['OPER_MULTIPLY']: OP_CODES['MULTIPLY'],
LEXER_TYPES['OPER_DIVIDE']: OP_CODES['DIVIDE'],
}
class Parser(object):
def tokenizer(self, data):
tokens = []
buff = ""
def appendToken(value):
tokens.append(self.lexer(value, tokens[-1] if tokens else None))
for lett in data:
if lett in SYMBOLS['GROUP'] or lett in SYMBOLS['OPER'] or lett in SYMBOLS['IGNORED']:
if buff:
appendToken(buff)
buff = ""
if lett not in SYMBOLS['IGNORED']:
appendToken(lett)
else:
buff += lett
if buff:
appendToken(buff)
return tokens
def lexer(self, token, prev_token):
lexer_type = 'NAME'
san_token = token.strip()
if self._isNumber(token):
lexer_type = 'NUMBER'
san_token = self._toNumber(san_token)
elif self._isSign(token, prev_token):
lexer_type = 'SIGN_POSITIVE' if token == SYMBOLS['SIGN'][0] else 'SIGN_NEGATIVE'
elif self._isMathOper(token):
if token == SYMBOLS['OPER'][0]:
lexer_type = 'OPER_ADD'
elif token == SYMBOLS['OPER'][1]:
lexer_type = 'OPER_SUBSTRACT'
elif token == SYMBOLS['OPER'][2]:
lexer_type = 'OPER_MULTIPLY'
elif token == SYMBOLS['OPER'][3]:
lexer_type = 'OPER_DIVIDE'
elif self._isGroup(token):
lexer_type = 'LGROUP' if token == SYMBOLS['GROUP'][0] else 'RGROUP'
return [LEXER_TYPES[lexer_type], san_token]
def parse(self, tokens):
# Based on 'Shunting yard algorithm'
operator_stack = []
sign_token = None
intructions = []
values = []
def add_instruction(token):
op_code = LEXER_OP_CODES[token[0]]
intructions.append(op_code)
if op_code == OP_CODES['LOAD_CONST'] or op_code == OP_CODES['LOAD_NAME']:
values.append(token[1])
prev_lett = None
for token in tokens:
token_type, token_value = token
if token_type == LEXER_TYPES['NUMBER']:
add_instruction(token)
if sign_token:
add_instruction(sign_token)
sign_token = None
elif token_type == LEXER_TYPES['NAME']:
operator_stack.insert(0, token)
elif token_type in LEXER_SIGN:
sign_token = token
elif token_type == LEXER_TYPES['RGROUP']:
while operator_stack and operator_stack[0][0] != LEXER_TYPES['LGROUP']:
add_instruction(operator_stack.pop(0))
operator_stack.pop(0)
elif token_type in LEXER_OPER:
while operator_stack and operator_stack[0][0] in OPER_PRECEDENCES and OPER_PRECEDENCES[token_type] <= OPER_PRECEDENCES[operator_stack[0][0]]:
add_instruction(operator_stack.pop(0))
operator_stack.insert(0, token)
else:
operator_stack.insert(0, token)
prev_token = token
while len(operator_stack):
token = operator_stack.pop(0)
if token[0] in LEXER_GROUP:
raise Exception("Los parentesis no coinciden")
add_instruction(token)
return {
'instructions': intructions,
'values': values,
}
def _toNumber(self, token):
try:
return int(token)
except ValueError:
return float(token)
def _isNumber(self, token):
try:
self._toNumber(token)
except ValueError:
return False
return True
def _isIgnored(self, token):
return token in SYMBOLS['IGNORED']
def _isMathOper(self, token):
return token in SYMBOLS['OPER']
def _isGroup(self, token):
return token in SYMBOLS['GROUP']
def _isSign(self, token, prev_token_info):
return token in SYMBOLS['SIGN'] and (
not prev_token_info or
prev_token_info[0] in LEXER_OPER or
prev_token_info[0] == LEXER_TYPES['LGROUP']
)
class VirtualMachine(object):
def __init__(self):
self.stack = []
self.OP_CODES_REFS = {
OP_CODES['ADD']: self._oper_add,
OP_CODES['SUBSTRACT']: self._oper_substract,
OP_CODES['MULTIPLY']: self._oper_multiply,
OP_CODES['DIVIDE']: self._oper_divide,
}
self.NAMES_REFS = {
'min': self._min,
'max': self._max,
}
self.parser = Parser()
def eval(self, data):
tokens = self.parser.tokenizer(data)
parse_info = self.parser.parse(tokens)
for instr in parse_info['instructions']:
if instr == OP_CODES['LOAD_CONST']:
self.stack.append(parse_info['values'].pop(0))
elif instr == OP_CODES['LOAD_NAME']:
dname = parse_info['values'].pop(0)
if dname in self.NAMES_REFS:
valB = self.stack.pop()
valA = self.stack.pop()
self.stack.append(self.NAMES_REFS[dname](valA, valB))
else:
raise Exception(f"Nombre '{dname}' no disponible!")
elif instr == OP_CODES['UNITARY_NEGATIVE']:
self.stack.append(self.stack.pop() * -1)
elif (
instr == OP_CODES['ADD'] or
instr == OP_CODES['SUBSTRACT'] or
instr == OP_CODES['MULTIPLY'] or
instr == OP_CODES['DIVIDE']
):
valB = self.stack.pop()
valA = self.stack.pop()
self.stack.append(self.OP_CODES_REFS[instr](valA, valB))
return self.stack.pop()
def _oper_add(self, a, b):
return a + b
def _oper_substract(self, a, b):
return a - b
def _oper_multiply(self, a, b):
return a * b
def _oper_divide(self, a, b):
return a / b
def _min(self, a, b):
return min(a, b)
def _max(self, a, b):
return max(a, b)
vmachine = VirtualMachine()
res = vmachine.eval(sys.argv[1])
print(f"El Resultado de '{sys.argv[1]}' es: {res}")
** Se usa: python math_eval.py "(4+2)*-3"
Con estos principios puedes llegar a crear tu propio lenguaje de programación o un interprete para uno existente, … pero se añaden algunos conceptos más como "bloque", "frame", etc…
No es un Hilo completo ni completado