Skip to content

Instantly share code, notes, and snippets.

@rymndhng
Last active August 29, 2015 14:12
Show Gist options
  • Save rymndhng/a81eb5b44dbdc127f637 to your computer and use it in GitHub Desktop.
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
# 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