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:
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.
I had this as an assignment for a class once, in Java, so I'll sit
this one out. Fun quiz!

http://rubysmalltalk.blogspot.com/

All truth passes through three stages. First, it is ridiculed. Second,
it is violently opposed. Third, it is accepted as being selfevident.
Schopenhauer (attr.)
> I had this as an assignment for a class once, in Java, so I'll sit
> this one out. Fun quiz!
Well, doubtless in java you solved it in a way that demonstrated your
use of certain basic data structures that you'd just learned about.
There are at least two completely different algorithms to use in
solving this in a conventional manner, and I've just solved it in a
third, completely unconventional ("evil") manner. So solve it in a
manner different from what you did in class.
(The nospoiler rule makes phrasing this reply difficult)
Also, being strict about the minimal parentheses rule makes things a
bit interesting:
'1 2 + 3 4 + +' should become '1 + 2 + 3 + 4'
But:
'1 2  3 4  ' should become '1  2  (3  4)'
Likewise for multiplication and division.
Also, you could add exponentiation, but if you do remember that infix
exponentiation associates to the right, not the left, so:
'2 2 ^ 2 ^' should become '(2 ^ 2) ^ 2'
But:
'2 2 2 ^ ^' should become '2 ^ 2 ^ 2'
So really, there's lots more to it than whatever you did it in that
java class.

s=%q( Daniel Martin  mar...@snowplow.org
puts "s=%q(#{s})",s.to_a.last )
puts "s=%q(#{s})",s.to_a.last
Or '1  2  3 + 4' (yikes!) :^0
Todd
Well one feature of the Ruby Quiz is that our Quiz Master generally
allows submitters quite a bit of flexibility in reinterpreting the
problem. To me, however, that form seems outside the problem
description, as you're a) applying the distributive property, and b)
ending up with a different set of operators than what you started with
(from 3 minuses to 2 minuses and 1 plus).
And once you start down the road '4 2 3 + *' could become '4 * (2 +
3)', '8 + 12', or even '20'.
Eric
====
Are you interested in onsite Ruby training that's been highly
reviewed by former students? http://LearnRuby.com
Of course. It's not a quiz about simplification. I just thought it
was funny (a stretch on the minimizing of parentheses). It keeps the
same digits, though; only changes the operators. It's quite clear
that the only symbols  digits or operators  we're allowed to add
or remove are ) and (.
Cheers,
Todd
Robert
###############################
# Read postfix from args or stdin
# Print an infix solution *without* paranthesis
postfix = ARGV.empty? ? $stdin.read.split : ARGV
postfix = postfix.map{  ele  Integer( ele ) rescue ele }
stack = []
postfix.each do  ele 
case ele
when Integer
stack << ele
else
rhs = stack.pop
stack[ 1 ] = stack[ 1 ].send( ele, rhs )
end
end
puts stack.first.to_s
#########################################################"
# Read postfix from args or stdin
# Print an infix solution with *many* paranthesis
postfix = ARGV.empty? ? $stdin.read.split : ARGV
postfix = postfix.map{  ele  Integer( ele ) rescue ele }
stack = []
postfix.each do  ele 
case ele
when Integer
stack << ele
else
rhs = stack.pop
stack[ 1 ] = "( #{stack[ 1 ]} ) #{ele} ( #{rhs} )"
end
end
puts stack.first
##################################################
# Read postfix from args or stdin
# Print an infix solution with *some* paranthesis
# the stupid ( and expensive ) way.
class Expression
Combinations = [
["", "", "", ""],
["( ", " )", "", ""],
["", "", "( ", " )"],
["( ", " )", "( ", " )"]
]
attr_reader :text, :value
def initialize text
@value = Integer( text )
@text = text
end
def apply op, rhs
new_text = "#@text #{op} #{rhs.text}"
@value = @value.send( op, rhs.value )
Combinations.each do  parens 
txt = ["", @text, " #{op} ", rhs.text ].
zip( parens ).flatten.join
if eval( txt ) == @value then
return @text = txt
end
end
raise RuntimeError, "ooops"
end
end
postfix = ARGV.empty? ? $stdin.read.split : ARGV
postfix = postfix.map{  ele  Expression.new( ele ) rescue ele }
stack = []
postfix.each do  ele 
case ele
when Expression
stack << ele
else
rhs = stack.pop
stack.last.apply ele, rhs
end
end
puts stack.first.text
#############################################
# Read postfix from args or stdin
# Print an infix solution with *some* paranthesis
# (the clever way?)
class Expression
Priorities = {
"**" => 2,
"*" => 1, "/" => 1, "%" => 1,
"+" => 0, "" => 0,
nil => 3
}
Commutative = %w[ * + ]
attr_reader :text, :top_op
def initialize text
@top_op = nil
@text = text
end
def apply op, rhs
@text = parented_text( op ) +
" #{op} " << rhs.parented_text( op, false )
@top_op = op
end
def comm? op
Commutative.include? op
end
def parented_text op, is_lhs=true
my_prio = Priorities[ @top_op ]
op_prio = Priorities[ op ]
return @text if op_prio < my_prio
return "( #@text )" if op_prio > my_prio
return @text if comm?( op )  is_lhs
"( #@text )"
end
end
postfix = ARGV.empty? ? $stdin.read.split : ARGV
postfix = postfix.map{  ele 
Expression::Priorities[ ele ] ? ele : Expression.new( ele )
}
stack = []
postfix.each do  ele 
case ele
when Expression
stack << ele
else
rhs = stack.pop
stack[ 1 ].apply ele, rhs
end
end
puts stack.first.text
http://pastie.caboo.se/124288
I'm pretty it removes every unnecessary (), at least for  + ** ^ /.
Thanks for the quiz!
if arr.length == err.length
arr.each_with_index do x,y
the_stack << x unless ops.include?(x)
if ops.include?(x) && the_stack.length > 1
b = the_stack.pop
a = the_stack.pop
the_stack << "(#{a} #{x} #{b})" if (x == "+"  x == "") && (y <
(arr.length  1))
the_stack << "#{a} #{x} #{b}" if x == "*"  x == "/"  y ==
(arr.length  1)
end
end
puts the_stack[0]
end
# Harry

A Look into Japanese Ruby List in English
http://www.kakueki.com/ruby/list.html
Since I recently wrote a small RPN calculator in ruby
(http://www.vim.org/scripts/script.php?script_id=2040), I found this
idea interesting.
Here is my take on this. It provides some kind of simplicistic
pattern
matcher and should be extensible. The assumption is made that the
input
consists of numeric data and predefined operators. No error checking
is
done.
Regards,
Thomas.
class Quiz148
class << self
def run(args)
iqueue = args.map {e e.split(/\s+/)}.flatten
return Quiz148.new(iqueue).process
end
end
def initialize(iqueue)
@iqueue = iqueue
@depth = 0
@stack = []
@ops = {
'+' => [10],
'' => [10, [String, String, false, true]],
'*' => [5],
'/' => [5],
'^' => [5, [String, Numeric, true, false]],
}
@opnames = @ops.keys
end
def get_elt(op, idx=1, other_value=nil)
val = @stack.delete_at(idx)
case val
when Array
eop, val = val
else
eop = nil
end
if op and eop
opp, *opatterns = @ops[op]
eopp, *epatterns = @ops[eop]
if eopp > opp
return '(%s)' % val
end
end
return val
end
def process
@iqueue.each do token
if @opnames.include?(token)
val1 = get_elt(token, 2)
val2 = get_elt(token, 1)
@ops[token][1..1].each do p1, p2, e1, e2
if val1.kind_of?(p1) and val2.kind_of?(p2)
val1 = '(%s)' % val1 if e1
val2 = '(%s)' % val2 if e2
break
end
end
@stack << [token, '%s %s %s' % [val1, token, val2]]
else
@stack << eval(token)
end
end
# The stack should include only one element here. A check
would
# be necessary.
get_elt(nil)
end
end
if __FILE__ == $0
if ARGV.empty?
puts Quiz148.run('2 3 +') == '2 + 3'
puts Quiz148.run('56 34 213.7 + * 678 ') == '56 * (34 +
213.7)  678'
puts Quiz148.run('1 56 35 + 16 9  / +') == '1 + (56 + 35) /
(16  9)'
puts Quiz148.run('1 2 + 3 4 + +') == '1 + 2 + 3 + 4'
puts Quiz148.run('1 2  3 4  ') == '1  2  (3  4)'
puts Quiz148.run('2 2 ^ 2 ^') == '(2 ^ 2) ^ 2'
puts Quiz148.run('2 2 2 ^ ^') == '2 ^ 2 ^ 2'
else
puts Quiz148.run(ARGV)
end
end
> 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.
> 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)))
>
Hi,
Fortunately, this week I had some time to check the Ruby quiz, and
even to code something. Unfortunately I only had about 10 minutes, so
I only solved the basic problem:
stack = []
expr = ARGV.join(" ")
expr.split(/ /).each do x
case x
when *%w{+ *  /}
op2 = stack.pop
op1 = stack.pop
stack.push "(#{op1} #{x} #{op2})"
else
stack.push x
end
end
puts stack.pop
This is how it works with the examples. It doesn't remove a single
parenthesis :(
C:\Jesus>ruby quiz148.rb 2 3 +
(2 + 3)
C:\Jesus>ruby quiz148.rb "56 34 213.7 + * 678 "
((56 * (34 + 213.7))  678)
C:\Jesus>ruby quiz148.rb 1 56 35 + 16 9  / +
(1 + ((56 + 35) / (16  9)))
I'll try to find some time to implement some parenthesis
simplification, although I doubt I will succeed...
Thanks,
Jesus.
def convert array
cur=array.pop
case cur
when Numeric: return cur
when String:
rhs=convert(array)
lhs=convert(array)
return "(#{lhs} #{cur} #{rhs})"
end
end
equation=ARGV[0].split.collect{x Integer(x) rescue Float(x) rescue x}
puts convert(equation)

Ken (Chanoch) Bloom. PhD candidate. Linguistic Cognition Laboratory.
Department of Computer Science. Illinois Institute of Technology.
http://www.iit.edu/~kbloom1/
class Quiz148
class << self
def run(args)
iqueue = args.map {e e.split(/\s+/)}.flatten
return Quiz148.new(iqueue).process
end
end
def initialize(iqueue)
@iqueue = iqueue
@depth = 0
@stack = []
@ops = {
'+' => [10],
'' => [10, nil, [Object, String, false,
true]],
'*' => [5],
'/' => [5],
'%' => [5],
'^' => [5, nil, [String, Numeric, true,
false]],
'**' => [5, nil, [String, Numeric, true,
false]],
'sqrt' => [0, nil, [Object, true]],
'binom' => [5, '#{op}(#{val1}, #{val2})'],
}
@opnames = @ops.keys
end
def get_elt(op, idx=1)
val = @stack.delete_at(idx)
case val
when Array
eop, val = val
else
eop = nil
end
if op and eop
opp, *opatterns = @ops[op]
eopp, *epatterns = @ops[eop]
if opp != 0 and eopp > opp
return '(%s)' % val
end
end
return val
end
def process
@iqueue.each do token
if @opnames.include?(token)
op = token
opp, fmt, *patterns = @ops[op]
if opp == 0
fmt = '#{op}#{val1}'
val1 = get_elt(token, 1)
patterns.each do p1, e1
if val1.kind_of?(p1)
val1 = '(%s)' % val1 if e1
break
end
end
@stack << [token, eval("\"#{fmt}\"")]
else
fmt = '#{val1} #{op} #{val2}'
val1 = get_elt(token, 2)
val2 = get_elt(token, 1)
patterns.each do p1, p2, e1, e2
if val1.kind_of?(p1) and val2.kind_of?(p2)
val1 = '(%s)' % val1 if e1
val2 = '(%s)' % val2 if e2
break
end
end
@stack << [token, eval("\"#{fmt}\"")]
end
else
@stack << eval(token)
end
end
# The stack should include only one element here. A check
would
# be necessary.
get_elt(nil)
end
end
if __FILE__ == $0
if ARGV.empty?
puts Quiz148.run('2 3 +') == '2 + 3'
puts Quiz148.run('56 34 213.7 + * 678 ') == '56 * (34 +
213.7)  678'
puts Quiz148.run('1 56 35 + 16 9  / +') == '1 + (56 +
35) / (16  9)'
puts Quiz148.run('1 2 + 3 4 + +') == '1 + 2 + 3 +
4'
puts Quiz148.run('1 2  3 4  ') == '1  2  (3 
4)'
puts Quiz148.run('1 3 4  ') == '1  (3  4)'
puts Quiz148.run('2 2 ^ 2 ^') == '(2 ^ 2) ^ 2'
puts Quiz148.run('2 2 2 ^ ^') == '2 ^ 2 ^ 2'
puts Quiz148.run('2 sqrt 2 2 ^ ^') == 'sqrt(2) ^ 2
^ 2'
puts Quiz148.run('2 3 2 2 ^ ^ sqrt 3 + *') == '2 * (sqrt(3
^ 2 ^ 2) + 3)'
puts Quiz148.run('2 3 binom 2 2 ^ ^') == 'binom(2, 3)
^ 2 ^ 2'
puts Quiz148.run('1 2 3 2 2 ^ ^ binom + 3 *') == '(1 +
binom(2, 3 ^ 2 ^ 2)) * 3'
puts Quiz148.run('2 3 2 2 ^ ^ binom') == 'binom(2, 3 ^
2 ^ 2)'
class TreeNode
attr_accessor :el,:left,:right
def initialize(el,left,right)
@el,@left,@right=el,left,right
end
def TreeNode.from_postfix(exp_arr)
stack = []
exp_arr.each do exp_str
if PREC.keys.include? exp_str.to_sym
op2,op1 = stack.pop,stack.pop
stack.push(TreeNode.new(exp_str.to_sym,op1,op2))
else
stack.push(exp_str.to_f)
end
end
stack.first
end
def to_minparen_infix
l,r = [left,right].map{oo.to_minparen_infix}
l = "(#{l})" if left.respond_to?(:el) and (PREC[left.el]<PREC[self.el] or
(self.el==left.el and not LEFT_ASSOCS[left.el]))
r= "(#{r})" if right.respond_to?(:el) and (PREC[right.el]<PREC[self.el] or
(self.el==right.el and not RIGHT_ASSOCS[right.el]))
l+" #{self.el} "+r
end
end
class Float
def to_minparen_infix
if self%1==0
to_i.to_s
else
to_s
end
end
end
puts TreeNode.from_postfix(ARGV.first.split(/ /)).to_minparen_infix
3. Enjoy!
========================================
$ 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.
____________________________________________________________________________________
Get easy, oneclick access to your favorites.
Make Yahoo! your homepage.
http://www.yahoo.com/r/hs
Here's my solution. I know it's pretty long but I'm still learning...
BIG thanks for the quiz!
#!/usr/bin/env ruby
# Solution to Ruby Quiz #148 (see http://www.rubyquiz.com/quiz148.html)
# by Pawel Radecki (pawel.j...@gmail.com).
# Note1: There may be couple of different and correct postfix to infix
# transformations but this program only gives one and ignores others.
#
# Example:
# postfix: 1 2 + 4 * 5 + 3 
# infix: (1 + 2) * 4 + 5  3
# infix: (1+2)*4+53
# infix: 5 + (1 + 2) * 4  3
# infix: 5 + 4 * (1 + 2)  3
# ... (there are more)
# Note2: Unary operators not supported!
# Note3: I don't know why ^ in input argument doesn't work, anybody
knows...?
require 'logger'
$LOG = Logger.new($stderr)
#logging
#$LOG.level = Logger::DEBUG #DEBUG
$LOG.level = Logger::ERROR #PRODUCTION
class PostfixEquation < String
private
@@OPERATOR_PRIORITIES = {
'V' => 2,
'**' => 2,
'*' => 2,
'/' => 2,
'+' => 3,
'' => 3
}
def normalize_expression (expression)
a = expression.split
$LOG.debug("array: #{a}")
$LOG.debug("#{a[0]} #{a[2]} #{a[1]}")
@operator_stack.push(a[2])
$LOG.debug("@operator_stack #{@operator_stack}")
s = "#{a[0]} #{a[2]} #{a[1]}"
if @operator_stack.length>1 &&
@@OPERATOR_PRIORITIES[@operator_stack[2]]<@@OPERATOR_PRIORITIES[a[2]]
s = "(#{s})"
end
if @two_branches
@operator_stack.pop
end
#hack to resolve situation with two complex expressions forming
another
if a[0] =~/[az]+/ && a[1] =~/[az]+/
@two_branches = true
else
@two_branches = false
end
return s
end
public
def initialize(equation)
@string = super.to_str
@label = "a"
@expressions = {}
@operator_stack = []
@two_branches = false
end
def to_infix
$LOG.debug("string: #{@string}")
while (true)
$LOG.debug("string: #{@string}")
$LOG.debug("string lenth: #{@string.length}")
#look for "(number or letter(s)) (number or letter(s))
operator" pattern
#where number is chain of any digit and . (dot) characters
#letter(s) is one or more letters
#and operator is one of following characters: +  * / p r
@string =~
/([09\.]+[az]+)\s([09\.]+[az]+)\s((\*\*)(V)\+\*\/)/
$LOG.debug("pattern match: #{$`}<<#{$&}>>#{$'}")
# if the the expression is not valid
if ($&==nil  $&=="") && @string.length>1
$LOG.error("Stack is not empty!")
raise Exception.new("Stack is not empty!")
end
@expressions[@label] = $&
@string = "#{$`}#{@label}#{$'}"
$LOG.debug("string: #{@string}")
$LOG.debug("string lenth: #{@string.length}")
#if it's the last match
if $`=="" && $'=="" && @string.length==1
break
end
@label.succ!
$LOG.debug("label: #{@label}")
$LOG.debug("")
end
while (!@expressions.empty?)
@string.sub!(/([az])/) {
letter = $1.dup
s = String.new(normalize_expression(@expressions[letter]))
@expressions.delete(letter)
s
}
$LOG.debug("string: #{@string}")
$LOG.debug("")
end
return @string
end
end
USAGE = <<ENDUSAGE
Usage:
postfix_to_infinix.rb 'mathematical equation'
Valid binary operators: +  * / V **
where
V is a root operator, ex.: 5 V 1 means 5th root of a number 1
** is a power operator, ex.: 2 ** 3 means power with base 2 and
exponent 3
(Unary operators not supported!)
Example:
postfix_to_infinix.rb '56 34 213.7 + ** 678 '
ENDUSAGE
if ARGV.length!=1
puts USAGE
exit
end
e = PostfixEquation.new(ARGV[0])
begin
puts e.to_infix
rescue StandardError => err
puts err
end

Pawel Radecki
m: +48 695 346476
e: pawel.j...@gmail.com
w: http://radeckimarch.blogspot.com/
Hello,
Here is my solution. It minimizes the use of parentheses, and can easily be
extended to support other operators in addition to +, , * / as long as they
are evaluated from lefttoright:
# This class represents a single token on the infix stack.
# A token may be a single operator / number from the postfix expr, or a
portion of the infix expr being built.
class Token
# Accepts a token string and optionally the last operator added
def initialize(tok, last_op = nil)
@tok, @last_op = tok, last_op
end
# Determines if the current token is an operator
def is_op?
case @tok
when "+", "", "*", "/"
return true
else
return false
end
end
# Defines the precedence of operators
def precedence(op)
case op
when "*", "/"
return 5
when "+", ""
return 6
else
return nil
end
end
# Returns the token with parentheses added if they are needed for the
given op
def pack(op)
return "(#{tok})" if last_op != nil and (precedence(op) <
precedence(last_op))
return tok
end
attr_reader :tok, :last_op
end
# Module of Postfix ==> Infix conversion functions
module PostfixToInfix
# Main convertion function
def PostfixToInfix.translate(postfix)
stack, toks = [], postfix.split(" ").reverse
for tok in toks
stack << Token.new(tok)
process_stack(stack)
end
process_stack(stack) while stack.size > 1 # Finish stack processing
stack[0].tok
end
# Process the current postfix stack, converting to infix if there is
enough info
def PostfixToInfix.process_stack(stack)
while stack.size > 2 and not stack[1].is_op? and not stack[2].is_op?
eq = []
3.times{ eq << stack.pop }
op = eq[2].tok
tok = "#{eq[0].pack(op)} #{op} #{eq[1].pack(op)}"
stack << Token.new(tok, op)
end
end
end
Full Program: http://pastie.caboo.se/124320
Test Cases: http://pastie.caboo.se/124321
Thanks,
Justin
On Nov 30, 2007 8:28 AM, Ruby Quiz <ja...@grayproductions.net> wrote:
#!/usr/bin/ruby w
argv = Array.new
if ARGV.empty?
puts "#{$0} <Postfix equation>"
else
ARGV.each do a
if ['+', '', '/', '*'].include?(a)
last = argv.pop
first = argv.pop
argv << "(#{first} #{a} #{last})"
else
argv << a
end
end
puts argv
end
I will try and mod the code to remove some parenthesis.
Regards,
Lee

Posted via http://www.rubyforum.com/.
Thomas.
class Quiz148
class << self
def run(args)
iqueue = args.map {e e.split(/\s+/)}.flatten
return Quiz148.new(iqueue).process
end
end
def initialize(iqueue)
@iqueue = iqueue
@depth = 0
@stack = []
@ops = {
'+' => [10],
'' => [10, 2, nil, [[Object, nil], [String,
'(%s)']]],
'*' => [5],
'/' => [5],
'%' => [5],
'<<' => [3],
'^' => [5, 2, nil, [[String, '(%s)'],
[Numeric, nil]]],
'**' => [5, 2, nil, [[String, '(%s)'],
[Numeric, nil]]],
'sqrt' => [0, 1, '#{op}(#{vals})'],
'binom' => [0, 2, '#{op}(#{vals.join(\', \')})'],
'sum3' => [0, 3],
'Array' => [0, 1, '[#{vals.join(\', \')}]'],
}
@opnames = @ops.keys
end
def process
@iqueue.each do token
if @opnames.include?(token)
op = token
opp, arity, fmt, *patterns = @ops[op]
case arity
when 1
aop, 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 = (1..arity).inject([]) {a, i a <<
@stack.pop}.reverse
idx = 0
vals.map! do aop, val
if aop
aopp, *aopatterns = @ops[aop]
if opp > 0 and aopp > opp
val = '(%s)' % val
end
end
patterns.each do pattern
p, e = pattern[idx]
if (aop.nil? or aopp > 0) and val.kind_of?(p)
if e
val = e % val
end
break
end
end
idx += 1
val
end
@stack << [op, eval("\"#{fmt}\"")]
else
@stack << [nil, eval(token)]
end
end
# The stack should include only one element here. A check
would
# be necessary.
o, v = @stack.pop
v
end
end
puts Quiz148.run('1 2 2 binom 3 2 ^ sum3') == 'sum3(1,
binom(2, 2), 3 ^ 2)'
puts Quiz148.run('1 2 2 binom 3 3 Array') == '[1, binom(2,
2), 3]'
puts Quiz148.run('1 2 3 3 Array 4 <<') == '[1, 2, 3] <<
4'
puts Quiz148.run('1 2 3 3 Array 4 2 * <<') == '[1, 2, 3] <<
(4 * 2)'
> Hello everybody,
>
> Here's my solution. I know it's pretty long but I'm still learning...
> BIG thanks for the quiz!
>
>
>
> #!/usr/bin/env ruby
>
> # Solution to Ruby Quiz #148 (see http://www.rubyquiz.com/quiz148.html)
> # by Pawel Radecki (pawel.j...@gmail.com).
>
> # Note1: There may be couple of different and correct postfix to infix #
> transformations but this program only gives one and ignores others. #
> # Example:
> # postfix: 1 2 + 4 * 5 + 3 
> # infix: (1 + 2) * 4 + 5  3
> # infix: (1+2)*4+53
> # infix: 5 + (1 + 2) * 4  3
> # infix: 5 + 4 * (1 + 2)  3
> # ... (there are more)
>
> # Note2: Unary operators not supported!
>
> # Note3: I don't know why ^ in input argument doesn't work, anybody
> knows...?
It appears to be this regex over here. You need to escape the ^ if you
want to use it in a regex, because ^ signals the beginning of a line in a
regex.
> @string =~
> /([09\.]+[az]+)\s([09\.]+[az]+)\s((\*\*)(V)\+\*\/)/
Ken
> This week's quiz is to write a script that translates postfix
> expressions into the equivalent infix expression.
#! /usr/bin/env ruby
#
# Accepts RPN using the basic four operations +  / *, as well as
# ^ to denote exponentiation, and outputs infix notation with the
# minimum number of parentheses. Note that infix exponentiation
# associates to the right, so 2 ^ 2 ^ 2 == 2 ^ (2 ^ 2)
instr = ARGV.join(' ');
s = instr.dup
s.gsub!(/(\d+(\.\d*)?)/, '<n:\1>')
s.gsub!(/\s/,'')
# Data structures? We don't need no stinkin' data structures.
# Postfix expression to infix expression via regular expressions.
while s =~ /<.*</ do
f = false
f = s.gsub!(%r{<.:([^>]*)><.:([^>]*)>\+}, '<+:\1 + \2>')
f = s.gsub!(%r{<.:([^>]*)><[+]:([^>]*)>}, '<:\1  (\2)>')
f = s.gsub!(%r{<.:([^>]*)><[^+]:([^>]*)>}, '<:\1  \2>')
f = s.gsub!(%r{<[+]:([^>]*)><[+]:([^>]*)>\*}, '<*:(\1) * (\2)>')
f = s.gsub!(%r{<[+]:([^>]*)><[^+]:([^>]*)>\*}, '<*:(\1) * \2>')
f = s.gsub!(%r{<[^+]:([^>]*)><[+]:([^>]*)>\*}, '<*:\1 * (\2)>')
f = s.gsub!(%r{<[^+]:([^>]*)><[^+]:([^>]*)>\*}, '<*:\1 * \2>')
f = s.gsub!(%r{<[+]:([^>]*)><[*/+]:([^>]*)>/}, '</:(\1) / (\2)>')
f = s.gsub!(%r{<[^+]:([^>]*)><[*/+]:([^>]*)>/}, '</:\1 / (\2)>')
f = s.gsub!(%r{<[+]:([^>]*)><[^*/+]:([^>]*)>/}, '</:(\1) / \2>')
f = s.gsub!(%r{<[^+]:([^>]*)><[^*/+]:([^>]*)>/}, '</:\1 / \2>')
f = s.gsub!(%r{<[^n]:([^>]*)><[^n^]:([^>]*)>\^}, '<^:(\1) ^ (\2)>')
f = s.gsub!(%r{<[^n]:([^>]*)><[n^]:([^>]*)>\^}, '<^:(\1) ^ \2>')
f = s.gsub!(%r{<n:([^>]*)><[^n^]:([^>]*)>\^}, '<^:\1 ^ (\2)>')
f = s.gsub!(%r{<n:([^>]*)><[n^]:([^>]*)>\^}, '<^:\1 ^ \2>')
unless f
raise "Malformed RPN string: '#{instr}' (s is #{s})"
end
end
s.gsub!(/<.:(.*)>/, '\1')
puts s
__END__
Here's mine.
It removes parenthesis, and handles all the binary operators in Ruby
(unless I missed some).
You can use a different set of operators and precedence rules by
changing the $Operators hash.
#postfix to infix
# ruby quix #148
# Adam Shelly
#
# Converts postfix to infix notation
# uses ruby's operators & precedence rules
$Operators = {
'&&'=>0, ''=>0,
'=='=>1, '==='=>1, '<=>'=>1,
'<='=>2, '>='=>2, '<' =>2, '>'=>2,
'^' =>3, '' =>3,
'&' =>4,
'<<'=>5, '>>'=>5,
'+' =>6, '' =>6,
'*' =>7, '/' =>7, '%'=> 7,
'**'=>8,
:term=>10
}
class Term
attr_reader :precedence
def initialize str, groupPrec=nil
@s = str
@precedence = $Operators[str]groupPrec$Operators[:term]
end
def isOp
@precedence != $Operators[:term]
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
lval = stack.pop
rval = stack.pop
raise "Empty Stack" unless lval && rval
lval.parenthesize if lval.precedence < term.precedence
rval.parenthesize if rval.precedence < term.precedence
phrase = "#{rval} #{term} #{lval}"
tok = Token.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
end
end
if __FILE__ == $0
puts Infix.new(ARGV.join(' ')).to_s
end
Adam
I should know better than to try to cleanup my code, and then submit
it without running it first.
This line:
> tok = Token.new(phrase,term.precedence)
should read
term = Term.new(phrase, term.precedence)
Adam
#!/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

Alex Shulgin
> I should know better than to try to cleanup my code, and then submit
> it without running it first.
>
> This line:
>> tok = Token.new(phrase,term.precedence)
> 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 '

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! :)

Alex
Here is my solution:
>
a=ARGV[0].split
pri='+*/'
prs=[]
i=0
while a.length>1 do
if pr=pri.index(op=a[i])
raise if i<2
a[i2]='('+a[i2]+')' if pr>>1 > prs[i2]
a[i1]='('+a[i1]+')' if pr>>1 > prs[i1]  (pr>>1 == prs[i1] &&
pr&1==1)
a[i2,3]=a[i2]+op+a[i1]
prs[i=2]=pr>>1
else
prs[i]=4
end
i+=1
end rescue a[0]="invalid expression"
puts a[0]
>
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 leftstrength (the one to the right) and another with rightstrength
# (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..N1).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 parsetree (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 (20070313 patchlevel 0) [i386mswin32])
For N = 10000, 20000 and input = '0 ' + (1..N1).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?
> 2. We discovered problem with Array#flatten. Is it a known issue?
> (I use ruby 1.8.6 (20070313 patchlevel 0) [i386mswin32])
>
> For N = 10000, 20000 and input = '0 ' + (1..N1).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 selfmade '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 (20070313 patchlevel 0) [i386mswin32]
Can anybody check it for ruby 1.9.1?
#!/usr/bin/ruby
N = 10000
inputs = []
inputs << '0 ' + (1..N1).to_a.join('  ') + ' '
inputs << (1..N).to_a.join(' ') + (" +" * (N1))
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('selfmade 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)
selfmade flatten 0.032000 0.000000 0.032000 ( 0.031000)
true
user system total real
original flatten 5.063000 0.000000 5.063000 ( 5.079000)
selfmade flatten 0.031000 0.000000 0.031000 ( 0.031000)
true
On Nov 30, 2007 7:28 AM, Ruby Quiz <ja...@grayproductions.net> wrote:
> 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 postfix stack depth) by using some
associativity
* evaluates the result
* gives stackreduced postfix form
The basic idea of the solution is to have an object for each expression
(possibly with subexpressions 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}")
}