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

Question

我有解释波兰语符号的解释器。我有 token 中的所有操作和数字，我有一个 token 列表。因此，例如 - - 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);
}

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