Created
July 3, 2014 09:08
-
-
Save alexband/5f5bc1a8ba720f6438aa to your computer and use it in GitHub Desktop.
Revisions
-
alexband created this gist
Jul 3, 2014 .There are no files selected for viewing
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters. Learn more about bidirectional Unicode charactersOriginal file line number Diff line number Diff line change @@ -0,0 +1,174 @@ 用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()