algorithm - プレフィックス式を評価するアルゴリズム？

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

スタックを使用します。変数と演算子を配置し、各スタックのポップを開始します。1つは演算子用で、もう1つはvaraiablss用です（ポップの数はアリティによって異なります）。