Interpreter recursive Polish Notation with tokens list

Question

I have interpreter that solve Polish notation. I have all operations and numbers in tokens and I have a list of tokens. So for example - - 5 4 2 is a list with these tokens:

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

Example tokens:

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

}

So, I cannot understand how to make recursive function to solve this problems. Because when I SubstractionToken.Inrerpret(value, value) I need to give the values from numberTokens what should be substract from itself, but what happen if the next token is an operation token? or we have - 5 - 7 2? I don't know how to implement such recursive function which will detect that the first operation should be made - 7 2 then - 5 and resultof(- 7 2), remember the results and back to the previous not done operations. Any help?

Answer 1

You usually do this with an evaluation stack which stores the results you've seen so far. When you encounter a number on in the input you push it on the stack and when you encounter a binary operation (e.g. '-') you pop two values from the stack, interpret them and push the result. Something like:

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

this could easily be made an iterative function if required.