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

Good day, everybody!

I've added the problem to online contest http://acm.mipt.ru/judge.

   http://acm.mipt.ru/judge/problems.pl?problem=126&lang=en

Now you can check yourself!

Sorry, I will use 'gets' instead of 'ARGV'.

#########################################
# OK
# Let's start with simple one.
# This one just does the job  without removing odd parentheses

stack = []
gets.strip.split.each do |token|
  case token
  when '*', '+', '/', '-'
    stack << [')', stack.pop, token, stack.pop, '('].reverse!
  else
    stack << token
  end
end

puts stack.flatten.join

########################################
#   Now let's do the thing we are here for.
# We will use idea of operator strength.
# Each operator has left and right strength.
# Binary  operation should "protect" itself with parentheses if there
is stronger operator
# to the left or to the right. Two neighbor operators affect each
other with strengths:
# one with left-strength (the one to the right) and another with right-strength
# (the one to the left)
#
OP_STRENGTH = {
  :left  => {'+'=>2, '-'=>2, '*'=>4, '/'=>4},
  :right => {'+'=>2, '-'=>3, '*'=>4, '/'=>5}
}

stack = []
gets.strip.split.each do |token|
  # puts "TOKEN '#{token.inspect}'"
  case token
  when '*', '+', '/', '-'
    stack << [stack.pop, token, stack.pop].reverse!
  else
    stack << token
  end
end

# Uncomment these line to see some sort of 'parse tree'
# require 'yaml'
# puts stack.to_yaml

def parenthesize(triplet, top_op_strength, side)
  if triplet.is_a? Array
    parenthesize(triplet[0], OP_STRENGTH[:left][triplet[1]], :right)
    parenthesize(triplet[2], OP_STRENGTH[:right][triplet[1]], :left)
    if OP_STRENGTH[side][triplet[1]] < top_op_strength
      triplet.push  ')'
      triplet.unshift '('
    end
  end
end

parenthesize(stack.last, 0, :right)

puts stack.flatten.join

#########################################
#
#
# Lets try the previous version with input
#       '0 ' + (1..N-1).to_a.join(' - ') + ' -',
# for N = 15000, 30000, 60000
# We will see two thins
#    1) in `parenthesize': stack level too deep (SystemStackError)
#    2) time grows quadratically. But why? The bad guy is 'flatten'!
#    First of all we should get rid of recursion:

def parenthesize(triplet, top_op_strength, side)
  return unless triplet.is_a?(Array)
  q = [ [triplet, top_op_strength, side] ]
  while !q.empty?
    t,top_op_strength,side = q.pop
    q << [t[0], OP_STRENGTH[:left][t[1]], :right] if t[0].is_a?(Array)
    q << [t[2], OP_STRENGTH[:right][t[1]], :left] if t[2].is_a?(Array)
    if OP_STRENGTH[side][t[1]] < top_op_strength
      t.push  ')'
      t.unshift '('
    end
  end
end
#########################################
#
#  The previous version still work O( L^2), where L is number of
tokens in input expression.
#  Let's get rid of 'flatten':
#
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

parenthesize(stack.last, 0, :right)
puts
############################################
#
#  And finally,  one may prefer Hash version of parse-tree (though
it's a little bit slower):
OP_STRENGTH = {
  :left  => {'+'=>2, '-'=>2, '*'=>4, '/'=>4},
  :right => {'+'=>2, '-'=>3, '*'=>4, '/'=>5}
}

stack = []
gets.strip.split.each do |token|
  case token
  when '*', '+', '/', '-'
    stack << {:r=>stack.pop, :op=>token, :l=>stack.pop}
  else
    stack << token
  end
end

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?(Hash)
      if OP_STRENGTH[side][t[:op]] < top_op_strength
        print '('
        q << ')'
      end
      q << [t[:r], OP_STRENGTH[:right][t[:op]], :left]
      q << t[:op]
      q << [t[:l], OP_STRENGTH[:left][t[:op]], :right]
    else
      print t
    end
  end
end

parenthesize(stack.last, 0, :right)
puts
############################################

Final remarks.

1. Defining left -and right- operator strengths allows us to take into
account different aspects
  1) priority
  2) commutativity/ non commutativity
  3) associativity type (left or right)

2. We discovered problem with Array#flatten. Is it a known issue?
    (I use ruby 1.8.6 (2007-03-13 patchlevel 0) [i386-mswin32])

For  N = 10000, 20000 and  input =  '0 ' + (1..N-1).to_a.join(' - ') + ' -'

  require 'benchmark'
  puts Benchmark.measure {
    stack.flatten
  }
return the following results:

N    time
5000  1.265000
10000  5.141000
20000  20.484000

So, it's quadratic.
While final solution works less than 1 second (0.079 seconds).
What's the problem with flatten?