From: Christian von Kleist <cvonkleist@...>
Date: 2007-12-04T05:56:27+09:00
Subject: Re: [QUIZ] Postfix to Infix (#148)

On Dec 3, 2007 3:44 PM, Eric DUMINIL <eric.duminil@gmail.com> wrote:
> 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 <artem.voroztsov@gmail.com> 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
> >
> >
>
>

OOO = "*/+-"
COM = "+*"

def postfix_to_infix(expression)
  terms = []
  expression.split(/\s/).each do |p|
    terms << p
    if OOO.include?(p)
      terms << [terms.slice!(-1), terms.slice!(-2), terms.slice!(-1)]
    end
  end
  peval(terms[0])
end

def peval(terms, parent_o = nil, is_right = false)
  return [terms, terms.to_f] unless terms.class == Array

  o = terms[0]
  a, a_val = peval(terms[1], o)
  b, b_val = peval(terms[2], o, true)

  sval = [a, o, b].join(' ')
  nval = a_val.send(o, b_val)

  if (OOO.index(o) > OOO.index(parent_o || o)) ||
    (!COM.include?(o) && OOO.index(o) == OOO.index(parent_o || o) && is_right)
    sval = '(' + sval + ')'
  end

  [sval, nval]
end

res = postfix_to_infix(ARGV[0])
puts res[0], res[1]



% ruby /tmp/rt.rb '56 34 213.7 + * 678 -'
56 * (34 + 213.7) - 678
13193.2


Some tests:

56 * (34 + 213.7) - 678 == 56 * (34 + 213.7) - 678 -> pass
2 + 3 == 2 + 3 -> pass
1 + (56 + 35) / (16 - 9) == 1 + (56 + 35) / (16 - 9) -> pass
1 + 2 + 3 + 4 == 1 + 2 + 3 + 4 -> pass
1 - 2 - (3 - 4) == 1 - 2 - (3 - 4) -> pass
5 - (1 - 2 - (3 - 4)) == 5 - (1 - 2 - (3 - 4)) -> pass
5 / (1 / 2 / (3 / 4)) == 5 / (1 / 2 / (3 / 4)) -> pass
2 / 7 / 9 == 2 / 7 / 9 -> pass
2 / (7 / 9) == 2 / (7 / 9) -> pass