From: Artem Voroztsov <artem.voroztsov@...>
Date: 2007-12-04T04:51:36+09:00
Subject: Re: [QUIZ] Postfix to Infix (#148)

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