Expression Evaluation

Question

Given an expression string array, return the final result of this expression

Example For the expression 2*6-(23+7)/(1+2), input is

[
  "2", "*", "6", "-", "(",
  "23", "+", "7", ")", "/",
  (", "1", "+", "2", ")"
],

return 2

Note The expression contains only integer, +, -, *, /, (, ).

Thoughts

expression -> expression tree expression tree -> post order -> reverse polish notation reverse polist notation -> evaluation

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 list of strings;
    # @return: an integer
    def evaluateExpression(self, expression):
        # write your code here
        if not expression:
            return 0
        result = []
        root = self.buildTree(expression)
        self.postOrder(root, result)
        result = self.evalRPN(result)
        return result

    def evalRPN(self, tokens):
        # Write your code here
        if not tokens:
            return 0
        stack = []
        for i in range(len(tokens)):
            cur = tokens[i]
            if cur == "+" or cur == "-" or cur == "*" or cur == "/":
                value1 = float(stack.pop())
                value2 = float(stack.pop())
                if cur == "+":
                    re = value2 + value1
                elif cur == "-":
                    re = value2 - value1
                elif cur == "/":
                    re = value2 / value1
                elif cur == "*":
                    re = value2 * value1
                stack.append(int(re))
            else:
                stack.append(cur)
        return int(stack.pop())        

    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