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?
