1

我有解释波兰符号的解释器。我有令牌中的所有操作和数字，并且我有一个令牌列表。例如- - 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)，记住结果并返回之前未完成的操作。有什么帮助吗？

4

2 回答 2

3

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

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

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

于 2016-05-25T16:24:06.857 回答
0

似乎您正在尝试解释没有括号的波兰语前缀，因此您必须知道每个运算符的操作数数量（无剩余参数）。STOPToken 是多余的，还是只是为了捕捉短或长的表达式？

当您eval的令牌列表恰好是SubtractionToken您从列表中弹出它并运行 eval 两次（每个参数一个）并使用结果应用您的函数并返回答案时。

示例：如果令牌是- - 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

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

于 2016-05-25T17:08:55.490 回答