Convert Expression to Reverse Polish Notation

Question

Given an expression string array, return the Reverse Polish notation of this expression. (remove the parentheses)

Have you met this question in a real interview? Yes Example For the expression [3 - 4 + 5] (which denote by ["3", "-", "4", "+", "5"]), return [3 4 - 5 +] (which denote by ["3", "4", "-", "5", "+"])

Thoughts

先用expression build, 再post order traversal expression tree就是reverse polish notation

Solution

class MyNode():
    def __init__(self, val, s):
        self.left = None
        self.right = None
        self.val = val
        self.s = s

class Solution:
    # @param expression: A string list
    # @return: The Reverse Polish notation of this expression
    def convertToRPN(self, expression):
        # write your code here
        if not expression:
            return None
        result = []
        root = self.buildTree(expression)
        self.postOrder(root, result)
        return result

    def postOrder(self, root, result):
        if not root:
            return
        if root.left:
            self.postOrder(root.left, result)
        if root.right:
            self.postOrder(root.right, result)
        result.append(root.s)

    def buildTree(self, expression):
        stack = []
        val = 0
        base = 0
        for i, s in enumerate(expression):
            #get priority
            if s == "(":
                base += 10
                #bracket doesn't add into stack, just continue
                continue
            elif s == ")":
                base -= 10
                continue
            val = self.getVal(s, base)
            curr = MyNode(val, s)
            while stack and val <= stack[-1].val:
                curr.left = stack.pop()
            if stack:
                stack[-1].right = curr
            stack.append(curr)
        if not stack:
            return None
        return stack[0]

    def getVal(self, s, base):
        if s == "+" or s == "-":
            return 1 + base
        elif s == "*" or s == "/":
            return 2 + base

        return sys.maxint