Basic CalculatorI II LeetCode OJ

原创
2015/09/09 19:56
阅读数 157
class Solution(object):

    def __init__(self):
        self.expressionList = []

    def priority(self, c):
        if(c=="*" or c=="/"):
            return 2
        elif(c=="+" or c=="-"):
            return 1
        else:
            return 0

    def leftPirorityIsNotLess(self, c1, c2):
        if(c1==None):
            return False
        return self.priority(c1)>=self.priority(c2)

    def isNumber(self, c):
        if("0"<=c and c<="9"):
            return True
        return False

    def isLeftBracket(self, c):
        if(c=="("):
            return True
        return False

    def isRightBracket(self, c):
        if(c==")"):
            return True
        return False

    def isOperator(self, c):
        if(c=="+" or c=="-" or c=="*" or c=="/"):
            return True
        return False

    def parse(self, s):
        stack = Stack()
        numString = ""
        charList = list(s)

        for char in charList:
            if(self.isNumber(char)):
                numString += char

            else:
                if(len(numString)>0):
                    self.expressionList.append(Node().setNum(int(numString)))
                    numString = ""
                
                if(self.isLeftBracket(char)):
                    stack.push(char)

                elif(self.isOperator(char)):
                    while(self.leftPirorityIsNotLess(stack.top(), char)):
                        self.expressionList.append( Node().setOp(stack.pop()))
                    stack.push(char)

                elif(self.isRightBracket(char)):
                    while(not self.isLeftBracket(stack.top())):
                        self.expressionList.append(Node().setOp(stack.pop()))
                    stack.pop()
                #default

        if(len(numString)>0):
            self.expressionList.append(Node().setNum(int(numString)))
            numString = ""

        while(not stack.isEmpty()):
            self.expressionList.append(Node().setOp(stack.pop()))

    def calculate(self, s):
        self.parse(s);

        stack = Stack()
        for node in self.expressionList:
            if(node.isNumber()):
                stack.push(node.num)
            else:
                r = stack.pop();
                l = stack.pop();
                stack.push(node.make(l,r));

        return stack.pop();
        
class Node(object):
    def __init__(self):
        self.flag = False;
    def setNum(self, num):
        self.num = num
        self.flag = True;
        return self
    def setOp(self, op):
        self.op = op
        return self
    def isNumber(self):
        return self.flag
    def make(self, left, right):
        if(self.op=="+"):
            return left + right
        if(self.op=="-"):
            return left - right
        if(self.op=="*"):
            return left * right
        if(self.op=="/"):
            return left / right
            
class Stack(object):
    def __init__(self):
        self.items = []
    def push(self, x):
        self.items.append(x)
    def pop(self):
        return self.items.pop()
    def top(self):
        if not self.isEmpty():
            return self.items[len(self.items)-1]
    def isEmpty(self):
        if(len(self.items)==0):
            return True
        else:
            return False


展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部