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 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 items with the help of a stack. Let's 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() method splits on whitespace by default. (If you think about it, this is most likely what you would expect.) The result is going to be that expr is a list with the values 4, 5, +, 5, 3, -, and *.

Each element of the expr list is going to be either an operator or an operand. If we get an operand, then we embed it in a tree node and push it onto the stack. If we get an operator, on the other hand, then we embed the operator into a tree node and pop its two operands into the node's left and right children. Here, we have to take care to ensure that the first pop goes into the right child; otherwise, we will have problems with subtraction and division.

Here is the code to build the tree:

    for term in expr: 
        if term in "+-*/": 
            node = TreeNode(term) 
            node.right = stack.pop() 
            node.left = stack.pop() 
        else: 
            node = TreeNode(int(term)) 
        stack.push(node) 

Notice that we perform a conversion from string to int in the case of an operand. You could use float() instead, if you wish to support floating point operands.

At the end of this operation, we should have one single element in the stack, and that holds the full tree. If we want to evaluate the expression, we would build the following little function:

    def calc(node): 
        if node.data is "+": 
            return calc(node.left) + calc(node.right) 
        elif node.data is "-": 
            return calc(node.left) - calc(node.right) 
        elif node.data is "*": 
            return calc(node.left) * calc(node.right) 
        elif node.data is "/": 
            return calc(node.left) / calc(node.right) 
        else: 
            return node.data 

In the preceding code, we pass in a node to the function. If the node contains an operand, then we simply return that value. If we get an operator, then we perform the operation that the operator represents on the node's two children. However, since one or more of the children could also contain either operators or operands, we call the calc() function recursively on the two child nodes (bearing in mind that all the children of every node are also nodes).

Now, we just need to pop the root node off the stack and pass it into the calc() function. Then, we should have the result of the calculation:

    root = stack.pop() 
    result = calc(root) 
    print(result) 

Running this program should yield the result 18, which is the result of (4 + 5) * (5 - 3).