Ruby code snippets : RPN Generator

The following program gives good illustration of string functions, regular expressions and blocks. This is a solution to the Reverse Polish Notation generator problem explained at http://www.spoj.pl/problems/ONP/.

Given an algebraic expression with brackets, this program will output the corresponding RPN form. For example, (a+(b+c)) becomes abc++. A good exercise will be to extend this program to use operator precedence in addition to brackets. But that would probably need a better algorithm.

# converts an infix algebraic expression to reverse polish notation (rpn)
# for example, (a+b)+c becomes cab++
# Note that braces are mandatory in this version : (a+(b+c)) works but not (a+b+c)
# This uses token replacement technique: (a+(b+c)) becomes (a+A) and then B where A = bc+ and B is aA+. 
# Finally A,B,.. etc are replaced by their original expression using a hash.
class RPNGenerator
  attr_accessor :lookup_token;
  attr_accessor :lookup_hash;
  
  @@SIMPLEST_EXP_REGEX = /[a-z|A-Z][\+\-\*\/\^][a-z|A-Z]/;
  @@ENCODED_REGEX = /[A-Z]/;
  
  def initialize
    @lookup_token = "A"; #each lowest expression tokens are replaced using this
    @lookup_hash = Hash.new
  end

  # Process the infix expression and return RPN
  # Modifies the original expression
  def process(infix_exp)
    substitute(infix_exp)
    expandRpn(infix_exp)
    infix_exp
  end
  
  # This substitutes the lowest level of expressions without braces to single capital letter tokens.
  # So final output will be a single capital letter.
  # Example -> (a+(b+c)) ->(a+A) -> B
  def substitute(infix_exp)
    simple_exp = infix_exp.scan(@@SIMPLEST_EXP_REGEX)
    simple_exp.each do
      |exp|
      rpn = exp[0].chr+exp[2].chr+exp[1].chr
      @lookup_hash[@lookup_token]=rpn
      infix_exp.sub!("("+exp+")",@lookup_token)
      @lookup_token.next! # get the next unique replacement token
    end
    substitute(infix_exp) if infix_exp.scan(@@SIMPLEST_EXP_REGEX).length > 0
  end

  # Expand the single capital letter token to RPN form using the supporting hash
  # Example -> B -> aA+ -> abc++
  def expandRpn(shortForm)
    shortForm.each_byte do |enc_char|
      enc_char = enc_char.chr
      shortForm.sub!(enc_char,@lookup_hash[enc_char]) if @lookup_hash[enc_char] !=nil
    end
    expandRpn(shortForm) if shortForm.scan(@@ENCODED_REGEX).length > 0
  end
  
  puts "Enter an infix expression: "
  infix = gets # get infix expression from user
  rpn = (RPNGenerator.new).process(infix)
  puts "Equivalent RPN expression is: #{rpn}" 
end

Leave a Reply