Created
June 23, 2016 08:41
-
-
Save ls0f/bbafc255386d611ef107362c1eb31ff3 to your computer and use it in GitHub Desktop.
cal
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#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