What type of algorithm would be used to construct a syntax tree from an expression represented in prefix order notation?
A:
Sbm007
2010-07-12 22:14:04
Isn't that to go from infix to postfix? Care to explain how you will get from prefix to expression tree using this?
Moron
2010-07-12 22:16:10
The wiki page seems to say the Shunting-yard algorithm converts infix notation, whereas my expressions are in prefix notation.
Johnny
2010-07-12 22:17:32
You are totally right, I have mis read the question. My apologies
Sbm007
2010-07-12 22:18:14
+1
A:
A simple recursive algorithm can convert a prefix-order expression to a syntax tree.
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))
Jeffrey L Whitledge
2010-07-12 22:30:52