Алгоритм для оценки префиксного выражения?

Question

У меня есть префиксное выражение, в котором есть только 4 бинарных оператора (+, -, *, /). Прямым способом оценки такого выражения является преобразование его в постфиксное выражение, а затем оценка этого выражения. Но я ищу алгоритм, который делает это напрямую, не преобразовывая его в какое-либо другое выражение?

Answer 1

Простой рекурсии:

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

Используйте стопку. Поместите ваши вары и операторы и начните выскакивать каждый стек, один для операторов, а другой для varaiablss (количество всплывающих окон в зависимости от arity).