On Wed, 5 Dec 2001, Sacha Chua wrote:
> > Actually, no. Each postfix expression is equivalent to exactly one > fully-parenthesized infix expression, if my math is still correct. > Incidentally, it's also the same as exactly one infix expression. > that's correct. in Graph Theory, your 'parse tree' is actually a spanning binary tree whose leaves are 9s and whose non-leaf nodes are operators. running the postfix/prefix/infix traversal over the spanning tree will yield exactly one expression. the reverse is true. the property of a spanning tree is that there is exactly only one way from one node to another. this makes a traversal produce exactly one expression and vice versa. produce all the possible trees, you produce all the possible infix/postfix/prefix equations. it's a one-to-one mapping. you know what folks, Graph Theory is a field of math where they derived OSPF (open-shortest path first) used to do dynamic IP routing. it's based on djikstra's shortest path algo. this is also where Huffman derived some file compression algo using his huffman tree. so sacha, in case you're given a project for this course, choose to make the file compressor (ala pkzip) using huffman trees. it's definitely worth the fun! pong _ Philippine Linux Users Group. Web site and archives at http://plug.linux.org.ph To leave: send "unsubscribe" in the body to [EMAIL PROTECTED] To subscribe to the Linux Newbies' List: send "subscribe" in the body to [EMAIL PROTECTED]
