活動日誌

■ [Ruby]Rubyist Magazine 0015 号

出ました。

http://jp.rubyist.net/magazine/?0015

■ [Ruby]夏休みの宿題 -- ポーランド記法

http://jp.rubyist.net/magazine/?0015-EditorsNote

そのまんまの書き方しかできなかった。

OPERATORS = %w(+ - * /)

def rpolish2tree(expr)
  stack = []
  expr.each do |t|
    if OPERATORS.include?(t)
      rhs = stack.pop
      lhs = stack.pop
      stack.push([t, lhs, rhs])
    else
      stack.push(t)
    end
  end
  stack[0]
end

def tree2polish(tree, result)
  if tree.is_a?(Array)
    op, lhs, rhs = tree
    result.push(op)
    tree2polish(lhs, result)
    tree2polish(rhs, result)
  else
    result.push(tree)
  end
  result
end


def polish2tree(expr)
  stack = []
  expr.each do |t|
    stack.push(t)

    while stack.size >= 3 && OPERATORS.include?(stack[-3]) && !OPERATORS.include?(stack[-2]) && !OPERATORS.include?(stack[-1])
      rhs = stack.pop
      lhs = stack.pop
      op = stack.pop
      stack.push([op, lhs, rhs])
    end
  end
  stack[0]
end

def tree2rpolish(tree, result)
  if tree.is_a?(Array)
    op, lhs, rhs = tree
    tree2rpolish(lhs, result)
    tree2rpolish(rhs, result)
    result.push(op)
  else
    result.push(tree)
  end
  result
end


rpolish = %w(1 2 2 / + 3 4 5 * + -)
#p rpolish2tree(rpolish)
p tree2polish(rpolish2tree(rpolish), [])

polish = %w(- + 1 / 2 2 + 3 * 4 5)
#p polish2tree(polish)
p tree2rpolish(polish2tree(polish), [])