Re: [QUIZ] Postfix to Infix (#148)

Since Pastie doesn't seem to be so reliable (at least today):

###########################################
# Ruby quiz #148
# http://www.rubyquiz.com/quiz148.html
# Eric Duminil
# 02/12/2007
#
### It removes unnecesary ().
#
#  ruby postfix_to_infix.rb '56 34 213.7 + * 678 -'
#  56*(34+213.7)-678
#  =13193.2
#
#  ruby postfix_to_infix.rb '1 56 35 + 16 9 - / +'
#  1+(56+35)/(16-9)
#  =14
#
#  ruby postfix_to_infix.rb '1 2+ 4* 5*'
#  (1+2)*4*5
#  =60
#
### You can omit spaces between operands and operators
#
#  ruby postfix_to_infix.rb '1 2+ 4* 5+ 3-'
#  (1+2)*4+5-3
#  =14
#
#  ruby postfix_to_infix.rb '1 2+ 3 4 + +'
#  1+2+3+4
#  =10
#
#  ruby postfix_to_infix.rb '1 2 - 3 4 - -'
#  1-2-(3-4)
#  =0
#
### You can use either ** or ^
### which actually raises troubles while parsing : is "**" == "* *" or
"**"=="^"  ?
#
#  ruby postfix_to_infix.rb '2 2 ^ 2 ^'
#  (2^2)^2
#  =16
#
#  ruby postfix_to_infix.rb '2 2 ** 2 **'
#  (2**2)**2
#  =16
#
#  ruby postfix_to_infix.rb '2 3 4 ** **'
#  2**3**4
#  =2417851639229258349412352
#
#  ruby postfix_to_infix.rb '2 3 ** 4 **'
#  (2**3)**4
#  =4096
#
### It raises when something's missing
#
#  ruby postfix_to_infix.rb '1 2+ 4* 5+ 3'
#  postfix_to_infix.rb:94:in `convert_to_infix': ArgumentError
#
#
### No UnaryOperation yet


class Operation
  attr_reader :operator, :operands
  attr_writer :with_parentheses
  def initialize(operator, *operands)
    @operator=operator
    @operands=operands
    @with_parentheses=false
    add_parentheses_to_operands_if_necessary!
  end

  def has_parentheses?
    @with_parentheses
  end
end

class BinaryOperation<Operation
  @@precedence_over={
    '+' =>['',''],
    #no need to put () before -
    '-'  =>['','- +'],
    '*' => ['- +','- +'],
    '/' => ['- +','- + * /'],
    '**'=>['- + * / ^ **','- + * /'],
    '^'=>['- + * / ^ **','- + * /']
  }

  def to_s
    operands.collect{|operand| if operand.is_a?(Operation) &&
operand.has_parentheses? then
        "(#{operand})"
      else
        operand
      end
    }.join(operator)
  end

  private

  def add_parentheses_to_operands_if_necessary!
    operands.each_with_index{|operand,i|
      operators_with_lower_priority=@@precedence_over[operator][i].split(' ')
      operand.with_parentheses=operators_with_lower_priority.any?{|o|
operand.operator == o} if operand.is_a?(BinaryOperation)
    }
  end
end

class Postfix<String
  def split_into_operands_and_operators
    self.scan(/([\w\.]+|\*+|\+|\/|\-|\^)/).flatten
  end

  def to_infix
    @to_infix||=convert_to_infix
  end

  def evaluate
    eval(self.to_infix.gsub(/\^/,'**'))
  end

  private

  def convert_to_infix
    stack=[]
    self.split_into_operands_and_operators.each{|term|
      if term=~/^[\w\.]+$/ then
        stack<<term
      else
        right_operand,left_operand=stack.pop,stack.pop
        stack<<BinaryOperation.new(term,left_operand,right_operand)
      end
    }
    raise ArgumentError unless stack.size==1
    stack.first.to_s
  end
end

p=Postfix.new(ARGV[0])
puts p.to_infix
puts "=#{p.evaluate}"

###########################################



see http://pastie.caboo.se/124473 for colored syntaxing

Thanks again,

Eric











On 03/12/2007, Artem Voroztsov <[e-mail]> wrote:
> All solutions you posted are fun. But now it's time for REAL challenge. :)))
>
>   'a b c d = 1 2 + and = ='
>     should be converted to
>   'a = b = ( c = d and 1 + 2 )'
>
> My program does this.
>
> The final task is: having information about operators priorities,
> commutativity/non-commutativity, and associativity type (left or
> right)
> construct OP_STRENGTH
>
> input = 'a b c d = 1 2 + and = ='
>
>   #
>   OP_STRENGTH = {
>     :left  => {'and'=>-1, '='=>1, '+'=>2, '-'=>2, '*'=>4, '/'=>4},
>     :right => {'and'=>-1, '='=>0 ,'+'=>2, '-'=>3, '*'=>4, '/'=>5}
>   }
>
>   def parenthesize(triplet, top_op_strength, side)
>     q = [ [triplet, top_op_strength, side] ]
>     while !q.empty?
>       t,top_op_strength,side = q.pop
>       if t.is_a?(Array)
>         if OP_STRENGTH[side][t[1]] < top_op_strength
>           print '( '
>           q << ')'
>         end
>         q << [t[2], OP_STRENGTH[:right][t[1]], :left]
>         q << t[1]
>         q << [t[0], OP_STRENGTH[:left][t[1]], :right]
>       else
>         print t, ' '
>       end
>     end
>   end
>
>   require 'benchmark'
>   puts Benchmark.measure {
>     stack = []
>     input.strip.split.each do |token|
>       case token
>       when '*', '+', '/', '-', '=', 'and'
>         stack << [stack.pop, token, stack.pop].reverse!
>       else
>         stack << token
>       end
>     end
>
>     parenthesize(stack.last, 0, :right)
>     puts
>   }
>
>
> And the second thing.
> For inputs
>
>   '0 ' + (1..10000).to_a.join(' - ') + ' *'
>   (1..N).to_a.join(' ') + ' /' * (N-1)
>
> where N = 10000 i have benchmark:
>
>   0.282000   0.000000   0.282000
>   0.313000   0.000000   0.313000
>
>