Last active
August 29, 2015 14:12
-
-
Save rymndhng/a81eb5b44dbdc127f637 to your computer and use it in GitHub Desktop.
Solves valid number parsing for: https://oj.leetcode.com/problems/valid-number/. Parsing strings for valid integer value is something you use in your Programming Languages. Here -- I tried to model the code similar to how I would conceptually think of the problem. In this case -- Python was great for providing a minimal interface
This file contains hidden or 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
# use a state machine model | |
class State: | |
def __init__(self, name, chars): | |
self.name = name | |
self.chars = chars | |
def __contains__(self, item): | |
return item in self.chars | |
def __repr__(self): | |
return "State('%s', '%s')" % (self.name, self.chars) | |
# These represent all the different states of the we are in and the values that transition into that state. | |
START = State('start', ' ') | |
WHOLE = State('whole', '0123456789') | |
DOT = State('dot', '.') | |
FRACTIONAL = State('frac', '0123456789') | |
E = State('e', 'e') | |
E_SIGN = State('esign', '+-') | |
E_NUMBER = State('e_number', '0123456789') | |
SIGN = State('neg', '-+') | |
END = State('end', ' ') | |
DEBUG = False | |
# An Exit State is a dictionary of `keys` which represent the allowed EXIT STATE and check function (because number parsing has some edge cases). | |
EXIT_STATES = { | |
WHOLE: None, | |
E_NUMBER: lambda col: (WHOLE in col) or (FRACTIONAL in col), | |
DOT: lambda col: len(col) > 1 and col[-2] not in [START, SIGN], | |
FRACTIONAL: None, | |
} | |
def transition(c, available_states): | |
""" Operation that gets the next state from the current character. Returns None if we cannot transition to the next state. | |
""" | |
for state in available_states: | |
if c in state: | |
# print "From %s, transitioning into %s" % (c, state) | |
return state | |
# print "From %s, transitioning into None" % c | |
return None | |
class Solution: | |
# @param s, a string | |
# @return a boolean | |
def isNumber(self, s): | |
previous = [] | |
state = START | |
for c in s: | |
if state is START: | |
state = transition(c, [START, WHOLE, SIGN, DOT]) | |
elif state is WHOLE: | |
state = transition(c, [WHOLE, DOT, E, END]) | |
elif state is DOT: | |
state = transition(c, [FRACTIONAL, END, E]) | |
elif state is FRACTIONAL: | |
state = transition(c, [FRACTIONAL, END, E]) | |
elif state is END: | |
state = transition(c, [END]) | |
elif state is E: | |
state = transition(c, [E_NUMBER, E_SIGN]) | |
elif state is E_NUMBER: | |
state = transition(c, [E_NUMBER, END]) | |
elif state is E_SIGN: | |
state = transition(c, [E_NUMBER, END]) | |
elif state is SIGN: | |
state = transition(c, [DOT, E, WHOLE, FRACTIONAL]) | |
else: | |
return False | |
if state is not END: | |
previous.append(state) | |
last_state = previous[-1] | |
if DEBUG: | |
print "previous: %s" % previous | |
for exit_state, fn in EXIT_STATES.items(): | |
if last_state is exit_state: | |
return (fn == None) or fn(previous) | |
return False | |
# This below section contains the unit tests I failed -- so I made sure to get them correct. Some of these are due to lack of requirements. | |
soln = Solution() | |
DEBUG = True | |
assert soln.isNumber(" ") == False | |
assert soln.isNumber("e") == False | |
assert soln.isNumber("123") == True | |
assert soln.isNumber("1 ") == True | |
assert soln.isNumber("2e10") == True | |
assert soln.isNumber(".1") == True | |
assert soln.isNumber("3.") == True | |
assert soln.isNumber(".") == False | |
assert soln.isNumber(" .") == False | |
assert soln.isNumber("3. ") == True | |
assert soln.isNumber(". ") == False | |
assert soln.isNumber("-1.") == True | |
assert soln.isNumber("+.8") == True | |
assert soln.isNumber(" -.") == False | |
assert soln.isNumber("46.e3") == True | |
assert soln.isNumber(".e1") == False | |
assert soln.isNumber(".2e81") == True | |
assert soln.isNumber(" 005047e+6") == True |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment