Python sol'n to QOTW #25 "RPN calculator"

Here's my Python solution to the RPN calculator.  The implementation
uses a dispatch table.  All handlers get access to the calculator,
in case they want to manipulate the stack.  I have an adapter class
to make it easy to add normal functions (unary, binary, and one
ternary -- pow(x,y,z) == x**y % z) .  My tokenizer is easier than
the perl ones because I can let Python do the work for me.  An
advantage in this case to strong type checking.  ;)

What's unusual about mine is that I support strings ('+ is the string
"+" instead of the command "+", 'cos is a string, etc.  But note
that the word cannot contain whitespace.

I also support simple macro-like functions and an if/then/else
statement.  Someone asked why roll/rolld were useful.  I have
a few functions which use them.  They are needed to get a number
from further up the stack into operating range.

To make the 'if' and 'def'ine statements easier to input, I
introduced a simple input scheme which disables interpretation
while those are being defined.  Otherwise I would need to quote
the words in the middle and that looked ugly.

Here it is in action.

Simple RPN calculator.
Use '?' to get a list of commands, 'quit' to exit
 > ?
'!' '%' '&' '*' '**' '+' '-' '/' '//' '<' '<<' '<=' '==' '>' '>=' '>>'  
'?' '^' 'abs' 'acos' 'asin' 'atan2' 'bin' 'ceil' 'clear' 'cos' 'cosh'  
'dec' 'def' 'degrees' 'drop' 'dup' 'e' 'enddef' 'endif' 'exec' 'exp'  
'fib' 'float' 'floor' 'hex' 'hypot' 'if' 'int' 'log' 'log10' 'nop'  
'oct' 'pi' 'pow' 'quit' 'radians' 'roll' 'rolld' 'sin' 'sinh' 'sqrt'  
'swap' 'troff' 'tron' '|' '~'


 > 2 4 5 ** **
0:  
179769313486231590772930519078902473361797697894230657273430081157732675 
805500963132708477322407536021120113879871393357658789768814416622492847 
430639474124377767893424865485276302219601246094119453082952085005768838 
150682342462881473913110540827237163350510684586298239947245938479716304 
835356329624224137216

 > hex
0:  
0x1000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
000000000000000000000000000000000000000000000000000000000000000000000000 
0000000000000000000000000000000000000000000

 > 169 ! /
0: 4210.97328754

 > dec
0: 4210.97328754

 > dup 0xf swap 1 -
2: 4210.97328754
1: 15
0: 4209.97328754

 > sqrt
2: 4210.97328754
1: 15
0: 64.8843069435

 > clear e
0: 2.71828182846

 > log
0: 1.0

 > exp
0: 2.71828182846

 > drop 81 sqrt
0: 9.0

 > 3 4 atan2
1: 9.0
0: 0.643501108793

 > degrees
1: 9.0
0: 36.8698976458

 > 0b100001 | 0b101001
Processing stopped with '|' because: unsupported operand type(s) for |:  
'float' and 'int'
2: 9.0
1: 36.8698976458
0: 33

 > clear 0b100001 0b101001 |
0: 41

 > bin
0: 0b101001

 > drop 0b010001 0b101001 &
0: 0b1

 > drop dec

             Here's an example if an if statement and using a string

 > clear 25 if dup sqrt int 2 ** == then 'square else 'not-square endif
0: square

 > clear 80 if dup sqrt int 2 ** == then 'square else 'not-square endif
0: not-square

 > clear

            Turn that into a function

 > def is-square if dup sqrt int 2 ** == then 'square else 'not-square  
endif enddef

 > 80 is-square
0: not-square

 > clear 81 is-square
0: square

 > clear 10000 is-square
0: square


             No loops, but I can do functional programming

 > # recusive solution to drop the top N elements

 > def dropN if dup 0 > then 1 - swap drop dropN else drop endif enddef

 > 101 102 103 104 105 106 107 108 109 110
9: 101
8: 102
7: 103
6: 104
5: 105
4: 106
3: 107
2: 108
1: 109
0: 110

 > 5 dropN
4: 101
3: 102
2: 103
1: 104
0: 105

These new functions are included in the available functions list
 > clear

 > ?
'!' '%' '&' '*' '**' '+' '-' '/' '//' '<' '<<' '<=' '==' '>' '>=' '>>'  
'?' '^' 'abs' 'acos' 'asin' 'atan2' 'bin' 'ceil' 'clear' 'cos' 'cosh'  
'dec' 'def' 'degrees' 'drop' 'dropN' 'dup' 'e' 'enddef' 'endif' 'exec'  
'exp' 'fib' 'float' 'floor' 'hex' 'hypot' 'if' 'int' 'is-square' 'log'  
'log10' 'nop' 'oct' 'pi' 'pow' 'quit' 'radians' 'roll' 'rolld' 'sin'  
'sinh' 'sqrt' 'swap' 'troff' 'tron' '|' '~'

      Here's a more complicated program (shown without the prompts)
      It finds the roots of a quadratic equation given a b c on the stack

# Compute the discriminant.  Stack must have a b c
def discriminant
   swap dup 2 ** 3 roll dup 4 rolld 3
   roll dup 3 rolld 4 * * -
enddef

# Given a b c, compute both roots.
# If it is complex, put the string 'imaginary' on the stack
# but do not touch a b c .  Otherwise consume a b c
# and replace them with the two solutions.
def roots
   discriminant
   if dup 0 < then drop 'imaginary else
     sqrt                # we have a b c d
     swap drop           # a b d
     2 roll 2 * dup      # b d 2*a 2*a
     2 roll swap / dup   # b 2*a d/(2*a) d/(2*a)
     3 rolld 3 rolld     # d/(2*a) d/(2*a) b 2*a
     / -1 * dup 3 rolld  #  -b/(2*a) d/(2*a) d/(2*a) -b/(2*a)
     + 2 rolld -         # (-b+d)/(2*a)   (-b-d)/(2*a)
   endif
enddef


 > -1 2 3 roots
1: -1.0
0: 3.0

 > clear 1 2 3 roots
3: 1
2: 2
1: 3
0: imaginary

 > clear 2 8 3 roots
1: -0.418861169916
0: -3.58113883008

 > clear 2 -4 2 roots
1: 1.0
0: 1.0

 >

Finally, it uses the platform's readline library if available.

					Andrew
					dalke-DxsMES/F/[email protected]

# Python solution to Perl Quiz of the Week #25 "RPN Calculator"
#  by Andrew Dalke < dalke @ dalke scientific . com >
# Contributed to the public domain Oct. 1, 2004
#
# The calculator is simple.  As words come in, either process
# them using entries in the dispatch table (if a string)
# or append to the stack.
#
# The handlers in the dispatch table are free to manipulate
# the calculator.  Usually they just modify the stack.  They
# may also change the function used to convert stack elements
# for the different display modes.
#
# Note: the oct, hex, and bin display modes only work on
# integers and not on floats.
#
# The 'SimpleFuncHandler' is an adapter to support existing
# Python functions.
#


import math, inspect, sys, operator

import readline  # enable readline support for raw_input

# Wrapper for calling a built-in function.
#   Get the args from the stack and call.
#   Append the result to the stack.
#   If there was a failure, revert the args to the stack
class SimpleFuncHandler:
     def __init__(self, func, nargs, name):
         self.func = func
         self.name = name
         self.nargs = nargs

     def __call__(self, rpncalc):
         # Only remove elements from the stack when the call succeeds
         if len(rpncalc.stack) < self.nargs:
             raise AssertionError(
                 "%s takes %d parameters, only %d available" % (
                 self.name, self.nargs, len(rpncalc.stack)))

         if self.nargs == 0:
             rpncalc.stack.append(self.func())
         else:
             terms = rpncalc.stack[-self.nargs:]
             result = self.func(*terms)
             rpncalc.stack[-self.nargs:] = [result]


class RPNCalc:
     def __init__(self):
         self.stack = []
         self.handlers = {}
         self.display_mode = display_dec
         self.do_quoting = 0
         self.stop_word = ""
         self.trace = 0

     def quote_until(self, stop_word):
         self.do_quoting = 1
         self.stop_word = stop_word

     def run(self, word = None):
         if word is None:
             word = self.stack.pop(-1)
         if word in self.handlers:
             if self.trace:
                 print "run", word, "with", self.stack[-5:], " --> ",
             self.handlers[word](self)
             if self.trace:
                 print self.stack[-5:]
         else:
             raise TypeError("unknown command %r" % (word,))

     def process(self, word):
         if word == "!'":  # stop quoting
             self.do_quoting = 0
             return

         if isinstance(word, basestring):
             if self.do_quoting:
                 if word == self.stop_word:
                     self.do_quoting = 0
                     self.run(word)
                 else:
                     self._append(word)
             else:
                 if word.startswith("'"):
                     self._append(word[1:])
                 else:
                     self.run(word)
         else:
             self._append(word)

     def _append(self, word):
         self.stack.append(word)
         if self.trace:
             print "Append", word, "to get", self.stack[-5:]

     def add_handler(self, handler, name = None):
         if name is None:
             name = handler.__name__
         self.handlers[name] = handler

     def display(self, outfile):
         for i, val in zip(range(len(self.stack)-1, -1, -1),
                           self.stack):
             print >>outfile, "%d: %s" % (i, self.display_mode(val))

# Some display functions (for 'dec', 'hex', 'bin' and 'oct' modes)

def display_dec(arg):
     return str(arg)

def display_hex(arg):
     if isinstance(arg, int):
         return hex(arg)
     elif isinstance(arg, long):
         return hex(arg)[:-1]    # remove the terminal 'L'
     return str(arg)

def display_oct(arg):
     if isinstance(arg, int):
         return oct(arg)
     elif isinstance(arg, long):
         return oct(arg)[:-1]    # remove the terminal 'L'
     return str(arg)

# Python doesn't have a 'bin' function.  Make one based on hex.
_hex2bin = {
     "0": "0000", "1": "0001", "2": "0010", "3": "0011", "4": "0100",
     "5": "0101", "6": "0110", "7": "0111", "8": "1000", "9": "1001",
     "a": "1010", "b": "1011", "c": "1100", "d": "1101", "e": "1110",
     "f": "1111"}

def bin(x):
     s = hex(x)
     if s[-1:] == "L":
         s = s[:-1]
     t = "".join(map(_hex2bin.__getitem__, s[2:]))
     # Remove any leading 0s.  If none, this returns -1
     # which is exactly what's needed to return "0b0"
     i = t.find("1")
     return "0b" + t[i:]

def display_bin(arg):
     if isinstance(arg, int) or isinstance(arg, long):
         return bin(arg)
     return str(arg)

class StackDefinedHandler:
     def __init__(self, commands):
         self.commands = commands
     def __call__(self, rpncalc):
         for command in self.commands:
             rpncalc.process(command)


def _rfind(stack, name, i = None):
     if i is None:
         i = len(stack)-1
     while i >= 0:
         if stack[i] == name:
             return i
         i = i - 1
     raise TypeError("Could not find %r in stack" % (name,))

# Kind of a hack.  Used to get a list of all the stack ops
_old_globals = globals().keys()

############# Start of the stack functions

# quit
def quit(rpncalc):
     sys.exit(0)

# drop    pops the top element and discards it.
def drop(rpncalc):
     del rpncalc.stack[-1]

# swap    swaps the 0th (top) and 1st elements in the stack.
def swap(rpncalc):
     stack = rpncalc.stack
     stack[-2], stack[-1] = stack[-1], stack[-2]

# clear   removes all values from the stack.
def clear(rpncalc):
     del rpncalc.stack[:]

# dup     duplicate the top element, push it onto the stack
def dup(rpncalc):
     rpncalc.stack.append(rpncalc.stack[-1])

# roll     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.
def roll(rpncalc):
     i = rpncalc.stack.pop(-1)
     if not isinstance(i, int):
         raise TypeError("can only roll with integers")
     if i < 0:
         raise TypeError("can not roll using negative numbers")
     if i == 0:
         return
     if i >= len(rpncalc.stack):
         raise TypeError("roll value larger than the stack")
     i = -i-1
     val = rpncalc.stack.pop(i)
     rpncalc.stack.append(val)

# rolld   "N rolld" would move the 0th element in the stack to the
# Nth position, dropping the other elements down.
def rolld(rpncalc):
     i = rpncalc.stack.pop(-1)
     if not isinstance(i, int):
         raise TypeError("can only rolld with integers")
     if i < 0:
         raise TypeError("can not rolld using negative numbers")
     if i == 0:
         return
     if i >= len(rpncalc.stack):
         raise TypeError("rolld value larger than the stack")
     i = -i-1
     rpncalc.stack.insert(i, rpncalc.stack[-1])
     del rpncalc.stack[-1]


def dir_(rpncalc):
     ops = rpncalc.handlers.keys()
     ops.sort()
     print " ".join(map(repr, ops))
dir_.__name__ = "?"

# suffix with "_" because hex and oct are builtins
def dec_(rpncalc):
     rpncalc.display_mode = display_dec
dec_.__name__ = "dec"

def bin_(rpncalc):
     rpncalc.display_mode = display_bin
bin_.__name__ = "bin"

def oct_(rpncalc):
     rpncalc.display_mode = display_oct
oct_.__name__ = "oct"

def hex_(rpncalc):
     rpncalc.display_mode = display_hex
hex_.__name__ = "hex"

# Use the name of the top item as the command to run
def exec_(rpncalc):
     word = rpncalc.stack.pop(-1)
     rpncalc.run(word)
exec_.__name__ = "exec"

def nop(rpncalc):
     pass

def if_(rpncalc):
     rpncalc.stack.append("if")
     rpncalc.quote_until("endif")
if_.__name__ = "if"

def endif(rpncalc):
     try:
         else_pos = _rfind(rpncalc.stack, "else")
     except TypeError:
         else_pos = None
     then_pos = _rfind(rpncalc.stack, "then", else_pos)
     if_pos = _rfind(rpncalc.stack, "if", then_pos)
     if_commands = rpncalc.stack[if_pos+1:then_pos]
     then_commands = rpncalc.stack[then_pos+1:else_pos]
     if else_pos is not None:
         else_commands = rpncalc.stack[else_pos+1:]
     else:
         else_commands = []

     del rpncalc.stack[if_pos:]
     for command in if_commands:
         rpncalc.process(command)
     val = rpncalc.stack.pop(-1)
     if val:
         for command in then_commands:
             rpncalc.process(command)
     else:
         for command in else_commands:
             rpncalc.process(command)

def def_(rpncalc):
     rpncalc.stack.append("def")
     rpncalc.quote_until("enddef")
def_.__name__ = "def"

def enddef(rpncalc):
     def_pos = _rfind(rpncalc.stack, "def")
     name_pos = def_pos + 1
     if name_pos >= len(rpncalc.stack):
         raise TypeError("No name given to new function")
     name = rpncalc.stack[name_pos]
     commands = rpncalc.stack[name_pos+1:]
     del rpncalc.stack[def_pos:]
     rpncalc.handlers[name] = StackDefinedHandler(commands)


def tron(rpncalc):
     rpncalc.trace = 1

def troff(rpncalc):
     rpncalc.trace = 0


############## end of stack function definitions

stack_funcs = dict([(k, v) for (k, v) in globals().items()
                              if (k not in _old_globals) and  
callable(v)])


del _old_globals, k, v

#### some extra functions

def factorial(n):
     if n < 1:
         raise TypeError("can only find factorials of positive numbers")
     if not (isinstance(n, int) or isinstance(n, long)):
         raise TypeError("can only find factorials of integers")
     fact = 1L
     while n > 1:
         fact *= n
         n -= 1
     return fact

def fib(n):
     if n < 1:
         raise TypeError("can only find fib(n) for n > 1")
     if not (isinstance(n, int) or isinstance(n, long)):
         raise TypeError("can only find fib(n) of integers")
     if n == 1:
         return 1
     if n == 2:
         return 1
     x = 1L
     y = 1L
     while n > 2:
         x, y = y, x+y
         n -= 1
     return y

####

# Let Python do the hard work of figuring out if the
# number is a number type.
def convert_type(s):
     # Is it a binary value?  Python doesn't understand
     # the "0b" notation so handle it ourselves.
     if s[:2] == "0b":
         return int(s[2:], 2)

     # Is it an integer?
     try:
         return int(s, 0)
     except ValueError:
         pass

     # A float?
     try:
         return float(s)
     except ValueError:
         pass

     # Unsupported data type.  Treat as a string
     return s


def main():
     rpncalc = RPNCalc()

     def addf(func, nargs = None, name = None):
         if nargs is None:
             nargs = len(inspect.getargspec(func)[0])
         if name is None:
             name = func.__name__
         rpncalc.add_handler(SimpleFuncHandler(func, nargs, name), name)

     addf(operator.add, 2, "+")
     addf(operator.sub, 2, "-")
     addf(operator.mul, 2, "*")
     addf(operator.truediv, 2, "/")
     addf(operator.floordiv, 2, "//")
     addf(pow, 2, "**")
     addf(pow, 3, "pow")           # x**y mod z
     addf(abs, 1, "abs")
     addf(operator.gt, 2, ">")
     addf(operator.ge, 2, ">=")
     addf(operator.eq, 2, "==")
     addf(operator.le, 2, "<=")
     addf(operator.lt, 2, "<")
     addf(operator.mod, 2, "%")
     addf(operator.lshift, 2, "<<")
     addf(operator.rshift, 2, ">>")
     addf(operator.and_, 2, "&")
     addf(operator.or_, 2, "|")
     addf(operator.xor, 2, "^")
     addf(operator.invert, 1, "~")

     addf(int, 1)
     addf(float, 1)
     addf(lambda :math.pi, 0, "pi")
     addf(lambda :math.e, 0, "e")
     addf(math.cos, 1)
     addf(math.sin, 1)
     addf(math.cosh, 1)
     addf(math.sinh, 1)
     addf(math.exp, 1)
     addf(math.log, 1)
     addf(math.log10, 1)
     addf(math.sqrt, 1)
     addf(math.atan2, 2)
     addf(math.asin, 1)
     addf(math.acos, 1)
     addf(math.radians, 1)
     addf(math.degrees, 1)
     addf(math.ceil, 1)
     addf(math.floor, 1)
     addf(math.hypot, 2)

     addf(factorial, name = "!")
     addf(fib)

     add = rpncalc.add_handler
     for k, v in stack_funcs.items():
         rpncalc.add_handler(v)

     print "Simple RPN calculator."
     print "Use '?' to get a list of commands, 'quit' to exit"
     while 1:
         try:
             inp = raw_input("> ")
         except EOFError:
             break
         i = inp.find("#")
         if i != -1:
             inp = inp[:i]
         words = inp.split()
         for word in words:
             word = convert_type(word)
             try:
                 rpncalc.process(word)
             except SystemExit:
                 raise
             except:
                 print "Processing stopped with %r because: %s" % (
                     word, sys.exc_info()[1])
                 break
         if not rpncalc.do_quoting:
             # we're defining a function or if statement
             rpncalc.display(sys.stdout)
             print

if __name__ == "__main__":
     main()