從前綴順序表達式構建語法樹的算法

Question

將使用什麼類型的算法從以前綴順序符號表示的表達式構造語法樹？

Answer 1

簡單的遞歸算法可以將前綴順序表達式轉換爲語法樹。

GetNextPrefixExpression(tokenStream) 
    nextToken = tokenStream.GetNextToken() 
    if nextToken.IsValue() 
     return new Value(nextToken) 
    else if nextToken.IsUnaryOperator() 
     return new UnaryOperator(nextToken, GetNextPrefixExpression(tokenStream)) 
    else if nextToken.IsBinaryOperator() 
     return new BinaryOperator(nextToken, GetNextPrefixExpression(tokenStream), GetNextPrefixExpression(tokenStream)) 
    else if nextToken.IsTrinaryOperator() 
     return new TrinaryOperator(nextToken, GetNextPrefixExpression(tokenStream), GetNextPrefixExpression(tokenStream), GetNextPrefixExpression(tokenStream))