algorithm - online - Algoritmo para evaluar la expresión del prefijo

infix to postfix online

Question

Tengo una expresión de prefijo que solo tiene los 4 operadores binarios (+, -, *, /). Una forma directa de evaluar tal expresión es convertirla a una expresión de postfijo y luego evaluar esa expresión. Pero estoy buscando un algoritmo que lo haga directamente sin convertirlo a ninguna otra expresión.

Answer 1

Recursión simple:

Evaluate(input):
  Read a token from input.
  If the token is a value:
    Return the value of the token
  If the token is a binary operator:
    Let first_argument = Evaluate(input)
    Let second_argument = Evaluate(input)
    Return apply(operator, first_argument, second_argument)

Answer 2

Usa una pila. Coloque sus vars y operadores y comience a hacer estallar cada pila, uno para operadores y otro para varaiablss (el número de pops depende de arity).