# coding: utf-8
def getPriority op
  case op
  when '('
    5
  when '0'..'9'
    4
  when '*', '/'
    3
  when '+', '-'
    2
  when ')', nil
    1
  end
end

def rpn exp
  stack = []
  result = []
  stack.push(nil)
  i = 0
  # 演算要素をスタックからポップし、返還後配列の末尾に追加する。
  while i < exp.size
    elementPriority = getPriority(exp[i])
    stackTop = stack.last
    while getPriority(stackTop) >= elementPriority && stackTop != '('
      result << stack.pop
      stackTop = stack.last
    end
    # 返還前配列を参照し、演算処理をする。
    if  exp[i] == ')'
      stack.pop
    else
      stack.push(exp[i])
    end
    i += 1
  end
  # スタックに残った演算要素を、返還後配列の末尾に追加する。
  while stack.last != nil
    result << stack.pop
  end
  result.join(' ')
end

puts rpn '1+2*3'
puts rpn '(2+3)*4'