Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Ruby Quiz - Postfix to Infix (#148) 翻訳

Ruby Quiz(James Edward Gray II氏が管理)の#148「Postfix to Infix」の一部の翻訳(意訳を含む)。

クイズの概要 Quiz Summary

The big advantage of postfix expressions is that they are built with a stack in mind. This turns out to be a powerful way to do math both for computers and humans. HP makes some great RPN calculators that literally display a stack on the screen and give you the tools the manipulate it. To handle the expression:

2 3 +

on a calculator like that, you could type a two followed by the enter key to push the number onto the stack. Similarly, three and enter pushes that number, shifting the two up a slot. Finally, pressing the plus key pops two values from the stack, performs the requested operation, and pushes the result back onto the stack.

後置式の大きな利点は、それらがスタックを念頭に置いて構築されていることです。 これは、コンピュータおよび人間の両方にとって、数学をするための強力な方法となっています。 HPは、文字通りスクリーン上にスタックを表示し、それを操作するためのツールを提供する、偉大なRPN計算機をいくつか作りました。 そのような計算機で次の式:

2 3 +

を扱うには、2に続いてスタックにその数をプッシュするためにエンターキーをタイプすればよいです。 同様に、3とエンターはその数をプッシュし、2をスロットの上方へ移動させます。 最終的に、プラスキーを押すと、2つの値をスタックからポップし、要求された演算を実行し、その結果をスタック上にプッシュバックします。

We can solve this problem just like that. We only need to change that final step to push an equivalent infix expression back to the stack, instead of some mathematical result. Here is some code from Jesús that does just that:

私たちは、ちょうどそのようにしてこの問題を解くことができます。 私たちに必要なのは、最後の段階を、数学的な結果ではなく等価な中置式をスタックにプッシュバックするように変えることだけです。 そのようにする、神から賜ったコードはこちらです:

stack = []
expr = ARGV.join(" ")
expr.split(/ /).each do |x|
  case x
  when *%w{+ * - /}
    op2 = stack.pop
    op1 = stack.pop
    stack.push "(#{op1} #{x} #{op2})"
  else
    stack.push x
  end
end
puts stack.pop

Note that the first line creates the key data structure, our stack. From there the code iterates over each chunk of the expression. When the chunk isn't an operator it must be a number and push()ed onto the stack by the else clause. For operators, two values are pop()ped, transformed into an infix String, and pushed back onto the stack. The first operand pop()ped is actually the right-hand side operand, so it's important to remember to reverse them as Jesús does here. The final line of code just pop()s and prints the final element from the stack which will be our infix expression.

最初の行で鍵となるデータ構造、スタックを作っていることに注意してください。 そこから、コードは式の各チャンクをイテレートします。 チャンクが演算子でなければそれは数であり、else節によってスタックにpush()されます。 演算子では、2つの値がpop()され、中置文字列へと変換され、スタックにプッシュバックされます。 Pop()される最初のオペランドは、実際には右手側のオペランドであるため、ここで神が行っているように、それらを反転することを覚えておくのが重要です。 コードの最後の行は、スタックから中置式となっているだろう最後の要素をpop()して出力するだけです。

This code solves the problem and produces perfectly accurate translations. The only downside is that it adds a lot of parentheses to ensure the order of evaluation is handled correctly. While that's not at all wrong, the expressions could be a little prettier if we drop some of the unneeded symbols.

このコードは問題を解き、完璧に正確な翻訳を生み出します。 唯一つの欠点は、評価の順番が正しく処理されたことを保証するために、多くの括弧を追加することです。 それは誤りではまったくありませんが、私たちがいくつかの不要な記号を除けば、その式は少し読みやすくなるかもしれません。

To do that, we need to make our stack a little smarter. James Koppel sent in a solution that reads the postfix expression like we have already seen, but instead of building Strings as the results it builds a custom syntax tree object. That object is smart enough to convert itself into an infix expression with minimal parentheses. Let's examine how that works.

そのようにするには、スタックをもう少し賢くする必要があります。 James Koppelは、私たちが既に見てきたように後置式を読みますが、結果としてStringを構築するのではなく、特別な構文木オブジェクトを構築する解決策を送ってきてくれました。 そのオブジェクトは、自身を最小限の括弧が付いた中置式に変換するのに十分に賢いものです。 それでは、それがどのように動くのか、調べてみましょう。

Here's the start of the code:

コードの最初はこのようになっています:

PREC = {
  :+ => 0,
  :- => 0,
  :* => 1,
  :/ => 1,
  :% => 1,
  :^ => 2
}

LEFT_ASSOCS = {
  :+ => true,
  :- => true,
  :* => true,
  :/ => true,
  :% => true,
  :^ => false
}

RIGHT_ASSOCS = {
   :+ => true,
   :- => false,
   :* => true,
   :/ => false,
   :% => false,
   :^ => true
 }

class TreeNode
  attr_accessor :el, :left, :right

  def initialize(el,left,right)
    @el,@left,@right=el,left,right
  end

  # ...

You've seen this code before. It's almost identical to Jesús's solution. The primary difference here is that the code is converting to Float and TreeNode objects, instead of working in Strings. The stack still guides the process, but the result is an abstract syntax tree.

あなたは以前このコードを見ています。 それはほとんど神の解決策と同等です。 ここでの最初の違いは、コードがString内で作業するのではなく、FloatおよびTreeNodeオブジェクトへと変換していることです。 スタックは依然としてプロセスを導いていますが、結果は抽象構文木となっています。

Once we have a tree, we need the code to convert it to an infix expression:

一度木を手に入れれば、それを中置式に変換するコードが必要になります:

# ...

  def to_minparen_infix
    l, r = [left, right].map { |o| o.to_minparen_infix }

    if left.respond_to?(:el) &&
      (PREC[left.el] < PREC[self.el] ||
       (PREC[self.el] == PREC[left.el] && !LEFT_ASSOCS[self.el]))
      l = "(#{l})"
    end

    if right.respond_to?(:el) &&
      (PREC[right.el] < PREC[self.el] ||
       (PREC[self.el] == PREC[right.el] && !RIGHT_ASSOCS[self.el]))
      r= "(#{r})"
    end

    "#{l} #{self.el} #{r}"
  end
end

class Float
  def to_minparen_infix
    if self % 1 == 0
      to_i.to_s
    else
      to_s
    end
  end
end

The conversion for a given node isn't too hard to understand. First, convert the left and right subexpressions. For Floats this amounts to the helper method that Stringifies them with or without trailing decimal digits at the bottom of the code. For another TreeNode this is just a recursive process.

与えられたノードの変換は、理解するのにそれほど難しくありません。 最初に、左と右の副次式を変換します。 Floatでは、これは、コードの一番下にある、小数点以下をつけるあるいはつけない、文字列化のヘルパーメソッドに預けられます。 その他のTreeNodeでは、これは単なる再帰プロセスです。

Once we have the minimal left and right subexpression the question becomes, do they need parentheses? The middle lines of TreeNode#to_minparen_infix sort this out. If a subexpression isn't a simple Float (which won't have an el() method) and it has a precedence lower than us or the same us when we aren't a left associative operator, parentheses are added. A similar check then is made for the right side using the right associativity table. With any needed parenthesis in place, the expression is simply the left subexpression followed by our operator and the right subexpression.

左および右の最小の副次式を手に入れたところで疑問が生じます。 それらには括弧が必要でしょうか? 真ん中の TreeNode#to_minparen_infix がこれを解決します。 もし副次式が単純なFloat(el() メソッドを持っていない)ではなく、かつ、「それが自分より低い優先順位を持っている、あるいは自分が左結合性演算子でなく優先順位が同じ」場合、括弧が追加されます。 そして、同様のチェックが、右結合性テーブルを使って右側に対しても行われます。 必要な括弧が配置されれば、式は単純に「左の副次式 自分の演算子 右の副次式」となります。

The application code just needs to hand-off the argument to the program and trigger the conversion of the root node. The result of that conversion can be printed as a final infix expression with minimal parentheses. Here's that code:

アプリケーションのコードに必要なのは、引数をプログラムに渡し、ルートノードの変換をトリガーすることだけです。 その変換結果は、最小限の括弧を伴う最終的な中置式として出力することができます。 そのコードはこちらです:

# ...

puts TreeNode.from_postfix(ARGV.first.split(/ /)).to_minparen_infix
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment