Friday, July 9, 2010

RPN Calculator

Here's another one from Programming Praxis. It's an RPN (reverse Polish calculator) problem that I've chosen to implement in Ruby. The text from Praxis is the header comment of the program.

The first thing we do is open up the Array class and alias last with a new method called peek which returns the the last element of the array. Obviously, we could just use last, but the "norm" for stacks is peek. Next we actually create the stack using an Array. We could probably create our own stack with only the appropriate methods, but that's probably overkill for this little project (as I suppose you could argue creating peek is). Next, we'll just loop forever, printing a prompt,reading a line of text, and then processing it. The processing consists of taking a line apart and grabbing either a number, the first regular expression, or an operator, the second. For a number, we simply push it on the stack. For an operator, we pop the top two items off the stack and perform the operation on them. Then we push the result back on the stack. Finally, we strip whatever we just found, either number or operator, off the line and continue. When we finish processing the line, we print the top of stack and then continue on to the next line.

Here's the actual code


# Implement an RPN calculator that takes an expression like 19 2.14 + 4.5 2 4.3
# / - * which is usually expressed as (19 + 2.14) * (4.5 - 2 / 4.3) and responds
# with 85.2974. The program should read expressions from standard input and
# print the top of the stack to standard output when a newline is encountered.
# The program should retain the state of the operand stack between expressions.


# Open up the Array class so we can add a
# method to look at the "top of the stack".
class Array
alias :peek :last
end

# Create the stack we'll use for processing.
stack = Array.new
while true

# Print the prompt.
print ">> "

# Get the line to process and remove the trailing \n.
line = gets.chomp

while line.size > 0

# Check for a number first so that we don't grab a +/-
# and use it for an operator.
if line =~ /^\s*([-+]?[0-9]*\.?[0-9]+)\s*/
# Found an operand so we'll just push it
# on the stack after changing it to a float.
stack.push $1.to_f
elsif line =~ /^\s*([\+\-\*\/])\s*/ then
# The line has an operator (+/-*).
operator = $1

# Get the operands off the stack.
operand_2 = stack.pop
operand_1 = stack.pop

# Evaluate the expression and push it on to the stack.
stack.push case operator
when '+'
operand_1 + operand_2
when '-'
operand_1 - operand_2
when '*'
operand_1 * operand_2
when '/'
operand_1 / operand_2
end
end

# Replace whatever we just found with the empty string.
line.sub!($&, "")
end

# We've finished processing the line, so print out the
# top of the stack.
puts "Top of stack = #{stack.peek}"
end



As always, let me know if you have questions or comments.

2 comments:

  1. Nice idea, here's my version: http://gist.github.com/477890

    ReplyDelete
  2. manveru, Very nice! I hadn't seen StringScanner before, but it's something I'll be using in the future.

    ReplyDelete