[Neworleans-pm] Fwd: Solutions and Discussion for Perl Quiz of the
Week #25 (RPN calculator)
E. Strade, B.D.
estrabd at yahoo.com
Thu Oct 14 11:28:35 CDT 2004
=====
http://www.brettsbsd.net/~estrabd
__________________________________
Do you Yahoo!?
Yahoo! SiteBuilder - Free, easy-to-use web site design software
http://sitebuilder.yahoo.com
----- Original message -----
From: "Dan Sanderson" <lists at dansanderson.com>
To: perl-qotw at plover.com
Date: Thu, 14 Oct 2004 10:33:37 -0400
Subject: Solutions and Discussion for Perl Quiz of the Week #25 (RPN
calculator)
Sample solutions and discussion
Perl Quiz of The Week #25 (20040928)
(The quiz question is archived at http://perl.plover.com/qotw/r/025 .)
== Posted Solutions
As of October 3, 2004, twelve people submitted solutions to this quiz.
Nine used Perl, one used Python and two used Ruby. Thanks to everyone
who participated in this week's quiz.
Rod Adams
http://perl.plover.com/~alias/list.cgi?1:mss:2295
Kester Allen
http://perl.plover.com/~alias/list.cgi?1:mss:2297
Rich Bishop
http://perl.plover.com/~alias/list.cgi?1:mss:2292
Dan Boger
http://perl.plover.com/~alias/list.cgi?1:mss:2302
Roger Burton West
http://perl.plover.com/~alias/list.cgi?1:msp:2285
Michael Carman
http://perl.plover.com/~alias/list.cgi?1:msp:2288
http://perl.plover.com/~alias/list.cgi?1:mss:2294
Andrew Dalke (Python)
http://perl.plover.com/~alias/list.cgi?1:mss:2300
Jon Ericson
http://perl.plover.com/~alias/list.cgi?1:msp:2294
James Edward Gray II (Ruby)
http://perl.plover.com/~alias/list.cgi?1:msp:2284
Zed Lopez
http://perl.plover.com/~alias/list.cgi?1:msp:2297
Alex Smolianinov
http://perl.plover.com/~alias/list.cgi?1:mss:2304
http://perl.plover.com/~alias/list.cgi?1:mss:2317
Mike Stok (Ruby)
http://perl.plover.com/~alias/list.cgi?1:mss:2303
I tried to get every solution working. A few I couldn't get to run,
and a few more could not do everything listed in the original problem,
but most solutions did quite well and bugs seemed minor. The
following test script exercised the basic features (without causing
error conditions):
3
5
+
2 *
2 3 + /
5 -
10 3 %
2 8 **
drop
100
swap
clear
100 dup
200 dup + + +
Many solutions implemented extensions to the basic problem, including
some or all of the suggestions listed with the problem text, and many
good original ideas. I did not test every feature of every
implementation, but you should give them a try, they're neat.
As this was intended to be a "regular" quiz, I will walk through a
simple a simple Perl implementation. We can discuss fancier topics in
perl-qotw-discuss.
== Prompting For and Processing Input
A fancy prompt was not actually a requirement of the quiz, but it's
easy to include one using the Perl module Term::Readline. The
following is an example of setting up a prompt and looping over input,
one line at a time, until the user hits Control-D (the End Of File
character):
use Term::Readline;
my $term = new Term::ReadLine 'RPN calculator';
my $prompt = '> ';
# ...
while (defined(my $line = $term->readline($prompt))) {
# ...
}
exit(0);
Without a fancy prompt, we could just read lines of input from STDIN
the usual way:
while (defined(my $line = <STDIN>)) {
# ...
}
The calculator processes input one term at a time, and there can be
multiple terms on a line of input. We can split the line into a list
of terms using the split operator and a regular expression that
matches white space:
for my $term (split(/\s+/, $line)) {
# ...
}
== The Stack
Each term will be either a number or an operation. If the term is a
number, it gets pushed onto a stack. If the term is an operation, the
operation executes, possibly using or modifying the contents of the
stack.
Perl arrays can behave as stacks easily, using Perl's push and pop
operators. The calculator only needs one stack:
my @stack;
After each line is processed, the stack is printed to the terminal.
The problem text showed the stack being printed from "bottom" to
"top," one element per line. Each line included a number representing
the stack level, where 0 is the top. This display makes it easy to
use stack manipulation functions that take a stack level number as a
parameter, like the suggested "roll" operation.
If we're using Perl's push and pop operators, we must remember that
the top of the stack is the last element in the @stack array. The
following for() loop displays the elements in the proper order, with
the correct numbering:
for (my $i = scalar(@stack); $i > 0; --$i) {
print $i-1, ": ", $stack[$i-1], "\n";
}
== Processing Terms
The calculator needs to do something different if a term matches an
operation, or if it matches a number. If it matches neither a number
or a known operation, it is an error. A simple way to do something
different for each case would be an if/elsif/else structure:
if ($term =~ / (a pattern that matches a number) /) {
# Push the number onto the stack.
# ...
} elsif ($term eq '+') {
# Execute the plus (+) operation.
# ...
} elsif ($term eq '-') {
# Execute the minus (-) operation.
# ...
# ...
} else {
print "Invalid term: $term\n";
}
We can construct a regular expression that matches a number by
deciding what makes a number. For instance, a number might begin with
a minus sign (if it is negative), then have zero or more digits, then
optionally have a decimal point and one or more digits. Such a
regular expression might look like this:
if ($term =~ /^-?\d*(\.\d+)?$/) {
Several posted solutions used the Regexp::Common module to provide the
pattern that matches a number. The patterns included in this module
are thorough, well tested, and cover many more cases that the pattern
above forgot. The module includes patterns for numbers, dates,
delimited strings, balanced parentheses, profane language, and much
more.
use Regexp::Common;
# ...
if ($term =~ /^$RE{num}{real}$/) {
If the term is a number, push it onto the stack. For this example,
we'll assume that the term is something Perl understands as a number,
so we can treat the $term value as a number without further
manipulation. Only numbers are allowed on our stack, so we simply
need to push it:
push @stack, $term;
== Arithmetic Operations
If the term is an operation, the calculator performs the operation
using values on the stack. The basic problem description listed six
arithmetic operations, each of which takes two values and results in
one value: + - * / % **
Here is a simple implementation of the plus (+) operation, which pops
two values off the top of the stack, adds them together, and pushes
the result on the stack:
} elsif ($term eq '+') {
my $a = pop @stack;
my $b = pop @stack;
push @stack, $b + $a;
The remaining arithmetic operations could be written similarly.
Notice that for some operations, the order of terms is important. The
problem text says "20 5 /" results in 20 divided by 5, which equals 4.
This means the division operation will pop the 5 first ($a) then the
20 ($b), so it must return $b / $a to produce the correct result.
== Stack Manipulation Operations
Here are possible implementations for the four stack manipulation
operations mentioned in the problem:
} elsif ($term eq 'drop') {
pop @stack;
} elsif ($term eq 'swap') {
my $a = pop @stack;
my $b = pop @stack;
push @stack, $a, $b;
} elsif ($term eq 'clear') {
@stack = ();
} elsif ($term eq 'dup') {
push @stack, $stack[$#stack];
Notice how this implementation of "dup" gets the value of the last
element in the array (the top of the stack) without popping it.
== Errors and Edge Cases
The problem text stated that if a term or operation causes an error,
processing of a line stops, allowing the user to correct the error
without further operations on the line causing undesirable damage to
the contents of the stack. So far, we have code that detects one
error case, when the term is neither a number nor a valid operation.
We want it to both print an error and stop processing the line.
Since we're processing terms in a for loop, Perl's "last" operator
will exit out of the loop without processing additional terms.
} else {
print "Invalid term: $term\n";
last;
}
Another error case might be using an operation when there aren't
enough elements on the stack. Using the + operation when there is
only one item doesn't make sense, and is probably an error the user
wants to correct before proceeding. In this implementation, we can
use "last" again when an error is encountered:
} elsif ($term eq '+') {
if (scalar(@stack) < 2) {
print "Not enough elements on stack\n";
last;
}
my $a = pop @stack;
my $b = pop @stack;
push @stack, $b + $a;
Some operations have specific error cases. For instance, "99 0 /"
would cause Perl to attempt to divide by zero, which would result in
termination of the program. We may want the division operation to
catch this case as an error and continue to run:
} elsif ($term eq '/') {
if (scalar(@stack) < 2) {
print "Not enough elements on stack\n";
last;
}
if ($stack[$#stack] == 0) {
print "Division by zero attempted\n";
last;
}
my $a = pop @stack;
my $b = pop @stack;
push @stack, $b + $a;
There are other edge cases we may want to consider to make the
calculator more useful. For example, we may want a blank line to
simply re-display the prompt, instead of complaining.
== Other Ways: A Dispatch Table
The implementation above uses an if/elsif/else structure to check if
$term is equal to one of the strings that represents an operation.
For each term, each operation is compared until a match is found.
Because the term has to match an exact string, we could use a hash
table instead of a bunch of conditions to look up the operation to
perform. This could be faster, and may make the source code easier to
read if there are many possible operations. We could even write a way
for other modules or plugins to add operations to the calculator
simply by modifying the hash table.
A hash table can refer to operations using subroutine references. For
instance:
sub plus {
my $a = pop @stack;
my $b = pop @stack;
push @stack, $b + $a;
}
%operations = ( '+' => \&plus,
# ...
);
If no other part of the program is going to use the &plus subroutine,
we can write this as an anonymous subroutine:
%operations = ( '+' => sub {
# ...
my $a = pop @stack;
my $b = pop @stack;
push @stack, $b + $a;
},
# ...
);
We can then replace all the operations in our if/elsif/else structure
with:
} elsif (exists($operations{$term})) {
$operations{$term}->();
Now that the code for executing the plus operation is in an anonymous
subroutine, the routine can no longer use "last" to stop processing of
terms if there is an error. We need a different way for subroutines
to report errors to the main loop. The subroutines could simply
return true if successful or false if there was an error, or it could
return the empty string ("") on success and an error message if there
was an error.
A better way might be to use Perl exception handling. The subroutine
could call "die" with a message if there was an error. The code
calling the subroutine could be wrapped in an "eval" block, which
executes the code and stores the message of any "die" call in the $@
special variable.
'/' => sub {
die "Not enough elements on stack"
if (scalar(@stack) < 2);
die "Division by zero attempted"
if $stack[$#stack] == 0;
my $a = pop @stack;
my $b = pop @stack;
push @stack, $b + $a;
},
# ...
} elsif (exists($operations{$term})) {
eval { $operations{$term}->(); }
if ($@) {
print $@;
last;
}
A nice side-effect of using exception handling is we no longer need to
worry about calculation errors that would cause Perl to die.
Specifically, we do not need to check if the / operator would cause
division by zero, because if it did, Perl would throw an exception
that would get caught in the eval block, and an appropriate error
message would be printed.
== Other Ways: Re-using Code
Our operation routines are getting rather long, repeating common tasks
like checking the number of elements on the stack, popping the
appropriate number of items, and so forth. The posted solutions used
a bunch of different techniques to make operation definitions more
succinct.
We could have a subroutine that checks that there are at least two
elements on the stack, reports an error if there aren't, and otherwise
pops and returns the two elements:
sub pop2 {
die "Not enough values on stack\n" if scalar(@stack) < 2;
return (pop @stack, pop @stack);
}
Then our six arithmetic operations could be defined as:
'+' => sub { my ($a, $b) = &pop2; push @stack, $b + $a; },
'-' => sub { my ($a, $b) = &pop2; push @stack, $b - $a; },
'*' => sub { my ($a, $b) = &pop2; push @stack, $b * $a; },
'/' => sub { my ($a, $b) = &pop2; push @stack, $b / $a; },
'%' => sub { my ($a, $b) = &pop2; push @stack, $b % $a; },
'**' => sub { my ($a, $b) = &pop2; push @stack, $b ** $a; },
We could go further, and define a subroutine that evaluates any binary
operation that can be evaluated in Perl using infix notation:
sub do_binary {
my $op = (@_);
die "Not enough values on stack\n" if scalar(@stack) < 2;
my ($a, $b) = (pop @stack, pop @stack);
push @stack, eval "$b $op $a";
}
# ...
'+' => sub { do_binary('+'); },
# ...
== Extensions
An extension suggested by the problem text involved additional Perl
builtin operations, some of which were infix binary operations ($b &
$a) while others were prefix unary (cos $a) or prefix binary (atan2
$b, $a). If succinct dispatch code was used, additional supporting
code may be required.
Another involved entering numbers of different bases, supporting
hexadecimal (0xABCD), binary (0b11010), and octal (0762). These forms
are understood by Perl as numbers, though strings containing these
would need to be eval'd into numeric form before being pushed onto the
stack (otherwise they remain strings). The pattern match for numbers
would also need to be changed to accept the new forms.
The problem text suggested different display modes for the stack,
controlled by operations (that otherwise did not affect the stack
contents). A state variable, affected by the "dec", "bin", "oct" and
"hex" operations, could control the stack printing routine.
"roll" and "rolld" could be implemented using Perl's splice operator.
== Conclusion
The posted solutions had a variety of strategies for re-using code,
and a bunch of good ideas for extensions. They're all worth checking
out. Thanks again to those who submitted solutions.
CPAN has several modules regarding RPN calculators. Math::RPN
implements an rpn() routine that takes one or more terms in a
comma-delimited string, and returns the result, supporting several
dozen operations. Parse::RPN is similar to Math::RPN, with many more
operations supported. Tk::Calculator::RPN::HP is a Perl/Tk widget
that implements an RPN calculator based on many of the Hewlett-Packard
calculators.
http://search.cpan.org/~fdulau/Parse-RPN-2.7/RPN.pm
http://search.cpan.org/~owen/Math-RPN-1.08/RPN/RPN.pm
http://search.cpan.org/~lusol/Tk-Calculator-RPN-HP-0.6/Tk/Calculator/RPN/HP.pm
The interactive terminal-based RPN calculator I've been using for a
while is called "vc", and is written in Perl. It includes vector
math, undo/redo, variables and macro programmability.
http://perl.foundries.sourceforge.net/article.pl?sid=02/10/19/0132232&mode=thread&tid=167
-- Dan
More information about the NewOrleans-pm
mailing list