Python Data Structures and Algorithms

Parsing a reverse Polish expression

Now we are going to build up a tree for an expression written in postfix notation. Then we will calculate the result. We will use a simple tree implementation. To keep it really simple, since we are going to grow the tree by merging smaller trees, we only need a tree node implementation:

    class TreeNode:         def __init__(self, data=None):             self.data = data             self.right = None             self.left = None 

In order to build the tree, we are going to enlist the help of a stack. You will see why soon. But for the time being, let us just create an arithmetic expression and set up our stack:

        expr = "4 5 + 5 3 - *".split()         stack = Stack() 

Since Python is a language that tries hard to have sensible defaults, its split()