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 = )) { # ... } 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