2011年7月11日月曜日

写経みたいなもの

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク

練習問題への解答

ローマン数字を整数に変換する。peekの実装で、''が読み出されたときにrewindしてしまっていた。


tes.py
import unittest
from roman import roman2numeric

# cases made from http://ja.wikipedia.org/wiki/%E3%83%AD%E3%83%BC%E3%83%9E%E6%95%B0%E5%AD%97

class TestRome2NumericBasicCase(unittest.TestCase):
  def test_none(self):
    self.assertEqual(roman2numeric(''), 0)
  def test_one(self):
    self.assertEqual(roman2numeric('I'), 1)
  def test_five(self):
    self.assertEqual(roman2numeric('V'), 5)
  def test_ten(self):
    self.assertEqual(roman2numeric('X'), 10)
  def test_fifty(self):
    self.assertEqual(roman2numeric('L'), 50)
  def test_hundred(self):
    self.assertEqual(roman2numeric('C'), 100)
  def test_fivehundred(self):
    self.assertEqual(roman2numeric('D'), 500)
  def test_thousand(self):
    self.assertEqual(roman2numeric('M'), 1000)


class TestRome2NumericCombinedCase(unittest.TestCase):
  def test_two(self):
    self.assertEqual(roman2numeric('II'), 2)
  def test_three(self):
    self.assertEqual(roman2numeric('III'), 3)
  def test_six(self):
    self.assertEqual(roman2numeric('VI'), 6)
  def test_seven(self):
    self.assertEqual(roman2numeric('VII'), 7)
  def test_eight(self):
    self.assertEqual(roman2numeric('VIII'), 8)
  def test_eleven(self):
    self.assertEqual(roman2numeric('XI'), 11)
  def test_twenty(self):
    self.assertEqual(roman2numeric('XX'), 20)
  def test_30(self):
    self.assertEqual(roman2numeric('XXX'), 30)

  def test_60(self):
    self.assertEqual(roman2numeric('LX'), 60)
  def test_70(self):
    self.assertEqual(roman2numeric('LXX'), 70)
  def test_80(self):
    self.assertEqual(roman2numeric('LXXX'), 80)

  def test_200(self):
    self.assertEqual(roman2numeric('CC'), 200)
  def test_300(self):
    self.assertEqual(roman2numeric('CCC'), 300)
  def test_600(self):
    self.assertEqual(roman2numeric('DC'), 600)
  def test_800(self):
    self.assertEqual(roman2numeric('DCCC'), 800)

  def test_1100(self):
    self.assertEqual(roman2numeric('MC'), 1100)
  def test_1200(self):
    self.assertEqual(roman2numeric('MCC'), 1200)

  def test_eighteeneityeight(self):
    self.assertEqual(roman2numeric('MDCCCLXXXVIII'), 1888)
  def test_twothousand(self):
    self.assertEqual(roman2numeric('MM'), 2000)


class TestRome2NumericComplexCase(unittest.TestCase):
  def test_four(self):
    self.assertEqual(roman2numeric('IV'), 4)
  def test_nine(self):
    self.assertEqual(roman2numeric('IX'), 9)
  def test_14(self):
    self.assertEqual(roman2numeric('XIV'), 14)
  def test_nineteen(self):
    self.assertEqual(roman2numeric('XIX'), 19)
  def test_fourty(self):
    self.assertEqual(roman2numeric('XL'), 40)
  def test_ninety(self):
    self.assertEqual(roman2numeric('XC'), 90)
  def test_ninetythree(self):
    self.assertEqual(roman2numeric('XCIII'), 93)
  def test_ninenine(self):
    self.assertEqual(roman2numeric('XCIX'), 99)

  def test_400(self):
    self.assertEqual(roman2numeric('CD'), 400)
  def test_900(self):
    self.assertEqual(roman2numeric('CM'), 900)


  def test_nineninenine(self):
    self.assertEqual(roman2numeric('CMXCIX'), 999)
    #self.assertRaise(roman2numeric('IM'), 999) #???

  def test_nineteenninetynine(self):
    self.assertEqual(roman2numeric('MCMXCIX'), 1999)
roman.py
import StringIO


def nullimple(s):
  return 0


'''
  cfg

  R -> Letter*
  Letter -> 'I' | 'V' | 'X' | 'L' | 'C' | 'D' | 'M'
  # too large

  Basic/Combined Level
  'M'*'D'?'C'{0,3}'L'?'X'{0,3}'V'?'I'{0,3}


'''
def CombinedLevel(s):
  r = 0
  for d in s:
    if d == 'M':
      r += 1000
    elif d == 'D':
      r += 500
    elif d == 'C':
      r += 100
    elif d == 'L':
      r += 50
    elif d == 'X':
      r += 10
    elif d == 'V':
      r += 5
    elif d == 'I':
      r += 1
    else:
      raise 'error'
  return r



def ComplexLevel(s):
  '''
  cfg

  R -> thousands hundreds tens ones
  thousands -> 'M' thousands | empty
  hundreds -> 'C' 'M' | range500to800 | 'C''D' | range000to300
  range500to800 -> 'D' range000to300
  range000to300 -> 'C'{0, 3}
  tens -> 'X' 'C' | range50to80 | 'X' 'L' | range00to30
  range50to80 -> 'L' range00to30
  range00to30 -> 'X'{0,3}
  ones -> 'I''X' | range5to8 | 'I''V' | range0to3
  range5to8 -> 'V' range0to3
  range0to3 -> 'I'{0,3}

  '''
  global lookahead, result #ugh!
  result = 0

  buf = StringIO.StringIO(s)
  lookahead = None


  def roman():
    ''' R -> thousands hundreds tens ones '''
    global lookahead
    lookahead = buf.read(1)
    while True:
      if lookahead == 'M':
        thousands()
      else:
        break
    if lookahead in ('C', 'D'):
      hundreds()
    if lookahead in ('X', 'L'):
      tens()
    if lookahead in ('V', 'I'):
      ones()

  def thousands():
    global result
    match('M')
    result += 1000

  def hundreds():
    ''' hundreds -> 'C' 'M' | range500to800 | 'C''D' | range000to300 '''
    global result
    p = peek()
    if p == 'M':
      match('C')
      match('M')
      result += 900
      return
    elif p == 'D':
      match('C')
      match('D')
      result += 400
      return
    elif lookahead == 'D':
      range500to800()
    else:
      range000to300()
    return

  def range500to800():
    global result
    match('D')
    result += 500
    range000to300()

  def range000to300():
    global result
    while True:
      if lookahead == 'C':
        match('C')
        result += 100
      else:
        break
  def tens():
    ''' tens -> 'X' 'C' | range50to80 | 'X' 'L' | range00to30'''
    global result
    p = peek()
    if p == 'C':
      match('X')
      match('C')
      result += 90
      return
    elif p == 'L':
      match('X')
      match('L')
      result += 40
      return
    elif lookahead == 'L':
      range50to80()
    else:
      range00to30()

  def range50to80():
    global result
    match('L')
    result += 50
    range00to30()

  def range00to30():
    global result
    while True:
      if lookahead == 'X':
        match('X')
        result += 10
      else:
        break

  def ones():
    ''' ones -> 'I''X' | range5to8 | 'I''V' | range0to3 '''
    global result
    p = peek()
    if p == 'X':
      match('I')
      match('X')
      result += 9
      return
    elif p == 'V':
      match('I')
      match('V')
      result += 4
      return
    elif lookahead == 'V':
      range5to8()
    else:
      range0to3()

  def range5to8():
    ''' range5to8 -> 'V' range0to3 '''
    global result
    match('V')
    result += 5
    range0to3()

  def range0to3():
    ''' range0to3 -> 'I'{0,3} '''
    global result
    while True:
      if lookahead == 'I':
        match('I')
        result += 1
      else:
        break

  def match(t):
    global lookahead
    if lookahead == t:
      lookahead = buf.read(1)
    else:
      error('expected %s, but got %s'%(t, lookahead))

  def peek():
    #print 'peek pos%d %s'%(buf.tell(), buf.getvalue())
    r = buf.read(1)
    if r:
      buf.seek(-1, 1)
    #print 'peek pos%d %s'%(buf.tell(), buf.getvalue())
    #print 'read:', repr(r)
    return r

  def error(msg):
    raise Exception(msg)

  roman()

  return result

def roman2numeric(s):
  #return nullimple(s)
  #return CombinedLevel(s)
  return ComplexLevel(s)

2011年7月6日水曜日

写経 p87

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク
いろいろ間違えた。


import StringIO



class Token:
  def __init__(self, raw):
    self.raw = raw

  def __eq__(self, x):
    assert isinstance(x, Token)
    return self.raw == x.raw


class Num(Token):
  def __init__(self, raw):
    Token.__init__(self, raw)
    self.value = int(raw)

class Identifier(Token):
  pass

class Div(Token):
  pass

class Mod(Token):
  pass

class Done(Token):
  pass



buf = None
lineno = None
lookahead = None
symtable = dict()


def lexan():
  while True:
    t = buf.read(1)
    if t.isspace():
      pass #skip white spaces
    elif t == '\n':
      lineno = lineno + 1
    elif t.isdigit():
      tokenval = None
      tokenval = int(t)
      t = buf.read(1)
      while t.isdigit():
        tokenval = tokenval * 10 + int(t)
        t = buf.read(1)
      buf.seek(-1, 1)
      return Num(tokenval)
    elif t.isalpha():
      lexbuf = ''
      while t.isalpha() or t.isdigit():
        lexbuf += t
        t = buf.read(1)
        # no size error...
      # lexbuf += EOS python string do not need explicit \0
      if t != '':
        buf.seek(-1, 1)

      # it is better idea to tweek constructor of Identity as a flyweight pattern?
      try:
        i = symtable[lexbuf]
      except KeyError:
        i = Identifier(lexbuf)
        symtable[lexbuf] = i
      return i

    elif t == '': #EOF
      return Done(t)

    else:
      # tokenval = None
      return Token(t) #, tokenval)


def parse():
  global lookahead
  lookahead = lexan()
  while not isinstance(lookahead, Done):
    expr()
    match(';')

def expr():
  global lookahead
  t = None
  term()
  while True:
    if lookahead.raw in ('+', '-'):
      t = lookahead
      match(lookahead)
      term()
      emit(t)
      continue
    else:
      return

def term():
  global lookahead
  factor()
  while True:
    if lookahead.raw in ('*', '/') or isinstance(lookahead, (Div, Mod)):
      t = lookahead
      match(lookahead)
      factor()
      emit(t)
      continue
    else:
      return


def factor():
  global lookahead
  if lookahead.raw == '(':
    match('(')
    expr()
    match(')')
  elif isinstance(lookahead, Num):
    emit(lookahead)
    match(lookahead)
  elif isinstance(lookahead, Identifier):
    emit(lookahead)
    match(lookahead) #Identifier)
  else:
    error("syntax error")
def match(t):
  global lookahead
  if isinstance(t, Token):
    if lookahead == t:
      lookahead = lexan()
    else:
      error("syntax error")
  elif isinstance(t, str):
    if lookahead.raw == t:
      lookahead = lexan()
    else:
      error('lookahead is %s, match arg is %s'%(lookahead.raw,  t))
  else:
    error("syntax error")

def error(msg):
  raise msg + ' at %d'%(lineno)


def emit(t):
  if False:
    pass
  elif isinstance(t, Div):
    print 'Div'
  elif isinstance(t, Mod):
    print 'Mod'
  elif isinstance(t, Num):
    print '%d'%(t.value)
  elif isinstance(t, Identifier):
    print t.raw
  else:
    print "token %s"%(t.raw)



def init():
  global symtable
  symtable['div'] = Div('div')
  symtable['mod'] = Mod('mod')


buf = StringIO.StringIO('2+3 * 5;\n 12 div 7 mod 2;')
lineno = 1

init()
parse()




2011年7月5日火曜日

唐突に写経

このエントリーをブックマークに追加 このエントリーを含むはてなブックマーク
いつまでつづくのやら。

import StringIO
buf = StringIO.StringIO('9-5+2')

lookahead = ''

def expr():
  term()
  while True:
    if lookahead == '+':
      match('+')
      term()
      print '+',
    elif lookahead =='-':
      match('-')
      term()
      print '-',
    else:
      break


def term():
  if lookahead.isdigit():
    print lookahead,
    match(lookahead)
  else:
    error()

def match(t):
  global lookahead
  if lookahead == t:
    lookahead = buf.read(1)
  else:
    error()

def error():
  print 'syntax error'
  raise



lookahead = buf.read(1)
expr()
print '\n'