From: Eric Mahurin <eric.mahurin@...>
Date: 2007-12-03T12:23:23+09:00
Subject: Re: [QUIZ] Postfix to Infix (#148)

------=_Part_6709_21522714.1196652205145
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
Content-Disposition: inline

On Nov 30, 2007 7:28 AM, Ruby Quiz <james@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 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}")
}

------=_Part_6709_21522714.1196652205145--