Postfix to Infix (#148)

The three rules of Ruby Q.:

  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 Q. by submitting ideas as often as you can:

http://www.rubyquiz.com/

  1. Enjoy!

Suggestion: A [QUIZ] in the subject of emails about the problem helps
everyone
on Ruby T. 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.

On Nov 30, 2007 8:28 AM, Ruby Q. [email protected] wrote:

    16
    $ ruby postfix_to_infix.rb '2 3 +'

the minimum of what is needed. For example, prefer these results:
$ 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!

On Nov 30, 2007 4:24 PM, Christian von Kleist [email protected]
wrote:

function as such:

    $ 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!
Why? I’d rather say that it is quite challange to provide a solution
in Ruby that is not just a rewrite of your Java solution.
I do not think that there are an “ethic” considerations ;).
Cheers
Robert

http://ruby-smalltalk.blogspot.com/


All truth passes through three stages. First, it is ridiculed. Second,
it is violently opposed. Third, it is accepted as being self-evident.
Schopenhauer (attr.)

“Christian von Kleist” [email protected] writes:

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 no-spoiler 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.

On Dec 1, 2007 4:18 PM, Daniel M. [email protected] wrote:

“Christian von Kleist” [email protected] writes:
But:

‘1 2 - 3 4 - -’ should become ‘1 - 2 - (3 - 4)’

Or ‘1 - 2 - 3 + 4’ (yikes!) :^0

Todd

On Dec 1, 5:27 pm, Todd B. [email protected] wrote:

On Dec 1, 2007 4:18 PM, Daniel M. [email protected] wrote:

“Christian von Kleist” [email protected] writes:
But:

‘1 2 - 3 4 - -’ should become ‘1 - 2 - (3 - 4)’

Or ‘1 - 2 - 3 + 4’ (yikes!) :^0

Well one feature of the Ruby Q. 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 on-site Ruby training that’s been highly
reviewed by former students? http://LearnRuby.com

On Dec 1, 2007 5:05 PM, Eric I. [email protected] wrote:

Well one feature of the Ruby Q. 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

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

Here is my solution:

http://pastie.caboo.se/124288
I’m pretty it removes every unnecessary (), at least for - + ** ^ /.

Thanks for the quiz!

Here goes my solution for this Quiz, I am confident that solutions 1
and 2 are correct, well 3 too, for 4 that is less sure ;).
Nice to have a quiz which can be solved in less time again.

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

Here is my solution.

It solves the minimum requirements with minimal error checking.

Removes some parentheses.

#str = “1 56 35 + 16 9 - / +”
str = “1 2 - 3 4 - - 2 * 7.4 + 3.14 * 2 / 1.2 + 3 4 - -”
ops = %w[+ - * /]
arr = str.split(/\s+/)
err = arr.select {|c| c =~ /^\d+.?\d?/ || ops.include?©}
the_stack = []

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

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:

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

On Fri, 30 Nov 2007 08:28:17 -0500, Ruby Q. wrote:

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

-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-
=-=-=-=-=
2 3 5 + *
tells it to print the result.
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))

$ ruby postfix_to_infix.rb ‘1 56 35 + 16 9 - / +’ (1 + ((56 +

  1. / (16
  • 9)))

Posting equations and your output is not a spoiler.

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)

After trinking some coffee, I added functions and templates:

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)’
else
puts Quiz148.run(ARGV)
end
end

On Nov 30, 2007 2:28 PM, Ruby Q. [email protected] wrote:

the minimum of what is needed. For example, prefer these results:
$ 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 :frowning:

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.

Well, here is my submission… I truly was stuck with this so I just done
the most basic stuff, I will have a look through the other submissions a
bit later to see how others done it…

#!/usr/bin/ruby -w

argv = Array.new
if ARGV.empty?
puts "#{$0} "
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

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 Q. #148 (see http://www.rubyquiz.com/quiz148.html)

by Pawel R. ([email protected]).

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+5-3

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] =~/[a-z]+/ && a[1] =~/[a-z]+/
@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 =~
/([0-9.]+|[a-z]+)\s([0-9.]+|[a-z]+)\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 ([email protected]?)
        @string.sub!(/([a-z])/) {
            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 5-th 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

I’m sorry for spamming this list with my inferior solutions. But J
Koppel’s approach made me to reconsider my solution, which now
supports custom output format (eg for Arrays), functions with 3+
arity, and functions for which the arity is defined by the last
argument on the stack.

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?§
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

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)’
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)’
else
puts Quiz148.run(ARGV)
end
end

On Sun, 02 Dec 2007 12:14:10 -0500, Pawel R. wrote:

by Pawel R. ([email protected]).

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 =~

/([0-9.]+|[a-z]+)\s([0-9.]+|[a-z]+)\s((**)|(V)|+|*|/|-)/

–Ken

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 left-to-right:

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 5:28 AM, Ruby Q. [email protected] wrote:

This week’s quiz is to write a script that translates postfix expressions into
the equivalent infix expression.

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 S.

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

This forum is not affiliated to the Ruby language, Ruby on Rails framework, nor any Ruby applications discussed here.

| Privacy Policy | Terms of Service | Remote Ruby Jobs