Переводчик рекурсивный Польский Обозначение с помощью списка токенов

Question

У меня есть переводчик, который решает польскую нотацию. У меня есть все операции и числа в токенах, и у меня есть список токенов. Так, например - - 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 (значение, значение), мне нужно указать значения от numberTokens, что должно быть выводом из себя, но что произойдет, если следующий токен - это токен операции? или у нас есть - 5 - 7 2? Я не знаю, как реализовать такую ​​рекурсивную функцию, которая обнаружит, что первая операция должна быть выполнена - 7 2 then - 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); 
} 

это может быть легко сделано итеративной функцией, если требуется.

Answer 2

Кажется, вы пытаетесь интерпретировать префикс латинского текста без круглых скобок, чтобы вам было нужно знать количество операндов на одного оператора (без аргументов покоя). 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 должен использовать это для извлечения его выражения, иначе вы будете читать одно и то же выражение дважды.