rpn.py

class State:
  state_handlers = {
    's_open': ('h_open', 'h_num'),
    's_close': ('h_close', 'h_op'),
    's_num': ('h_num'),
    's_op': ('h_op')
  }

  state_map = {
    'h_open': 's_open',
    'h_num': 's_close',
    'h_op': 's_open',
    'h_close': 's_close'
  }

  def __init__(self, s):
    self.src = s
    self.mode = 's_open'
    self.pos = 0
    self.priority = 0
    self.max_priority = 0
    self.parsed = []
  
  def parse(self):
    self.parsed = []
    while self.pos < len(self.src):
      ok = False
      for handler_name in State.state_handlers[self.mode]:
        handler = Handler.getHandler(handler_name)
        ok = handler.parse(self)
        if ok:
          self.mode = State.state_map[handler_name]
          break
      if not ok:
        break

class Handler:
  def __init__(self):
    self.value = ''

  @staticmethod
  def getHandler(name):
    if name == 'h_open':
      return OpenHandler()
    elif name == 'h_op':
      return OpHandler()
    elif name == 'h_num':
      return NumHandler()
    elif name == 'h_close':
      return CloseHandler()

    return None

  def parse(self, state):
    result = False
    while state.pos < len(state.src):
      if self.check(state.src[state.pos], state):
        result = True
        state.pos += 1
      else:
        break
    if self.value:
      state.parsed.append(self.value)
      self.value = ''

    return result

class OpenHandler(Handler):
  def check(self, char, state):
    if char == '(':
      state.priority += 1
      return True

    return False

class CloseHandler(Handler):
  def check(self, char, state):
    if char == ')':
      state.priority -= 1
      return True

    return False

class OpHandler(Handler):
  ops = {'+':0, '-':0, '*':1, '/':1}
  def check(self, char, state):
    if char in self.ops:
      priority = 2 * state.priority + OpHandler.ops[char]
      if state.max_priority < priority:
        state.max_priority = priority
      self.value = (char, priority)
      return True

    return False

class NumHandler(Handler):
  def check(self, char, state):
    if char in '0123456789':
      self.value += char
      return True

    return False

class RPNBuilder:
  @staticmethod
  def build(data, max_priority):
    while max_priority >= 0:
      i = 1
      while i < len(data):
        (op, priority) = data[i]
        if priority == max_priority:
          left = data[i - 1]
          right = data[i + 1]
          data[i - 1] = left + ' ' + right + ' ' + op
          del data[i : i + 2]
        else:
          i += 2
      max_priority -= 1

    return data[0]

state = State('128*(3+64)-1')
state.parse()

print(RPNBuilder.build(state.parsed, state.max_priority))