具有标记列表的解释器递归波兰表示法

我有解释波兰表示法的解释器。我拥有令牌中的所有操作和数字，并且我有一个令牌列表。因此，例如- - 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并返回结果（ - 7 2），记住结果并回到先前未完成的操作。任何帮助？

来源

2016-05-25 Blabla

听起来像你需要比解释器更多的解析器。 – stuartd

@stuartd：OP可能试图同时解析和解释。 – IAbstract

看看[this]（http://codereview.stackexchange.com/questions/48632/math-equation-as-string-to-reverse-polish-notation-parser）。我在2年前写了这个作为一个学习项目。它当然可以改进，但它应该有所帮助。 – JRLambert

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

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-25 16:24:06 Lee

虽然没有优先顺序。不确定哪里适合OP的范围。 – IAbstract

好的，我需要什么，如果我也有一元操作？如果我加上'else if（tok is IUnaryOperation）{var result =（（IUnaryOperation）tok）.Evaluate（eval.Pop（））; eval.Push（结果）'？ – Blabla

@IAbstract - RPM中没有优先顺序。可能存在源语法，但解析器会处理该语法。 – Lee

看来你试图解释没有括号的波兰语前缀，所以你必须知道每个操作符的操作数（没有其他参数）。 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-25 17:08:55 Sylwester

具有标记列表的解释器递归波兰表示法

回答

相关问题