numbata · July 18, 2012 22:50 · Jul 18, 2012
diff --git a/gistfile1.sh b/gistfile1.sh
@@ -0,0 +1,5 @@
+# Example
+
+    > ./rpn.rb '3 + 4 * 2 / (1 - 5) * 2'
+    RPN: 3 4 2 * 1 5 - / 2 * +
+    Result: -1.0
diff --git a/rpn.rb b/rpn.rb
@@ -0,0 +1,87 @@
+#!/usr/bin/env ruby
+
+class RPN
+  class Token < String
+    OPS_PRIORITY_MAP = [
+      '',
+      %w(- +),
+      %w(* /) 
+    ]
+
+    def priority
+      OPS_PRIORITY_MAP.index{|ops| ops.include? self} || 0
+    end
+
+    def operator?
+      OPS_PRIORITY_MAP.flatten.include? self
+    end
+
+    def open_bracket?
+      self == '('
+    end
+
+
+    def close_bracket?
+      self == ')'
+    end
+  end
+
+  def self.transform(expression)
+    result = []
+    operators = []
+
+    self.operands(expression).each do |token|
+      if token.operator?
+        if operators.last && token.priority <= operators.last.priority
+          result << operators.pop
+        end
+        operators << token
+      elsif token.close_bracket?
+        until operators.last.open_bracket? do
+          result << operators.pop
+        end
+        operators.pop
+      elsif token.open_bracket?
+        operators << token
+      else
+        result << token
+      end
+    end
+
+    (result + operators.reverse).join(' ')
+  end
+
+  def self.calc(expression)
+    stack = []
+    operands(expression).each do |token|
+      if token.operator?
+        b = stack.pop.to_f
+        a = stack.pop.to_f
+        stack << a.send(token.to_s, b)
+      else
+        stack << token
+      end
+    end
+
+    stack.last
+  end
+
+  private
+
+  # Split string to operators
+  #
+  # @param String expression
+  # @return Array
+  def self.operands expression
+    ops = Token::OPS_PRIORITY_MAP.flatten
+    expression.split(/(?:\s+|(?=[0-9]+)(?<![0-9])|(?=[#{ops.join}()]))/).map{|x| Token.new(x)}
+  end
+
+end
+
+
+expression = ARGV.join(' ')
+rpn_expression = RPN.transform(expression)
+puts "RPN: #{rpn_expression}"
+result = RPN.calc(rpn_expression)
+puts "Result: #{result}"