# Infix to Postfix Method

**URL:** <https://rubytalk.org/t/infix-to-postfix-method/37246>\
**Category:** ruby-talk\
**Created:** [28 April 2007 23:34 UTC](https://rubytalk.org/t/infix-to-postfix-method/37246 "2007-04-28T23:34:33Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![Peter\_Marsh](https://avatars.discourse-cdn.com/v4/letter/p/8c91f0/32.png) [@Peter\_Marsh](https://rubytalk.org/u/Peter_Marsh)\
**Post date:** [28 April 2007 23:34 UTC](https://rubytalk.org/t/infix-to-postfix-method/37246/1 "2007-04-28T23:34:33Z")

</div>

I'm still getting to grips with Ruby, but I think I'm doing well. My  
last post generated a lot of positive comments/advice which really  
helped me, so I thought I'd post some more of my code to try and repeat  
that!

The following is a method which will convert an infix expression (1+1)  
to a postfix expression (1 1 +). It expects a string and returns an  
array. Once again I'd really appreciate your comments.

def postfix(expression)

&nbsp;&nbsp;precedence = {nil=\>0,40=\>0,42 =\>2, 43=\>1, 45=\>1,47=\>2}

&nbsp;&nbsp;output = Array.new  
&nbsp;&nbsp;stack = Array.new  
&nbsp;&nbsp;temp = ''

&nbsp;&nbsp;expression.each\_byte do |asc|

&nbsp;&nbsp;&nbsp;&nbsp;case asc  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when 41  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;output.push(temp)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp = ''  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;loop{  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if stack.empty? == false  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;popped = stack.pop  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if popped == 40  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;output.push(popped.chr)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;raise 'Missing "("!'  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when 40,42, 43, 45, 47 #\*+-/  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;output.push(temp)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp = ''  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;unless asc == 40  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;p\_asc = precedence[asc]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;loop{  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if (p\_asc \> precedence[stack.last])  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;output.push(stack.pop.chr)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack.push(asc)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;temp += asc.chr  
&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;end  
&nbsp;&nbsp;stack.each{|asc| output.push(asc.chr)}  
&nbsp;&nbsp;!output.include?('(') or raise 'Missing ")"!'  
&nbsp;&nbsp;output.delete('')  
&nbsp;&nbsp;output  
end

> **···**
>
> --  
> Posted via [http://www.ruby-forum.com/](http://www.ruby-forum.com/).

---

<div class="post-metadata">

**Author:** ![Ezra\_Zygmuntowicz](https://avatars.discourse-cdn.com/v4/letter/e/958977/32.png) [@Ezra\_Zygmuntowicz](https://rubytalk.org/u/Ezra_Zygmuntowicz)\
**Post date:** [29 April 2007 00:41 UTC](https://rubytalk.org/t/infix-to-postfix-method/37246/2 "2007-04-29T00:41:35Z")

</div>

Hi~

> I'm still getting to grips with Ruby, but I think I'm doing well. My  
> last post generated a lot of positive comments/advice which really  
> helped me, so I thought I'd post some more of my code to try and repeat  
> that!
> 
> The following is a method which will convert an infix expression (1+1)  
> to a postfix expression (1 1 +). It expects a string and returns an  
> array. Once again I'd really appreciate your comments.

&nbsp;&nbsp;I have a very similar approach in a little parser I wrote for role based auth system. It uses a stack and converts to postfix before evaluating the expressions. It can parse strings like "(admin | moderator & !blacklist) | root" and compare to roles. I thought you might like to see it as it's very similar to the way your infix to postfix code works.

class RoleExp

&nbsp;&nbsp;&nbsp;def initialize(expression = nil)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@expression = expression  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;# using @@class vars here so they don't show up in #inspect  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@@symbols ||= {"(" =\> :lparen, ")" =\> :rparen, "&" =\> :and, "|" =\> :or, "!" =\> :not}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@@precedence ||= {:lparen =\> 0, :rparen =\> 0, :and =\> 1, :or =\> 1, :not =\> 2}  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;compile unless @expression.empty?  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;def compile(expression = nil)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@expression = expression || @expression  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@postfix =   
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack =   
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@expression.scan(/(\w+|\W)/).flatten.each do |term|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;term = @@symbols[term] || term.strip  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;next if term.to\_s.empty?  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;case term  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when :lparen  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack.push term  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when :and, :or, :not  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;until stack.empty?  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;break if @@precedence[term] \> @@precedence[stack.last]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@postfix \<\< stack.pop  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack.push term  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when :rparen  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while stack.last != :lparen  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@postfix \<\< stack.pop  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack.pop  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@postfix \<\< term  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@postfix.concat(stack.reverse)  
&nbsp;&nbsp;&nbsp;end

&nbsp;&nbsp;&nbsp;def compute  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return false if @postfix.empty?  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack =   
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@postfix.each do |term|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;case term  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when :and  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;rhs = stack.pop  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack.push(stack.pop && rhs)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when :or  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;rhs = stack.pop  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack.push(stack.pop || rhs)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;when :not  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack.push(!stack.pop)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;else  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack.push(yield(term))  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack.first  
&nbsp;&nbsp;&nbsp;end

end

class User  
&nbsp;&nbsp;&nbsp;attr\_accessor :roles  
&nbsp;&nbsp;&nbsp;def initialize(\*roles)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@roles = roles  
&nbsp;&nbsp;&nbsp;end  
end

bool = RoleExp.new "(admin | moderator & !blacklist)"  
p bool  
puts '='\*40

user = User.new 'admin', 'moderator'  
p user  
p bool.compute {|term| user.roles.include? term}  
puts '='\*40

user.roles \<\< 'blacklist'  
p user  
p bool.compute {|term| user.roles.include? term}

Cheers-  
-- Ezra Zygmuntowicz-- Lead Rails Evangelist  
-- ez@engineyard.com  
-- Engine Yard, Serious Rails Hosting  
-- (866) 518-YARD (9273)

> **···**
>
> On Apr 28, 2007, at 4:34 PM, Peter Marsh wrote:

---

<div class="post-metadata">

**Author:** ![Paul\_Brannan](https://avatars.discourse-cdn.com/v4/letter/p/76d3ee/32.png) [@Paul\_Brannan](https://rubytalk.org/u/Paul_Brannan)\
**Post date:** [29 April 2007 01:45 UTC](https://rubytalk.org/t/infix-to-postfix-method/37246/3 "2007-04-29T01:45:47Z")

</div>

> &nbsp;&nbsp;precedence = {nil=\>0,40=\>0,42 =\>2, 43=\>1, 45=\>1,47=\>2}

In general it's better not to explicitly specify ASCII values, so I'd  
write instead:

&nbsp;&nbsp;&nbsp;&nbsp;precedence = {nil=\>0, ?(=\>0, ?\*=\>2, ?+=\>1, ?-=\>1, ?/=\>2}

Note though that on newer versions of ruby, ?x will give you a string  
containing "x" rather than the ascii value of x. So to be more  
compatible, instead of writing:

> &nbsp;&nbsp;expression.each\_byte do |asc|

you'll want to write:

&nbsp;&nbsp;&nbsp;&nbsp;expression.each\_byte do |c|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;c = c.chr if ?x == "x"

and use c wherever you were using asc before.

(I feel like there should be a better way to do this, but I haven't  
found one. Pity there's no String#each\_char).

Paul

> **···**
>
> On Sun, Apr 29, 2007 at 08:34:33AM +0900, Peter Marsh wrote:

---

<div class="post-metadata">

**Author:** ![Peter\_Marsh](https://avatars.discourse-cdn.com/v4/letter/p/8c91f0/32.png) [@Peter\_Marsh](https://rubytalk.org/u/Peter_Marsh)\
**Post date:** [29 April 2007 10:01 UTC](https://rubytalk.org/t/infix-to-postfix-method/37246/4 "2007-04-29T10:01:32Z")

</div>

Paul Brannan wrote:

> **···**
>
> > On Sun, Apr 29, 2007 at 08:34:33AM +0900, Peter Marsh wrote:
> > 
> > > &nbsp;&nbsp;precedence = {nil=\>0,40=\>0,42 =\>2, 43=\>1, 45=\>1,47=\>2}
> > 
> > In general it's better not to explicitly specify ASCII values, so I'd  
> > write instead:
> 
> Could you explain why please, I can't see how it makes any difference,  
> really (but I am a noob!).
> 
> --  
> Posted via [http://www.ruby-forum.com/\](http://www.ruby-forum.com/%5C).

---

<div class="post-metadata">

**Author:** ![Logan\_Capaldo](https://avatars.discourse-cdn.com/v4/letter/l/7ea924/32.png) [@Logan\_Capaldo](https://rubytalk.org/u/Logan_Capaldo)\
**Post date:** [29 April 2007 20:18 UTC](https://rubytalk.org/t/infix-to-postfix-method/37246/5 "2007-04-29T20:18:45Z")

</div>

> (I feel like there should be a better way to do this, but I haven't  
> found one. Pity there's no String#each\_char).

There is a String#each\_char, but it's spelled a little funny 😉 :

"abc".scan(/./m) do |char|  
&nbsp;&nbsp;&nbsp;&nbsp;p char  
end

Paul

> **···**
>
> On 4/28/07, Paul Brannan \<pbrannan@atdesk.com\> wrote:
> 
> >

---

<div class="post-metadata">

**Author:** ![Dan\_Zwell](https://avatars.discourse-cdn.com/v4/letter/d/7ea924/32.png) [@Dan\_Zwell](https://rubytalk.org/u/Dan_Zwell)\
**Post date:** [29 April 2007 10:35 UTC](https://rubytalk.org/t/infix-to-postfix-method/37246/6 "2007-04-29T10:35:47Z")

</div>

Peter Marsh wrote:

> Paul Brannan wrote:
> 
> > > &nbsp;&nbsp;precedence = {nil=\>0,40=\>0,42 =\>2, 43=\>1, 45=\>1,47=\>2}
> > 
> > In general it's better not to explicitly specify ASCII values, so I'd  
> > write instead:
> 
> Could you explain why please, I can't see how it makes any difference, really (but I am a noob!).

In a high level language, it's good to use the high level functions. That way if low level representations of things ever change in a newer version, your existing scripts will be more likely to work in the newer version.

Consider this example, even though it's probably not a very good one: What if the upcoming unicode support changed something with the internal representation of strings so that "\*" was no longer represented as "42"? Then the entry in the hash {42 =\> 2} would no longer be applicable, but {?\* =\> 2} will continue to work, because if ruby's internal representation of "\*" changes in some version, so will the value of ?\*.

It also makes me happy that someone else is working on a converter from infix to postfix. I just (almost) finished implementing Dijkstra's Shunting Yard algorithm ([http://en.wikipedia.org/wiki/Shunting\_yard\_algorithm\](http://en.wikipedia.org/wiki/Shunting_yard_algorithm%5C)) in Ruby, as part of a bigger project. If you want to look at it, it's at [http://paste-bin.com/11526](http://paste-bin.com/11526), but it's 227 lines of poorly commented meaty algorithm. It currently works on mathematical equations with variables. It doesn't do any evaluation, though--just parses to an array.

Anyway, have fun.  
Dan

> **···**
>
> > > On Sun, Apr 29, 2007 at 08:34:33AM +0900, Peter Marsh wrote:

---

<div class="post-metadata">

**Author:** ![Peter\_Marsh](https://avatars.discourse-cdn.com/v4/letter/p/8c91f0/32.png) [@Peter\_Marsh](https://rubytalk.org/u/Peter_Marsh)\
**Post date:** [29 April 2007 10:47 UTC](https://rubytalk.org/t/infix-to-postfix-method/37246/7 "2007-04-29T10:47:57Z")

</div>

Thanks for that explination, it makes quite a lot of sense!

> **···**
>
> --  
> Posted via [http://www.ruby-forum.com/](http://www.ruby-forum.com/).

---

<div class="post-metadata">

**Author:** ![Thomas\_Hurst](https://avatars.discourse-cdn.com/v4/letter/t/53a042/32.png) [@Thomas\_Hurst](https://rubytalk.org/u/Thomas_Hurst)\
**Post date:** [29 April 2007 18:34 UTC](https://rubytalk.org/t/infix-to-postfix-method/37246/8 "2007-04-29T18:34:06Z")

</div>

Your implementation is very similar to mine (though I'm parsing boolean  
search queries, ala Google) -- mine is a bit simpler:

&nbsp;&nbsp;&nbsp;&nbsp;InputPriority = Hash.new(1000)  
&nbsp;&nbsp;&nbsp;&nbsp;InputPriority[:and] = 800  
&nbsp;&nbsp;&nbsp;&nbsp;InputPriority[:or] = 500  
&nbsp;&nbsp;&nbsp;&nbsp;InputPriority[:not] = 900  
&nbsp;&nbsp;&nbsp;&nbsp;InputPriority[nil] = 0  
&nbsp;&nbsp;&nbsp;&nbsp;InputPriority[:open] = 1000  
&nbsp;&nbsp;&nbsp;&nbsp;InputPriority[:close] = 1  
&nbsp;&nbsp;&nbsp;&nbsp;StackPriority = InputPriority.dup  
&nbsp;&nbsp;&nbsp;&nbsp;StackPriority[:open] = 1  
&nbsp;&nbsp;&nbsp;&nbsp;StackPriority[:close] = 1000

&nbsp;&nbsp;&nbsp;&nbsp;def rpnise(itokens)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack =   
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;instructions =

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;itokens.each do |itoken|  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if InputPriority[itoken] \> StackPriority[stack.last]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack.push(itoken)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;elsif InputPriority[itoken] \<= StackPriority[stack.last]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;while StackPriority[stack.last] \>= InputPriority[itoken]  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;instructions \<\< stack.pop  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack.push(itoken)  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;end  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;instructions.concat(stack.reverse)  
&nbsp;&nbsp;&nbsp;&nbsp;end

After this I sanitize the token stream and use it to build a tree of  
BooleanAnd/Or/Not/SubStringQuery objects to represent the search (which  
then rewrite themselves in a vague attempt at optimization and sorting).

Demo:  
&nbsp;&nbsp;# Token stream  
&nbsp;&nbsp;irb(main):009:0\> toks = analyser.simplify(tokenizer.tokenize("foo AND bar OR (wibble OR wobble NOT foo)"))  
&nbsp;&nbsp;[#\<NSearch::SubStringQuery:0x18a4a20 @substr="foo"\>,  
&nbsp;&nbsp;&nbsp;:and,  
&nbsp;&nbsp;&nbsp;#\<NSearch::SubStringQuery:0x18a49f8 @substr="bar"\>,  
&nbsp;&nbsp;&nbsp;:or,  
&nbsp;&nbsp;&nbsp;:open,  
&nbsp;&nbsp;&nbsp;#\<NSearch::SubStringQuery:0x18a49a8 @substr="wibble"\>,  
&nbsp;&nbsp;&nbsp;:or,  
&nbsp;&nbsp;&nbsp;#\<NSearch::SubStringQuery:0x18a4958 @substr="wobble"\>,  
&nbsp;&nbsp;&nbsp;:and,  
&nbsp;&nbsp;&nbsp;:not,  
&nbsp;&nbsp;&nbsp;#\<NSearch::SubStringQuery:0x18a4908 @substr="foo"\>,  
&nbsp;&nbsp;&nbsp;:close]

&nbsp;&nbsp;&nbsp;irb(main):010:0\> analyser.rpnise(toks)  
&nbsp;&nbsp;&nbsp;[#\<NSearch::SubStringQuery:0x188a670 @substr="foo"\>,  
&nbsp;&nbsp;&nbsp;&nbsp;#\<NSearch::SubStringQuery:0x188a648 @substr="bar"\>,  
&nbsp;&nbsp;&nbsp;&nbsp;:and,  
&nbsp;&nbsp;&nbsp;&nbsp;#\<NSearch::SubStringQuery:0x188a5f8 @substr="wibble"\>,  
&nbsp;&nbsp;&nbsp;&nbsp;#\<NSearch::SubStringQuery:0x188a5a8 @substr="wobble"\>,  
&nbsp;&nbsp;&nbsp;&nbsp;#\<NSearch::SubStringQuery:0x188a558 @substr="foo"\>,  
&nbsp;&nbsp;&nbsp;&nbsp;:not,  
&nbsp;&nbsp;&nbsp;&nbsp;:and,  
&nbsp;&nbsp;&nbsp;&nbsp;:or,  
&nbsp;&nbsp;&nbsp;&nbsp;:or]

You can then follow the instructions, popping each SubStringQuery onto a  
stack and popping them off on :and, :or and :not to build a tree of  
query objects:

#to\_s  
&nbsp;&nbsp;OR(OR(AND(NOT("foo"),"wobble"),"wibble"),AND("bar","foo"))

#to\_sql  
&nbsp;&nbsp;(((NOT (Title LIKE "%foo%") AND Title LIKE "%wobble%") OR Title LIKE  
&nbsp;&nbsp;&nbsp;&nbsp;"%wibble%") OR (Title LIKE "%bar%" AND Title LIKE "%foo%"))

I'd recommend against using Ruby's own Generator, btw; it uses callcc  
and has a tendancy towards being slow and leaky. If you just need a  
#next/#peek method, just turn it into an array and shove it in an  
appropriate object which tracks the position.

> **···**
>
> \* Dan Zwell (dzwell@gmail.com) wrote:
> 
> > It also makes me happy that someone else is working on a converter  
> > from infix to postfix. I just (almost) finished implementing  
> > Dijkstra's Shunting Yard algorithm  
> > ([http://en.wikipedia.org/wiki/Shunting\_yard\_algorithm\](http://en.wikipedia.org/wiki/Shunting_yard_algorithm%5C)) in Ruby, as  
> > part of a bigger project. If you want to look at it, it's at  
> > [http://paste-bin.com/11526](http://paste-bin.com/11526), but it's 227 lines of poorly commented  
> > meaty algorithm. It currently works on mathematical equations with  
> > variables. It doesn't do any evaluation, though--just parses to an  
> > array.
> 
> --  
> Thomas 'Freaky' Hurst  
> &nbsp;&nbsp;&nbsp;&nbsp;[http://hur.st/](http://hur.st/)

---

<div class="post-metadata">

**Author:** ![Dan\_Zwell](https://avatars.discourse-cdn.com/v4/letter/d/7ea924/32.png) [@Dan\_Zwell](https://rubytalk.org/u/Dan_Zwell)\
**Post date:** [29 April 2007 20:03 UTC](https://rubytalk.org/t/infix-to-postfix-method/37246/9 "2007-04-29T20:03:14Z")

</div>

Thomas Hurst wrote:

> Demo:  
> &nbsp;&nbsp;# Token stream  
> &nbsp;&nbsp;irb(main):009:0\> toks = analyser.simplify(tokenizer.tokenize("foo AND bar OR (wibble OR wobble NOT foo)"))  
> &nbsp;&nbsp;[#\<NSearch::SubStringQuery:0x18a4a20 @substr="foo"\>,  
> &nbsp;&nbsp;&nbsp;:and,  
> &nbsp;&nbsp;&nbsp;#\<NSearch::SubStringQuery:0x18a49f8 @substr="bar"\>,  
> &nbsp;&nbsp;&nbsp;:or,  
> &nbsp;&nbsp;&nbsp;:open,  
> &nbsp;&nbsp;&nbsp;#\<NSearch::SubStringQuery:0x18a49a8 @substr="wibble"\>,  
> &nbsp;&nbsp;&nbsp;:or,  
> &nbsp;&nbsp;&nbsp;#\<NSearch::SubStringQuery:0x18a4958 @substr="wobble"\>,  
> &nbsp;&nbsp;&nbsp;:and,  
> &nbsp;&nbsp;&nbsp;:not,  
> &nbsp;&nbsp;&nbsp;#\<NSearch::SubStringQuery:0x18a4908 @substr="foo"\>,  
> &nbsp;&nbsp;&nbsp;:close]
> 
> &nbsp;&nbsp;&nbsp;irb(main):010:0\> analyser.rpnise(toks)  
> &nbsp;&nbsp;&nbsp;[#\<NSearch::SubStringQuery:0x188a670 @substr="foo"\>,  
> &nbsp;&nbsp;&nbsp;&nbsp;#\<NSearch::SubStringQuery:0x188a648 @substr="bar"\>,  
> &nbsp;&nbsp;&nbsp;&nbsp;:and,  
> &nbsp;&nbsp;&nbsp;&nbsp;#\<NSearch::SubStringQuery:0x188a5f8 @substr="wibble"\>,  
> &nbsp;&nbsp;&nbsp;&nbsp;#\<NSearch::SubStringQuery:0x188a5a8 @substr="wobble"\>,  
> &nbsp;&nbsp;&nbsp;&nbsp;#\<NSearch::SubStringQuery:0x188a558 @substr="foo"\>,  
> &nbsp;&nbsp;&nbsp;&nbsp;:not,  
> &nbsp;&nbsp;&nbsp;&nbsp;:and,  
> &nbsp;&nbsp;&nbsp;&nbsp;:or,  
> &nbsp;&nbsp;&nbsp;&nbsp;:or]
> 
> You can then follow the instructions, popping each SubStringQuery onto a  
> stack and popping them off on :and, :or and :not to build a tree of  
> query objects:
> 
> #to\_s  
> &nbsp;&nbsp;OR(OR(AND(NOT("foo"),"wobble"),"wibble"),AND("bar","foo"))
> 
> #to\_sql  
> &nbsp;&nbsp;(((NOT (Title LIKE "%foo%") AND Title LIKE "%wobble%") OR Title LIKE  
> &nbsp;&nbsp;&nbsp;&nbsp;"%wibble%") OR (Title LIKE "%bar%" AND Title LIKE "%foo%"))
> 
> I'd recommend against using Ruby's own Generator, btw; it uses callcc  
> and has a tendancy towards being slow and leaky. If you just need a  
> #next/#peek method, just turn it into an array and shove it in an  
> appropriate object which tracks the position.

That's pretty neat. I hadn't thought of using this stuff to generate SQL. I'll probably acually use that idea some day. And thanks for the bit about Generator. I'm currently looking through a computational script (ported from c++)--I could never figure out why it used all my ram within a few seconds, but it used Generators several thousand times. I'm rewriting parts of it now, and we'll see what happens.

Dan

---

<div class="post-metadata">

**Author:** ![Thomas\_Hurst](https://avatars.discourse-cdn.com/v4/letter/t/53a042/32.png) [@Thomas\_Hurst](https://rubytalk.org/u/Thomas_Hurst)\
**Post date:** [29 April 2007 23:31 UTC](https://rubytalk.org/t/infix-to-postfix-method/37246/10 "2007-04-29T23:31:33Z")

</div>

> That's pretty neat. I hadn't thought of using this stuff to generate  
> SQL. I'll probably acually use that idea some day.

It can perform the match itself too:

irb(main):025:0\> query = NSearch::QueryParser.new.parse('foo bar NOT heh')  
#\<NSearch::RootQuery:0x1715380  
&nbsp;&nbsp;@query=  
&nbsp;&nbsp;&nbsp;#\<NSearch::BooleanAndQuery:0x1714fe8  
&nbsp;&nbsp;&nbsp;&nbsp;@criteria=  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;[#\<NSearch::SubStringQuery:0x1715240 @substr="bar"\>,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#\<NSearch::SubStringQuery:0x1715268 @substr="foo"\>,  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;#\<NSearch::BooleanNotQuery:0x1715038  
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;@criteria=#\<NSearch::SubStringQuery:0x17151f0 @substr="heh"\>\>]\>\>

I can then query.rewrite to have it normalize itself (sort, minor  
optimization), have it turn itself into various forms (SQL, boolean),  
and of course execute it:

irb(main):029:0\> query.match('foo bar')  
=\> true  
irb(main):030:0\> query.match('foo bar heh')  
=\> false

I also have a C library and a Ruby extension which uses it which  
accelerates matches. We're currently using it in our new search engine.  
Performance is on the order of 5 million matches/second on a single  
2GHz Opteron. In pure Ruby it's closer to 200,000/sec.

I'm planning to\_ferret to produce an equivilent ferret query, and  
extending it to provide tagged queries: "category:ruby lang:en OR  
lang:de". Obviously the trickiest bit here is making it work in C.

None of this is public, alas, but if there's interest..

> And thanks for the bit about Generator. I'm currently looking through  
> a computational script (ported from c++)--I could never figure out why  
> it used all my ram within a few seconds, but it used Generators  
> several thousand times. I'm rewriting parts of it now, and we'll see  
> what happens.

Yeah, that'll be the callcc. I really hope it's improved for 1.9.

> **···**
>
> \* Dan Zwell (dzwell@gmail.com) wrote:
> 
> --  
> Thomas 'Freaky' Hurst  
> &nbsp;&nbsp;&nbsp;&nbsp;[http://hur.st/](http://hur.st/)