Ruby Tips

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