[QUIZ] Postfix to Infix (#148)

[Alex Shulgin]

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

There are many different ways to write mathematical equations. Infix notation
is probably the most popular and yields expressions like:

2 * (3 + 5)

Some people like to work with a postfix notation (often called Reverse Polish
Notation or just RPN) though, which doesn't require parentheses for the same
equation:

2 3 5 + *

#!/usr/bin/ruby

$prec_tbl = {
['*', '+'] => true,
['*', '-'] => true,
['/', '+'] => true,
['/', '-'] => true,
['-', '-'] => true,
['/', '/'] => true
}

def precede?(top, op)
$prec_tbl[[top, op]]
end

def infix(arr, top = nil)
throw "invalid postfix expression" unless !arr.empty?
op = arr.pop
if op =~ /\+|\-|\*|\//
right = infix(arr, op)
left = infix(arr, op)
par = precede?(top, op)
(par ? "(" : "") + "#{left} #{op} #{right}" + (par ? ")" : "")
else
op
end
end

STDIN.each do |line|
arr = line.split(/\s+/)
begin
res = infix(arr)
throw "invalid postfix expression" unless arr.empty?
puts "#{res} => #{eval(res)}"
rescue
STDERR.puts $!
end
end

 

[Daniel Martin]

I should know better than to try to cleanup my code, and then submit
it without running it first.

This line:
should read
term = Term.new(phrase, term.precedence)

Even with that cleanup, it doesn't seem to work:

esau:/tmp$ ruby asrq148.rb '2 3 - 5 +'
+
esau:/tmp$ ruby asrq148.rb '2 3 -'
-

 

[Alex Shulgin]

#!/usr/bin/ruby

$prec_tbl = {
['*', '+'] => true,
['*', '-'] => true,
['/', '+'] => true,
['/', '-'] => true,
['-', '-'] => true,
['/', '/'] => true

Um... I think, I'm missing this here:

['/', '*'] => true

} [snip]

STDIN.each do |line|
arr = line.split(/\s+/)
begin
res = infix(arr)
throw "invalid postfix expression" unless arr.empty?
puts "#{res} => #{eval(res)}"

And it chokes on division by zero due to the eval() w/o printing the
infix form... :-/

rescue
STDERR.puts $!
end
end

Anyway I think it addresses the basic problem. Nice quiz!

 

[Eugene Kalenkovich]

Finally we got a quiz with 'less than 20 (minutees, loc)' rule satisfied

Here is my solution:

--------------------------------------------------

a=ARGV[0].split

pri='+-*/'

prs=[]
i=0

while a.length>1 do
if pr=pri.index(op=a)
raise if i<2
a[i-2]='('+a[i-2]+')' if pr>>1 > prs[i-2]
a[i-1]='('+a[i-1]+')' if pr>>1 > prs[i-1] || (pr>>1 == prs[i-1] &&
pr&1==1)
a[i-2,3]=a[i-2]+op+a[i-1]
prs[i-=2]=pr>>1
else
prs=4
end
i+=1
end rescue a[0]="invalid expression"

puts a[0]

 

[Voroztsov Artem]

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, p=>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[p]] < top_op_strength
print '('
q << ')'
end
q << [t[:r], OP_STRENGTH[:right][t[p]], :left]
q << t[p]
q << [t[:l], OP_STRENGTH[:left][t[p]], :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?

 

[Voroztsov Artem]

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?

So, here is the code just about 'flatten', not the QUIZ issue.
I write self-made 'flatten' and it works much faster for the
given case and many other cases we get in the quiz problem.

I use ruby 1.8.6 (2007-03-13 patchlevel 0) [i386-mswin32]

Can anybody check it for ruby 1.9.1?

#!/usr/bin/ruby

N = 10000

inputs = []
inputs << '0 ' + (1..N-1).to_a.join(' - ') + ' -'
inputs << (1..N).to_a.join(' ') + (" +" * (N-1))

class Array
def flatten2
res = []
x = self.reverse
while !x.empty?
a = x.pop
if a.is_a?(Array)
x.push(*a)
else
res << a
end
end
res.reverse
end
end

require 'benchmark'

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

res1 = res2 = nil

Benchmark.bm {|b|
b.report('original flatten') {
res1 = stack.flatten
}
b.report('self-made flatten') {
res2 = stack.flatten2
}
}
puts res1 == res2
end


I have the following output:

ruby test_flatten.rb

user system total real
original flatten 5.125000 0.000000 5.125000 ( 5.141000)
self-made flatten 0.032000 0.000000 0.032000 ( 0.031000)
true
user system total real
original flatten 5.063000 0.000000 5.063000 ( 5.079000)
self-made flatten 0.031000 0.000000 0.031000 ( 0.031000)
true

 

[Eric Mahurin]

Note: parts of this message were removed by the gateway to make it a legal Usenet post.

For an added bonus, try to keep the parentheses added to infix expressions
to
the minimum of what is needed.

My solution does the above, plus a few more things:

* maintains an OO data structure (to do everything below)
* further reduce parentheses (and post-fix stack depth) by using some
associativity
* evaluates the result
* gives stack-reduced post-fix form

The basic idea of the solution is to have an object for each expression
(possibly with sub-expressions as operands) and have methods for applying
another operation in either direction (i.e. have both #add and #radd -
reverse add). This allows independent decisions on what each type of
expression should do when it is in either operand of another operation.

Here are a few examples (result shows internal postfix, infix, and result):

ruby quiz148.rb "2 3 5 + *" 2 3 5 + * => 2*(3 + 5) => 16
ruby quiz148.rb "56 34 213.7 + * 678 -"

56 34 213.7 + * 678 - => 56*(34 + 213.7) - 678 => 13193.2

ruby quiz148.rb "1 56 35 + 16 9 - / +"

1 56 35 + 16 9 - / + => 1 + (56 + 35)*(16 - 9) => 14

ruby quiz148.rb "1 2 3 4 5 + + + +"

1 2 + 3 + 4 + 5 + => 1 + 2 + 3 + 4 + 5 => 15

ruby quiz148.rb "1 2 3 4 5 - - - -"

1 2 - 3 + 4 - 5 + => 1 - 2 + 3 - 4 + 5 => 3

Notice the last two. The internal postfix is different compared to the
original. It is better because when evaluating on a stack, less stack space
is needed (old max depth:5, new:2).

This architecture would also allow for further optimizations.

#!/usr/bin/env ruby

class Atom
def initialize(arg)
@data = arg
end
def to_s
@data.to_s
end
def to_a
[@data]
end
def eval
Kernel.eval(@data)
end
def radd(other)
other.add(self)
end
def add(other)
Sum.new(self, other)
end
def rsub(other)
other.sub(self)
end
def sub(other)
Difference.new(self, other)
end
def rmul(other)
other.mul(self)
end
def mul(other)
Product.new(self, other)
end
def rdiv(other)
other.div(self)
end
def div(other)
Quotient.new(self, other)
end
end

class Group < Atom
def initialize(expr)
@expr = expr
end
def to_s
"(#{@expr})"
end
def to_a
@expr.to_a
end
def eval
@expr.eval
end
end

class Sum < Atom
def initialize(left, right)
@left = left
@right = right
end
def to_s
"#{@left} + #{@right}"
end
def to_a
@left.to_a.concat(@right.to_a) << :+
end
def eval
@left.eval + @right.eval
end
def radd(other)
@left.radd(other).add(@right)
end
def rsub(other)
@left.rsub(other).sub(@right)
end
def rmul(other)
other.mul(Group.new(self))
end
def mul(other)
Product.new(Group.new(self), other)
end
def rdiv(other)
other.div(Group.new(self))
end
def div(other)
Quotient.new(Group.new(self), other)
end
end

class Difference < Sum
def to_s
"#{@left} - #{@right}"
end
def to_a
@left.to_a.concat(@right.to_a) << :-
end
def eval
@left.eval - @right.eval
end
def radd(other)
@left.radd(other).sub(@right)
end
def rsub(other)
@left.rsub(other).add(@right)
end
end

class Product < Atom
def initialize(left, right)
@left = left
@right = right
end
def to_s
"#{@left}*#{@right}"
end
def to_a
@left.to_a.concat(@right.to_a) << :*
end
def eval
@left.eval * @right.eval
end
def rmul(other)
@left.rmul(other).mul(@right)
end
def rdiv(other)
# could do this to reduce grouping and stack depth
# but this will increase expensive divisions
# @left.rdiv(other).div(@right)
other.div(Group.new(self))
end
end

class Quotient < Product
def to_s
"#{@left}*#{@right}"
end
def to_a
@left.to_a.concat(@right.to_a) << :/
end
def eval
@left.eval / @right.eval
end
def rmul(other)
@left.rmul(other).div(@right)
end
def rdiv(other)
@left.rdiv(other).mul(@right)
end
end

stack = []
ARGV.each { |arg|
arg.scan(/\S+/) { |token|
case token
when "+" : stack.push(stack.pop.radd(stack.pop))
when "-" : stack.push(stack.pop.rsub(stack.pop))
when "*" : stack.push(stack.pop.rmul(stack.pop))
when "/" : stack.push(stack.pop.rdiv(stack.pop))
else ; stack.push(Atom.new(token))
end
}
}

stack.each { |expr|
puts("#{expr.to_a.join(' ')} => #{expr} => #{expr.eval}")
}

 

[Ken Bloom]

Solutions that minimize parentheses must work with the following test
case:
"3 5 * 5 8 * /" should turn into "3 * 5 / (5 * 8)" not "3 * 5 / 5 * 8"
similarly for
"3 5 + 5 8 + -" which should turn into "3 + 5 - (5 + 8)"

Most of the solutions posted so far get this wrong (I haven't checked
exhaustively). A few that notably get it correct (while in some way
minimzing parentheses):
* Daniel Martin
* Robert Dober

--Ken

 

[Ken Bloom]

Note: parts of this message were removed by the gateway to make it a
legal Usenet post.


My solution does the above, plus a few more things:

* maintains an OO data structure (to do everything below) * further
reduce parentheses (and post-fix stack depth) by using some
associativity
* evaluates the result
* gives stack-reduced post-fix form

The basic idea of the solution is to have an object for each expression
(possibly with sub-expressions as operands) and have methods for
applying another operation in either direction (i.e. have both #add and
#radd - reverse add). This allows independent decisions on what each
type of expression should do when it is in either operand of another
operation.

Here are a few examples (result shows internal postfix, infix, and
result):

56 34 213.7 + * 678 - => 56*(34 + 213.7) - 678 => 13193.2
1 56 35 + 16 9 - / + => 1 + (56 + 35)*(16 - 9) => 14
1 2 + 3 + 4 + 5 + => 1 + 2 + 3 + 4 + 5 => 15
1 2 - 3 + 4 - 5 + => 1 - 2 + 3 - 4 + 5 => 3

This doesn't look right.
3 5 * 5 8 * / => 3*5*(5*8) => 0

--Ken

 

[Eugene Kalenkovich]

Solutions that minimize parentheses must work with the following test
case:
"3 5 * 5 8 * /" should turn into "3 * 5 / (5 * 8)" not "3 * 5 / 5 * 8"
similarly for
"3 5 + 5 8 + -" which should turn into "3 + 5 - (5 + 8)"

Most of the solutions posted so far get this wrong (I haven't checked
exhaustively). A few that notably get it correct (while in some way
minimzing parentheses):
* Daniel Martin
* Robert Dober

Hmm.. Please add my solution to the list

 

[Eric DUMINIL]

As soon as pastie works again, I'll get my script back and ask you to
add my solution to the list!

 

[Robert Dober]

Quoth Ruby Quiz:

The three rules of Ruby Quiz:

1. Please do not post any solutions or spoiler discussion for this quiz until
48 hours have passed from the time on this message.

2. Support Ruby Quiz by submitting ideas as often as you can:

http://www.rubyquiz.com/

3. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps everyone
on Ruby Talk follow the discussion. Please reply to the original quiz message,
if you can.

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=

There are many different ways to write mathematical equations. Infix notation
is probably the most popular and yields expressions like:

2 * (3 + 5)

Some people like to work with a postfix notation (often called Reverse Polish
Notation or just RPN) though, which doesn't require parentheses for the same
equation:

2 3 5 + *

You can compare the results of these equations using the Unix utilities bc
(infix) and dc (postfix):

$ bc <<< '2 * (3 + 5)'
16
$ dc <<< '2 3 5 + * p'
16

The "p" instruction tacked onto the end of the expression for dc just tells it
to print the result.

This week's quiz is to write a script that translates postfix expressions into
the equivalent infix expression. In the simplest form, your script should
function as such:

$ ruby postfix_to_infix.rb '2 3 +'
2 + 3

At minimum, try to support the four basic math operators: +, -, *, and /. Feel
free to add others though. For numbers, remember to accept decimal values.

You can count on the postfix expressions having spaces between each term, if you
like. While dc is content with 2 3+p, you don't have to support it unless you
want to.

For an added bonus, try to keep the parentheses added to infix expressions to
the minimum of what is needed. For example, prefer these results:

$ ruby postfix_to_infix.rb '56 34 213.7 + * 678 -'
56 * (34 + 213.7) - 678
$ ruby postfix_to_infix.rb '1 56 35 + 16 9 - / +'
1 + (56 + 35) / (16 - 9)

to these:

$ ruby postfix_to_infix.rb '56 34 213.7 + * 678 -'
((56 * (34 + 213.7)) - 678)
$ ruby postfix_to_infix.rb '1 56 35 + 16 9 - / +'
(1 + ((56 + 35) / (16 - 9)))

Posting equations and your output is not a spoiler.

The obvious solution to removing all unnecessary parentheses is to remove all
possible permutations of them from a string, eval() them all, and check to
make sure they get the right number .

Just kidding,

Look at my third solution, no idea is too stupid not to be put at work

Cheers
Robert

 

[tho_mica_l]

This 4th version also passes K Bloom's testcases.

Like some other solutions The converter is itself a stack-based
interpreter. Instead of evaluating the expression, the expression gets
transformed.


# The converter is itself a stack-based interpreter. Instead of
# evaluating the expression, the expression gets transformed.
class Quiz148
class << self
def run(args)
iqueue = args.map {|e| e.split(/\s+/)}.flatten
return Quiz148.new(iqueue).process
end

def test(input, expected)
observed = run(input)
ok = observed == expected
if ok
print '.'
else
puts "\n%s != %s\n" % [expected, observed]
end
end
end

def initialize(iqueue)
# Tokenized input
@iqueue = iqueue
# The stack of [operator, element] tuples
@stack = []
# Pre-defined operators
# Fields:
# - precedence
# - arity
# - left associative
# - right associative
# - template
@ops = {
'+' => [10, 2, true, true],
'-' => [10, 2, true, false],
'*' => [5, 2, true, false],
'/' => [5, 2, true, false],
'%' => [5, 2, true, false],
'<<' => [3, 2, true, false],
'^' => [5, 2, false, true],
'**' => [5, 2, false, true],
'sqrt' => [0, 1, true, true, '#{op}(#{vals})'],
'mean' => [0, 2, true, true, '#{op}
(#{vals.join(\', \')})'],
'sum3' => [0, 3, true, true],
'Array' => [0, -1, true, true, '[#{vals.join(\',
\')}]'],
}
@opnames = @ops.keys
end

def process
@iqueue.each do |token|
# Check whether the token is an operator.
if @opnames.include?(token)
op = token
opp, arity, assoc_left, assoc_right, fmt = @ops[op]
case arity
when -1
ap, arity = @stack.pop
when nil
arity = 2
end
case arity
when 1
fmt ||= '#{op}#{vals}'
when 2
fmt ||= '#{vals.join(\' \' + op + \' \')}'
else
fmt ||= '#{op}(#{vals.join(\', \')})'
end
vals = []
# Get the arguments.
arity.times do
if @stack.empty?
puts 'Malformed expression: too few argument'
end
vals.unshift(@stack.pop)
end
idx = 0
# Rewrite the operator's arguments.
vals.map! do |ap, val|
# If opp is <= 0, the operator is a function and
we
# can ignore precedence values. If the value is
an
# atom, ditto.
if ap and opp > 0
app, *rest = @ops[ap]
# If the other operator is a function, it's
considered atomic.
if app > 0
# Put the value in parentheses if the
# operator isn't left or right-
associative
# of if the other operator's precedence
is
# greater than the current operator's one.
if (idx == 0 and !assoc_left) or (idx == 1
and !assoc_right) or app > opp
val = '(%s)' % val
end
end
end
idx += 1
val
end
# Format the values.
@stack << [op, eval("\"#{fmt}\"")]
else
@stack << [nil, eval(token)]
end
end
o, v = @stack.pop
unless @stack.empty?
puts 'Malformed expression: too many argument'
end
v
end
end

if __FILE__ == $0
if ARGV.empty?
Quiz148.test('2 3 +', '2 + 3')
Quiz148.test('56 34 213.7 + * 678 -', '56 * (34 + 213.7) -
678')
Quiz148.test('1 56 35 + 16 9 - / +', '1 + (56 + 35) / (16 -
9)')
Quiz148.test('1 2 + 3 4 + +', '1 + 2 + 3 + 4')
Quiz148.test('1 2 - 3 4 - -', '1 - 2 - (3 - 4)')
Quiz148.test('1 3 4 - -', '1 - (3 - 4)')
Quiz148.test('2 2 ^ 2 ^', '(2 ^ 2) ^ 2')
Quiz148.test('2 2 2 ^ ^', '2 ^ 2 ^ 2')
Quiz148.test('2 sqrt 2 2 ^ ^', 'sqrt(2) ^ 2 ^ 2')
Quiz148.test('2 3 2 2 ^ ^ sqrt 3 + *', '2 * (sqrt(3 ^ 2 ^ 2) +
3)')
Quiz148.test('2 3 mean 2 2 ^ ^', 'mean(2, 3) ^ 2 ^ 2')
Quiz148.test('1 2 3 2 2 ^ ^ mean + 3 *', '(1 + mean(2, 3 ^ 2 ^
2)) * 3')
Quiz148.test('2 3 2 2 ^ ^ mean', 'mean(2, 3 ^ 2 ^ 2)')
Quiz148.test('1 2 2 mean 3 2 ^ sum3', 'sum3(1, mean(2, 2), 3 ^
2)')
Quiz148.test('1 2 2 mean 3 3 Array', '[1, mean(2, 2), 3]')
Quiz148.test('1 2 3 3 Array 4 <<', '[1, 2, 3] << 4')
Quiz148.test('1 2 3 3 Array 4 2 * <<', '[1, 2, 3] << (4 * 2)')
Quiz148.test('1 1 Array 1 2 3 3 Array 4 2 * << -', '[1] - ([1,
2, 3] << (4 * 2))')
Quiz148.test('3 5 * 5 8 * /', '3 * 5 / (5 * 8)')
Quiz148.test('3 5 + 5 8 + -', '3 + 5 - (5 + 8)')
else
puts Quiz148.run(ARGV)
end
end

 

[Eric Mahurin]

Note: parts of this message were removed by the gateway to make it a legal Usenet post.

This doesn't look right.
3 5 * 5 8 * / => 3*5*(5*8) => 0

Thanks Ken,

I obviously didn't test divide. My previously solution has a stupid typo in
Quotient#to_s. Should be:

class Quotient < Product
def to_s
"#{@left}/#{@right}" # had a * operator here before, whoops!
end
...

Here's a couple more tests:

ruby quiz148.rb "3 5 / 5 8 / /" 3 5 / 5 / 8 * => 3/5/5*8 => 0
ruby quiz148.rb "3 5 5 8 / / /"

3 5 5 / 8 * / => 3/(5/5*8) => 0

All the results are zero because it is using ruby's Fixnum#/. The last form
isn't quite optimal because it preferring to minimize divisions over
minimizing groupings/stack-depth. If you use the commented code in
Product#rdiv like this:

def rdiv(other)
# could do this to reduce grouping and stack depth
# but this will increase expensive divisions
@left.rdiv(other).div(@right) # might have more divisions now
#other.div(Group.new(self))
end


you'll get this:

ruby quiz148.rb "3 5 5 8 / / /"

3 5 / 5 * 8 / => 3/5*5/8 => 0

 

[Artem Voroztsov]

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

 

[Eric DUMINIL]

Since Pastie doesn't seem to be so reliable (at least today):

###########################################
# Ruby quiz #148
# http://www.rubyquiz.com/quiz148.html
# Eric Duminil
# 02/12/2007
#
### It removes unnecesary ().
#
# ruby postfix_to_infix.rb '56 34 213.7 + * 678 -'
# 56*(34+213.7)-678
# =13193.2
#
# ruby postfix_to_infix.rb '1 56 35 + 16 9 - / +'
# 1+(56+35)/(16-9)
# =14
#
# ruby postfix_to_infix.rb '1 2+ 4* 5*'
# (1+2)*4*5
# =60
#
### You can omit spaces between operands and operators
#
# ruby postfix_to_infix.rb '1 2+ 4* 5+ 3-'
# (1+2)*4+5-3
# =14
#
# ruby postfix_to_infix.rb '1 2+ 3 4 + +'
# 1+2+3+4
# =10
#
# ruby postfix_to_infix.rb '1 2 - 3 4 - -'
# 1-2-(3-4)
# =0
#
### You can use either ** or ^
### which actually raises troubles while parsing : is "**" == "* *" or
"**"=="^" ?
#
# ruby postfix_to_infix.rb '2 2 ^ 2 ^'
# (2^2)^2
# =16
#
# ruby postfix_to_infix.rb '2 2 ** 2 **'
# (2**2)**2
# =16
#
# ruby postfix_to_infix.rb '2 3 4 ** **'
# 2**3**4
# =2417851639229258349412352
#
# ruby postfix_to_infix.rb '2 3 ** 4 **'
# (2**3)**4
# =4096
#
### It raises when something's missing
#
# ruby postfix_to_infix.rb '1 2+ 4* 5+ 3'
# postfix_to_infix.rb:94:in `convert_to_infix': ArgumentError
#
#
### No UnaryOperation yet


class Operation
attr_reader perator, perands
attr_writer :with_parentheses
def initialize(operator, *operands)
@operator=operator
@operands=operands
@with_parentheses=false
add_parentheses_to_operands_if_necessary!
end

def has_parentheses?
@with_parentheses
end
end

class BinaryOperation<Operation
@@precedence_over={
'+' =>['',''],
#no need to put () before -
'-' =>['','- +'],
'*' => ['- +','- +'],
'/' => ['- +','- + * /'],
'**'=>['- + * / ^ **','- + * /'],
'^'=>['- + * / ^ **','- + * /']
}

def to_s
operands.collect{|operand| if operand.is_a?(Operation) &&
operand.has_parentheses? then
"(#{operand})"
else
operand
end
}.join(operator)
end

private

def add_parentheses_to_operands_if_necessary!
operands.each_with_index{|operand,i|
operators_with_lower_priority=@@precedence_over[operator].split(' ')
operand.with_parentheses=operators_with_lower_priority.any?{|o|
operand.operator == o} if operand.is_a?(BinaryOperation)
}
end
end

class Postfix<String
def split_into_operands_and_operators
self.scan(/([\w\.]+|\*+|\+|\/|\-|\^)/).flatten
end

def to_infix
@to_infix||=convert_to_infix
end

def evaluate
eval(self.to_infix.gsub(/\^/,'**'))
end

private

def convert_to_infix
stack=[]
self.split_into_operands_and_operators.each{|term|
if term=~/^[\w\.]+$/ then
stack<<term
else
right_operand,left_operand=stack.pop,stack.pop
stack<<BinaryOperation.new(term,left_operand,right_operand)
end
}
raise ArgumentError unless stack.size==1
stack.first.to_s
end
end

p=Postfix.new(ARGV[0])
puts p.to_infix
puts "=#{p.evaluate}"

###########################################



see http://pastie.caboo.se/124473 for colored syntaxing

Thanks again,

Eric

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

 

[Artem Voroztsov]

The final task is: having information about operators priorities,
commutativity/non-commutativity, and associativity type (left or
right) construct OP_STRENGTH

Errr .. "commutativity/non-commutativity" ->
"associativity/non-associativity"

Artem

 

[Alpha Chen]

A pretty simplistic regex-based solution that doesn't minimize
parentheses:

#!/usr/bin/env ruby

str = ARGV[0].split(/[^.\d+\-*\/]/).join(' ')

while str !~ /^\(.*\)$/
str.sub!(/([^ ]+) ([^ ]+) ([+\-*\/])/, '(\1\3\2)')
end

puts str.gsub(/([+\-*\/])/, ' \1 ').sub(/^\((.*)\)$/, '\1')

 

[Adam Shelly]

Even with that cleanup, it doesn't seem to work:

esau:/tmp$ ruby asrq148.rb '2 3 - 5 +'
+
esau:/tmp$ ruby asrq148.rb '2 3 -'
-

I think you only changed 'Token' to Term, and missed the 'tok'=>'term' sub.
That's the only way I get what you show.

Anyway, Here's an updated version wihch handles the associativity test cases.

#postfix to infix
# ruby quix #148
# Adam Shelly
# v2
# Converts postfix to infix notation
# uses ruby's operators & precedence rules

$Operators = {
'&&'=>'0 ', '||'=>'0 ',
'=='=>'1 ', '==='=>'1 ', '<=>'=>'1 ',
'<='=>'2 ', '>='=>'2 ', '<' =>'2 ', '>'=>'2 ',
'^' =>'3 ', '|' =>'3 ',
'&' =>'4 ',
'<<'=>'5L', '>>'=>'5L',
'+' =>'6 ', '-' =>'6L',
'*' =>'7 ', '/' =>'7L', '%'=> '7L',
'**'=>'8R',
:term=>'10 '
}

class Term
attr_reader recedence, :dir
def initialize str, groupPrec=nil
@s = str
@precedence = $Operators[str]||groupPrec||$Operators[:term]
@dir = @precedence[-1].chr
@precedence = @precedence.to_i
end
def isOp
@precedence != $Operators[:term].to_i
end
def parenthesize
@s="(#{@s})"
end
def to_s
@s
end
end

class Infix
def initialize rpn
stack=[]
rpn.split.each do |t|
term = Term.new(t)
if term.isOp
rval = stack.pop
lval = stack.pop
raise "Empty Stack" unless lval && rval
lval.parenthesize if lval.precedence < term.precedence or
term.dir=='R'&& lval.precedence == term.precedence
rval.parenthesize if rval.precedence < term.precedence or
term.dir=='L'&& rval.precedence == term.precedence
phrase = "#{lval} #{term} #{rval}"
term = Term.new(phrase,term.precedence)
#p term
end
stack.push term
end
@expr = stack.pop
raise "Extra terms" unless stack.size==0
end
def to_s
@expr.to_s
end
end

def test
puts Infix.new('2 3 +').to_s == '2 + 3'
puts Infix.new('56 34 213.7 + * 678 -').to_s == '56 * (34 + 213.7) - 678'
puts Infix.new('1 56 35 + 16 9 - / +').to_s == '1 + (56 + 35) / (16 - 9)'
puts Infix.new('1 2 + 3 4 + +').to_s == '1 + 2 + 3 + 4'
puts Infix.new('1 2 - 3 4 - -') .to_s == '1 - 2 - (3 - 4)'
puts Infix.new('2 2 ** 2 **').to_s == '(2 ** 2) ** 2'
puts Infix.new('2 2 2 ** **').to_s == '2 ** 2 ** 2'
puts Infix.new('1 2 3 4 5 + + + +').to_s == '1 + 2 + 3 + 4 + 5'
puts Infix.new('1 2 3 4 5 / / - -').to_s == '1 - (2 - 3 / (4 / 5))'
puts Infix.new('3 5 * 5 8 * /').to_s == '3 * 5 / (5 * 8)'
puts Infix.new('3 5 + 5 8 + -').to_s == '3 + 5 - (5 + 8)'
puts Infix.new('a b == c 1 + 2 < &&').to_s == 'a == b && c + 1 < 2'
puts Infix.new('1 2 << 4 <<').to_s == '1 << 2 << 4'
puts Infix.new('1 2 4 << <<').to_s == '1 << (2 << 4)'
end

if __FILE__ == $0
if ARGV.empty?
test
else
puts Infix.new(ARGV.join(' ')).to_s
end
end

 

[Sharon Phillips]

Hi,

Didn't have much time for this, so here's a partial solution.
What I haven't done is work on ARGV and the bracket removal code is
pretty basic
produces
1+(56+35)/(16-9) - good
1+(2+(3+4)) - needs work...

Cheers,
Dave


eqn= %w[1 56 35 + 16 9 - / +]
ops= %w[+ - * /]

stack= []

eqn.each do |e|
if ops.include? e
b= stack.pop || 0
a= stack.pop || 0
if stack.empty?
stack= [a, e.to_sym, b]
else
stack << [a, e.to_sym, b]
end
else
stack << e
end
end

def disp item, depth
str=''
if item.class== Array
inner= item.inject('') {|sum, e| sum << (disp e, depth+1)}
inner= "(#{inner})" unless ([:*, :/].include? item[1]) || depth==0
str << inner
else
str << item.to_s
end
str
end

puts disp(stack,0)