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:

Saber Python

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:

Deterministas: Se puede conocer los pasos desde la entrada hasta la salida
No Deterministas: No se puede conocer los pasos hasta que la máquina no se pone en marcha.

** 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