# Re: Postfix to Infix (#148)

**URL:** <https://www.ruby-forum.com/t/re-postfix-to-infix-148/121902>\
**Category:** Ruby\
**Created:** [December 2, 2007, 5:41pm UTC](https://www.ruby-forum.com/t/re-postfix-to-infix-148/121902 "2007-12-02T17:41:44Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![jameskelly](https://www.ruby-forum.com/letter_avatar_proxy/v4/letter/j/3ab097/32.png) [@jameskelly](https://www.ruby-forum.com/u/jameskelly)\
**Post date:** [December 2, 2007, 5:41pm UTC](https://www.ruby-forum.com/t/re-postfix-to-infix-148/121902/1 "2007-12-02T17:41:44Z")

</div>

PREC = {:+ =\> 0,:- =\> 0,:\* =\> 1,😕 =\> 1,:% =\> 1,:^ =\> 2}  
LEFT\_ASSOCS = {:+ =\> true,:- =\> true,:\* =\> true,😕 =\> true,  
:% =\> true,:^ =\> false}  
RIGHT\_ASSOCS = {:+ =\> true,:- =\> false,:\* =\> true,😕 =\> false,  
:% =\> false,:^ =\> true}

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

----- Original Message ----  
From: Ruby Q. [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
To: ruby-talk ML [removed\_email\_address@domain.invalid](mailto:removed_email_address@domain.invalid)  
Sent: Friday, November 30, 2007 7:28:17 AM  
Subject: [QUIZ] 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/](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.

```
  ____________________________________________________________________________________

```

Get easy, one-click access to your favorites.  
Make Yahoo! your homepage.  
[http://www.yahoo.com/r/hs](http://www.yahoo.com/r/hs)