From: Ezra Zygmuntowicz <ezmobius@...>
Date: 2007-04-29T09:41:35+09:00
Subject: Re: Infix to Postfix Method

Hi~

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

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

	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

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

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

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

end

class User
   attr_accessor :roles
   def initialize(*roles)
     @roles = roles
   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)