语言不可知论-评估前缀表达式的算法

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

使用堆栈。放置变量和运算符，开始弹出每个堆栈，一个用于运算符，另一个用于变量（弹出次数取决于arity）。