从前缀顺序表达式构建语法树的算法

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