Instantly share code, notes, and snippets.

Embed
What would you like to do?
Simple Python Parser for Leetcode 65 - Valid Number
# So.. I wrote a parser for that... I know there are many easier ways,
# but this parser just feels more generic and with a little extension
# for result handling, it can actually be extended to a fully functional
# recursive descendant parser.
# The parser is based on Monadic Parsing common in functional languages
class Parser:
def parse(self, a):
pass
class Many(Parser):
def __init__(self, p):
self.parser = p
def parse(self, a):
m = self.parser.parse(a)
res = []
rem = a
while m:
(rem, r) = m
res.append(r)
m = self.parser.parse(rem)
return (rem, res)
class Many1(Parser):
def __init__(self, p):
self.parser = p
def parse(self, a):
m = self.parser.parse(a)
if m:
(rem, res) = m
(rem2, res2) = Many(self.parser).parse(rem)
return (rem2, [res] + res2)
return None
class Char (Parser):
def __init__(self, c):
self.ch = c
def parse(self, a):
try:
if a[0] == self.ch:
return (a[1:], self.ch)
except:
pass
return None
class Satisfy(Parser):
def __init__(self, cond):
self.cond = cond
def parse(self, a):
try:
if self.cond(a[0]):
return (a[1:], a[0])
except:
pass
return None
class Return(Parser):
def __init__(self, v):
self.val = v
def parse(self, a):
return (a, self.val)
class Bind(Parser):
def __init__(self, p, f):
self.parser = p
self.f = f
def parse(self, a):
m = self.parser.parse(a)
if m:
(rem, res) = m
return self.f(res).parse(rem)
return None
class Sequential(Parser):
def __init__(self, p1, p2):
self.p1 = p1
self.p2 = p2
def parse(self, a):
return Bind(self.p1, lambda _: self.p2).parse(a)
class Try(Parser):
def __init__(self, p):
self.parser = p
def parse(self, a):
m = self.parser.parse(a)
return m if m else (a, [])
class Alternative(Parser):
def __init__(self, p1, p2):
self.p1 = p1
self.p2 = p2
def parse(self, a):
(rem, res) = Try(self.p1).parse(a)
if len(rem) == len(a):
return self.p2.parse(a)
return (rem, res)
spaces = Many(Char(' '))
digit = Satisfy(lambda x: x >= '0' and x <= '9')
digits = Many1(digit)
point = Char('.')
intandpoint = Sequential(digits, Try(point))
fraction = Sequential(point, digits)
stdfraction = Sequential(intandpoint, Try(digits))
sign = Try(Alternative(Char('-'), Char('+')))
number = Sequential(sign, Alternative(fraction, stdfraction))
exponential = Sequential(Satisfy(lambda x: x == 'E' or x == 'e'),
Sequential(sign, digits))
valid = Sequential(Sequential(spaces, Sequential(number, Try(exponential))),
spaces)
def validNumber(s):
m = valid.parse(s)
if m:
(rem, _) = m
return rem == ''
return False
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment