带有标记列表的解释器递归波兰表示法

Question

我有解波兰语符号的解释器。我有令牌中的所有操作和数字，我有一个令牌列表。因此，例如 - - 5 4 2 是一个包含这些标记的列表：

SubtractionToken, SubtractionToken, NumberToken, NumberToken, NumberToken, STOPToken.

示例标记：

class SubstractToken : IBinaryOperation
{
    public Number Interpret(Number value1, Number value2)
    {
        Number c = new Number(value1.Value() - value2.Value());
        return c;
    }
}

class Number : IToken
{
    private int value;

    public Number(int val)
    {
        value = val;
    }

    public int Value()
    {
        return value;
    }

}

所以，我无法理解如何使用递归函数来解决这个问题。因为当我 SubstractionToken.Inrerpret(value, value) 我需要给出 numberTokens 的值时，应该从自身减去什么，但是如果下一个标记是操作标记会发生什么？或者我们有 - 5 - 7 2？我不知道如何实现这样的递归函数，它将检测到应该进行第一个操作 - 7 2 然后 - 5 和 resultof(- 7 2)，记住结果并返回到之前未完成的操作。有帮助吗？

Answer 1

您通常使用一个评估堆栈来执行此操作，该堆栈存储您目前看到的结果。当你在输入中遇到一个数字时，你将它压入堆栈，当你遇到二进制操作（例如'-'）时，你从堆栈中弹出两个值，解释它们并压入结果。类似于：

public static Number Evaluate(List<IToken> tokens, Stack<Number> eval) {
    if(tokens.Count == 0) {
        if(eval.Count != 1) throw new InvalidArgumentException("Invalid expression");
        return eval.Pop();
    }
    var tok = tokens[tokens.Count-1];
    tokens.RemoveAt(tokens.Count-1);
    if (tok is Number) {
        eval.Push(tok);
    }
    else if(tok is IBinaryOperation) {
        var result = ((IBinaryOperation)tok).Evaluate(eval.Pop(), eval.Pop());
        eval.Push(result);
    }
    //handle other cases
    return Evaluate(tokens, eval);
}

如果需要，这可以很容易地成为一个迭代函数。

Answer 2

您似乎在尝试解释不带括号的波兰语前缀，这样您就必须知道每个运算符的操作数数量（无剩余参数）。 STOPToken 是多余的还是可能只是为了捕获短表达式或长表达式？

当你 eval 你的标记列表恰好是 SubtractionToken 你从列表中弹出它并且运行 eval 两次（每个参数一个）和结果应用你的函数和 return 答案。

示例：如果令牌是 - - 2 3 4 X

top is -, takes two arguments
  top is -, takes two arguments
    top is 2 
    top is 3, we have 2 arguments apply
  5
  top is 4, we have two arguments apply
9 , finished (X is left on stack)
check if X is the top to ensure the expression is valid

停止的原因可能是- - 5 X

top is -, takes two arguments
  top is -, takes two arguments
    top is 5
    top is X --> throw exception since the stop token is illegal as argument

现在，对于可变数据结构，您只需弹出令牌，但对于功能版本，您需要 return 值和令牌仍然可以读取，第二个 eval 需要使用它来获取它的表达式，否则您将读取相同的表达式两次。

带有标记列表的解释器递归波兰表示法

Interpreter recursive Polish Notation with tokens list

c#

recursion

polish-notation