c# - 解释器递归波兰语符号与 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），记住结果并返回到之前未完成的操作。有什么帮助吗？

最佳答案

通常，您可以使用评估堆栈来执行此操作，该堆栈存储您到目前为止所看到的结果。当您在输入中遇到数字时，将其压入堆栈中;当您遇到二进制运算符（例如'-'）时，您将从堆栈中弹出两个值，解释它们并压入结果。就像是：

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);
}

如果需要，可以很容易地将其设置为迭代函数。