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?

@stuartd: OP is probably trying to parse and interpret at the same time. — IAbstract, May 25 '16 at 16:27
Take a look at [this](http://codereview.stackexchange.com/questions/48632/math-equation-as-string-to-reverse-polish-notation-parser). I wrote this about 2 years ago as a learning project. It can certainly be improved, but it should help. — Jacob Lambert, May 25 '16 at 16:28

Lee · Accepted Answer · 2016-05-25T16:45:14.573

3

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.

edited May 25 '16 at 16:45

answered May 25 '16 at 16:24

Lee

142,018
20
234
287

No order of precedence, though. Not sure where that fits into the OP's scope. – IAbstract May 25 '16 at 16:28
Ok, What i need if I have also Unary operations? Would it be ok if I add `else if (tok is IUnaryOperation){ var result = ((IUnaryOperation)tok).Evaluate(eval.Pop()); eval.Push(result)`? – Blabla May 25 '16 at 16:30
@IAbstract - There is no order of precedence in RPM. There could be in the source grammar but that would be handled by the parser. – Lee May 25 '16 at 16:31
Well, true, @Lee ... but the way the OP wrote the initial sequence `- - 5 4 2` must then already have been parsed from `5 4 - 2 -`. Otherwise the original sequence isn't written in RPN ... technically. – IAbstract May 25 '16 at 16:40
Thanks, but there is also another error in code here `var tok = tokens.RemoveAt(tokens.Count - 1);` it says that it cannot assign void to an implicity-typed variable. So `RemoveAt()` returns void, with what should I replace with this code? – Blabla May 25 '16 at 16:43
ok great, now question, what if we divide by zero? how to implement exception? – Blabla May 25 '16 at 16:57
@IAbstract OP never metions **reverse** poish. Just that it's recursive and that it's polish (as in LISP/ prefix) – Sylwester May 25 '16 at 17:13
@Blabla - You could throw it in the implementation of the `DivideToken.Evaluate` method. Otherwise you could add a case in the evaluation function for `DivideToken` and throw if the second stack element is 0. – Lee May 25 '16 at 17:31

score 0 · Answer 2 · answered May 25 '16 at 17:08

It seems you are trying to interpret polish prefix without parentheses so that you would have to know the number of operands per operator (no rest args). The STOPToken is redundant or perhaps just to catch to short or long expressions?

when you eval your list of tokens and it happen to be SubtractionToken you pop it from the list and run eval twice (one for each argument) and with the results apply your function and return the answer.

Example: If the tokens are - - 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

Perhaps the reson for stop is - - 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

Now for a mutable data structure you just pop the tokens off, but for a functional version you'd need to return both the value and the tokens that still can be read and the second eval needs to use that to fetch it's expression or else you will read the same expression twice.

Interpreter recursive Polish Notation with tokens list

2 Answers2