Implement a basic calculator to evaluate a simple expression string. The expression string contains only non-negative integers, '+', '-', '*', '/' operators, and open '(' and closing parentheses ')'. The integer division should truncate toward zero.
import collections
class Solution:
# Standard parser implementation based on this BNF
# s := expression
# expression := term | term { [+,-] term] }
# term := factor | factor { [*,/] factor] }
# factor :== digit | '(' expression ')'
# digit := [0..9]
def calculate(self, s: str) -> 'Node':
tokens = collections.deque()
if s[0] == '-':
s = '0' + s
hasnum = False
num = 0
for c in s:
if c.isdigit():
num = int(c) + 10 * num
hasnum = True
else:
if hasnum:
tokens.append(num)
num = 0
hasnum = False
tokens.append(c)
if hasnum:
tokens.append(num)
return self.parse_expression(tokens)
def parse_expression(self, tokens):
lhs = self.parse_term(tokens)
while len(tokens) > 0 and tokens[0] in ['+', '-']:
op = tokens.popleft()
rhs = self.parse_term(tokens)
if op == '+':
lhs += rhs
else:
lhs -= rhs
return lhs
def parse_term(self, tokens):
lhs = self.parse_factor(tokens)
while len(tokens) > 0 and tokens[0] in ['*', '/']:
op = tokens.popleft()
rhs = self.parse_factor(tokens)
if op == '*':
lhs *= rhs
else:
lhs = int(lhs/rhs)
return lhs
def parse_factor(self, tokens):
if tokens[0] == '(':
tokens.popleft() # consume '('
val = self.parse_expression(tokens)
tokens.popleft() # consume ')'
return val
else:
# Single operand
token = tokens.popleft()
return token