Basic CalculatorI II LeetCode OJ
3500 ワード
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