Skip to content

Instantly share code, notes, and snippets.

@ls0f
Created June 23, 2016 08:41
Show Gist options
  • Save ls0f/bbafc255386d611ef107362c1eb31ff3 to your computer and use it in GitHub Desktop.
Save ls0f/bbafc255386d611ef107362c1eb31ff3 to your computer and use it in GitHub Desktop.
cal
#coding:utf-8
'''
expr ::= term { (+|-) term }*
term ::= factor { (*|/) factor }*
factor ::= ( expr )
| NUM
'''
class Token(object):
def __init__(self, type, value):
self.type = type
self.value = value
def __str__(self):
return "type:%s, value:%s" % (self.type, self.value)
def gen_tokens(text):
index = 0
while index < len(text):
c = text[index]
index += 1
if c in (" ", "\t", "\n"):
continue
elif c == "+":
yield Token("+", c)
elif c == "-":
yield Token("-", c)
elif c == "*":
yield Token("*", c)
elif c == "/":
yield Token("/", c)
elif c == "(":
yield Token("(", c)
elif c == ")":
yield Token(")", c)
elif str.isdigit(c):
s = index - 1
while index < len(text) and str.isdigit(text[index]):
index += 1
yield Token("NUM", text[s:index])
class Parse(object):
def __init__(self):
self.token = None
self.next_token = None
self.tokens = None
def parse(self, text):
self.tokens = gen_tokens(text)
self.advance()
return self.expr()
def advance(self):
self.token, self.next_token = self.next_token, next(self.tokens, None)
def accept(self, type):
if self.next_token and self.next_token.type == type:
self.advance()
return True
return False
def expr(self):
exp = self.term()
while self.accept("+") or self.accept("-"):
op = self.token.type
r = self.term()
if op == "+":
exp += r
else:
exp -= r
return exp
def term(self):
exp = self.factor()
while self.accept("*") or self.accept("/"):
op = self.token.type
r = self.factor()
if op == "*":
exp *= r
else:
exp /= r
return exp
def factor(self):
if self.accept("NUM"):
return int(self.token.value)
elif self.accept("("):
exp = self.expr()
self.accept(")")
return exp
else:
raise
if __name__ == "__main__":
p = Parse()
print p.parse("2")
print p.parse("1+2")
print p.parse("2+1*3")
print p.parse("2*((1+7) - 5))")
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment