```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
# 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