gistfile1.py

用python写一个将中缀表达式转换为逆波兰表达式的程序，并用unittest模块为它配上单元测试

## Notes:
## Version 1: I submitted solution failed last time. And copied my local code again into this box. (Called Huang Xiaomao already. :-)) 
## Version 2: Add code to handle operators * and /, which with high priority.
## Version 3: Add code to handle parentheses. (Test Failed)
## Version 4: Fix test failure about handling parentheses, add test case. (Failed to submit code agian, so copied the local code. )
## Version 5: #TODO: Do refactor about logic, and code paths. (Too busy on current working staff, will not do this any more. :-))

#!/usr/bin/python

import unittest

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

supported_operators = ['+', '-', '*', '/', '(', ')'] 
operator_priority_dict = {'+': 1, '-':1, '*':2, '/':2 }

def convert_notation(origin_notation):
    output_str = ''
    tree_root = convert_to_tree(origin_notation)
    output_str = travel_tree(tree_root, output_str)
    print "Final result: " + output_str + '\n --------'
    return output_str

def travel_tree(tree_node, output_str):
    if tree_node.left != None:
        output_str = travel_tree(tree_node.left, output_str)
    if tree_node.right != None:
        output_str = travel_tree(tree_node.right, output_str)
    output_str = output_str + tree_node.data
    # print "Current result: " + output_str
    return output_str

def insert_tree_node(character, root_node):
    if character == '(':
        print "New node: " + character
        virtual_node = TreeNode(character)
        if root_node == None:
            root_node = virtual_node            
        else:
            virtual_node.parent = root_node
            root_node.right = virtual_node
            root_node = virtual_node
        return root_node
    elif character == ')':
        while root_node.parent != None and root_node.data != '(':
            root_node = root_node.parent
            if root_node.data == '(':
                break
        if root_node.data == '(':
            print "New node: " + character
            virtual_node = TreeNode(character)
            root_node.right = virtual_node
            virtual_node.parent = root_node
        return root_node
    else:
        #TODO: handle the muiti-digit number.
        if character.isdigit():
            # New node
            print "New digit node: " + character
            new_digit_node = TreeNode(character)
            if None == root_node:
                root_node = new_digit_node
            else:
                if root_node.data in supported_operators:
                    if root_node.data == '(':
                        sub_tree_node = insert_tree_node(character, None)
                        root_node.left = sub_tree_node
                        sub_tree_node.parent = root_node
                        root_node = sub_tree_node
                    else:
                        root_node.right = new_digit_node
                        new_digit_node.parent = root_node
                        
                        # Need to reset root_node value, if the current root_node still has parent node.
                        while root_node.parent != None and root_node.parent.data != '(':
                            root_node = root_node.parent
                    
        elif character in supported_operators:
                    # Handle next opreator character.
            print "New operator node: " + character
            new_operator_node = TreeNode(character)
            if root_node.data.isdigit():
                new_operator_node.left = root_node
                new_operator_node.parent = root_node.parent
                if root_node.parent != None: 
                    root_node.parent.left = new_operator_node
                root_node.parent = new_operator_node
                root_node = new_operator_node
            elif root_node.data == '(':
                new_operator_node.left = root_node.left
                new_operator_node.parent = root_node.parent
                root_node.left.parent = new_operator_node
                root_node = new_operator_node
               # return root_node
            elif root_node.data != ')':
                if operator_priority_dict[character] <= operator_priority_dict[root_node.data]:
                    #  operator_node should be the parent of digit node.
                    new_operator_node.left = root_node
                    root_node.parent = new_operator_node
                    root_node = new_operator_node
                elif operator_priority_dict[character] > operator_priority_dict[root_node.data]:
                    # Handle operators with high priority
                    new_operator_node.parent= root_node
                    new_operator_node.left = root_node.right
                    root_node.right = new_operator_node
                    new_operator_node.left.parent = new_operator_node
                    root_node = new_operator_node
        
    return root_node
    
    
def convert_to_tree(origin_notation):
    # Convert the origin string to a tree. Then walk the tree to output the reverse polish notation.
    root_node = None
    for character in origin_notation:
        root_node = insert_tree_node(character, root_node)
        
        # Handle the ')' at the end of string...
    while root_node.parent != None:
        if root_node.data == '(' and root_node.right.data == ')':
            if root_node.parent == None:
                root_node.left.parent = None
                root_node = root_node.left
            else:
                root_node.parent.right = root_node.left
                root_node.left.parent = root_node.parent
            root_node = root_node.left
        root_node = root_node.parent            
    return root_node

class TestConvert(unittest.TestCase):
    def test_simple_addition(self):
        convertedStr = convert_notation("2+3")
        self.assertEquals("23+", convertedStr)
    
    def test_simple_additions(self):
        convertedStr = convert_notation("2+3+5")
        self.assertEquals("23+5+", convertedStr)
        
    def test_simple_multiply(self):
        convertedStr = convert_notation("3+4*5")
        self.assertEquals("345*+", convertedStr)
        
    def test_simple_multiply_2(self):
        convertedStr = convert_notation("3*4+5")
        self.assertEquals("34*5+", convertedStr)

    def test_simple_multiply_3(self):
        convertedStr = convert_notation("2/3-4*5")
        self.assertEquals("23/45*-", convertedStr)

    def test_simple_multiply_4(self):
        convertedStr = convert_notation("2/3*4-5*6/7")
        self.assertEquals("23/4*56*7/-", convertedStr)
    
    def test_simple_notation_with_parentheses(self):
        convertedStr = convert_notation("(2+3)*4")
        self.assertEquals("23+4*", convertedStr)        
     
    def test_simple_notation_with_parentheses_1(self):
        convertedStr = convert_notation("2*(3+4)")
        self.assertEquals("234+*", convertedStr)     
if __name__ == '__main__':
    unittest.main()