# 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.chr+exp.chr+exp.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
```