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.
- Defining left -and right- operator strengths allows us to take into
account different aspects
- priority
- commutativity/ non commutativity
- associativity type (left or right)
- 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?
