From: Justin Ethier <justin.ethier@...>
Date: 2007-12-03T02:27:52+09:00
Subject: Re: [QUIZ] Postfix to Infix (#148)

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

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 8:28 AM, Ruby Quiz <james@grayproductions.net> wrote:

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

------=_Part_6383_30243394.1196616474082--