[Kc] Perl Quiz of the Week #25 (RPN calculator)

[Garrett Goebel]

IMPORTANT: Please do not post solutions, hints, or other spoilers
        until at least 60 hours after the date of this message.
        Thanks.

IMPORTANTE: Por favor, no enviis soluciones, pistas, o cualquier otra
        cosa que pueda echar a perder la resolucin del problema hasta
        que hayan pasado por lo menos 60 horas desde el envo de este
        mensaje. Gracias.

IMPORTANT: S'il vous plat, attendez au minimum 60 heures aprs la
        date de ce message avant de poster solutions, indices ou autres
        rvlations. Merci.

WICHTIG: Bitte schicken Sie keine Lsungen, Tipps oder Hinweise fr
        diese Aufgabe vor Ablauf von 60 Stunden nach dem Datum dieser
        Mail. Danke.

VNIMANIE: Pozhalujsta ne shlite reshenija, nameki na reshenija, i
        voobshe lyubye podskazki v techenie po krajnej mere 60 chasov
        ot daty etogo soobshenija.  Spasibo.

Qing3 Zhu4Yi4: Qing3 Ning2 Deng3Dao4 Jie1Dao4 Ben3 Xin4Xi2 Zhi1Hou4 60
        Xiao3Shi2, Zai4 Fa1Biao3 Jie3Da2, Ti2Shi4, Huo4 Qi2Ta1 Hui4
        Xie4Lou4 Da2An4 De5 Jian4Yi4.  Xie4Xie4.

UWAGA: Prosimy nie publikowac rozwiazan, dodatkowych  badz pomocniczych
	informacjii przez co najmniej 60 godzin od daty tej wiadomosci.
	Dziekuje.

----------------------------------------------------------------

We're used to seeing arithmetic expressions written in "infix notation,"
where an operator appears between its two operands: "3 + 5".  Traditional
calculators use an entry method based on this notation, where the first
number is entered, followed by the operator, then the second number, and
finally a key to tell the calculator to produce the result: "3", "+", "5",
"=".  The display of an infix calculator typically shows the last number
entered, or the result of the last calculation.

In the 1970's, Hewlett-Packard introduced a pocket calculator using Reverse
Polish Notation (RPN), also known as postfix notation.  In postfix notation,
the operator appears after its operands: "3 5 +".
This expression would be keyed into an RPN calculator as follows: "3",
"Enter", "5", "Enter", "+".  The calculator stores the values on a stack as
they are entered; when the operator is keyed, the values are popped from the
stack, the operation is performed, and the result is pushed back onto the
stack.  The display of an RPN calculator typically shows the top few levels
of the stack for easy manipulation of multiple values.

RPN calculators are particularly useful for evaluating expressions with
multiple parts, such as "(3 + 5) * 2 / (2 + 3)".  With a typical infix
calculator, the results of one part would have to be remembered or written
down so the calculator can be cleared to calculate the other part, then
finally combined with the first part.  (Most infix calculators provide a
"memory" feature that stores one value for later
recall.)  With an RPN calculator, the expression could be keyed as it would
be written in postfix notation: "3 5 + 2 * 2 3 + /".

For this quiz, we'll implement an interactive RPN calculator.

The calculator will accept lines of input on standard input.  Each line will
contain zero or more terms separated by spaces.  A term may be a number or
an operator.  Each term will be evaluated in order, from left to right.  If
the term is a number, the value will be pushed onto the stack.  If the term
is an operator, the operation will be performed.  After a line of input has
been processed, the stack will be printed to standard output in reverse
order, with the top of the stack appearing last.

The following example shows lines of user input after the "> " prompt.
Stack printouts use numbered lines, with 0 representing the top of the
stack.

The number 3 is entered, pushing it onto an empty stack:

  > 3
  0: 3

The number 5 is entered, resulting in a stack of two values:

  > 5
  1: 3
  0: 5

The plus operator takes the top two elements off of the stack, adds them
together, and puts the result onto the stack:

  > +
  0: 8

A number and an operator both appear on the same line.  The number is pushed
onto the stack, and the operator is performed, in this case 8 * 2.

  > 2 *
  0: 16

Two numbers are pushed, followed by two operators.  The first operator, "+",
pops the 3 and the 2, adds them together, then pushes the result (5) onto
the stack.  The second operator, "/", pops the 5 that was just pushed and
the 16 that was already on the stack, and performs the division.  (In infix
notation, this division would be written as "16 / 5".)

  > 2 3 + /
  0: 3.2

Operators that require one value ("unary operators") take the topmost
element off the stack, perform their function on the value, and push the
result back onto the stack.  Operators that require two values ("binary
operators") take the top two elements off the stack and perform their
function using the "earliest" value as the first term and the "latest" value
as the second.  For example, "20 5 /" pushes 20, pushes 5 (resulting in the
stack 1: 25, 0: 5), then pops 5, pops 20, divides 20 by 5, then pushes the
result (4) back onto the stack.

If there are not enough elements on the stack to perform an operation, the
calculator should report an error and stop processing the line.

The calculator should support at least the following operators, whose
functions are similar to those in Perl: + - * / % **

The calculator should support the following stack manipulation commands:

  drop    pops the top element and discards it.
  swap    swaps the 0th (top) and 1st elements in the stack.
  clear   removes all values from the stack.
  dup     duplicate the top element, push it onto the stack

This specification lends itself easily to extension.  Feel free to add
features you think might make the calculator more useful.  A few
ideas:

* Support for additional Perl builtin operations: 
        & | ~ abs int cos sin exp log sqrt atan2

* Accept numbers entered in hexadecimal beginning in "0x", binary
  beginning in "0b", or octal beginning in "0".

* Support different display modes for how the stack is printed, with
  commands to switch modes.  "dec", "bin", "oct" and "hex" would
  switch the display to decimal, binary, octal or hexadecimal,
  respectively.  (These commands do not affect the contents of the
  stack.)

* An "N roll" command, which moves the Nth element in the stack to the
  0th position, pushing the other elements up (where N is a value
  popped from the top of the stack).  It is an error if there are not
  N elements in the stack.  For example:

   > 10 20 30 40 50
   4: 10
   3: 20
   2: 30
   1: 40
   0: 50

   > 2 roll
   4: 10
   3: 20
   2: 40
   1: 50
   0: 30

  Similarly, "N rolld" would move the 0th element in the stack to the
  Nth position, dropping the other elements down.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mail.pm.org/archives/kc/attachments/20040929/befdc16d/attachment.htm