23 02/11
01:03

Reverse Polish Notation Evaluation in Python

This introduction is followed by some Python code (function evaluate_postfix_expr) to evaluate expressions (only integers, but may be extended with ease) in Reverse Polish Notation (RPN). Some simple tests are also included in the bundle.

I agree it’s a little useless, but I thought it might be useful for someone (CS students maybe?). If you want to examine the stack in each iteration you only have to turn debugging on. That can be accomplished by changing logging.INFO to logging.DEBUG (line 7).

Copy, distribute or do whatever you want with it. It’s released in the public domain.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72

#!/usr/bin/env python
 
import logging
import re
import unittest
 
logging.basicConfig(level=logging.INFO)
 
operators_table = {'+': int.__add__, 
             '-': int.__sub__,
             '*': int.__mul__,
             '/': int.__div__,
             '^': int.__pow__}
 
class ExpressionError(Exception):
    def __init__(self, message):
        self._message = "Expression error: %s" % message
    def _get_message(self): 
        return self._message
    message = property(_get_message)
 
class TestEvaluation(unittest.TestCase):
    def test_correct(self):
        self.assertEqual(666, evaluate_postfix_expr("666"))
        self.assertEqual(2+3-6, evaluate_postfix_expr("2 3 + 6 -"))
        self.assertEqual(2*3+4, evaluate_postfix_expr("2 3 * 4 +"))
        self.assertEqual(2*(3+4), evaluate_postfix_expr("2 3 4 + *"))
        self.assertEqual(3**4, evaluate_postfix_expr("3   3  *     3  *      3 *"))
        self.assertEqual((7/2)**4, evaluate_postfix_expr("7 2 / 4 ^"))
        self.assertEqual((2**3)**4, evaluate_postfix_expr("2 3 ^ 4 ^"))
        self.assertEqual(5+((1+2)*4)-3, evaluate_postfix_expr("5 1 2 + 4 * 3 - +"))
 
    def test_malformed(self):
        self.assertRaises(ExpressionError, evaluate_postfix_expr, "+")
        self.assertRaises(ExpressionError, evaluate_postfix_expr, "2 +")
        self.assertRaises(ExpressionError, evaluate_postfix_expr, "+ 2 2")
        self.assertRaises(ExpressionError, evaluate_postfix_expr, "2 2")
        self.assertRaises(ExpressionError, evaluate_postfix_expr, "2 2 + -")
        self.assertRaises(ExpressionError, evaluate_postfix_expr, "a 2 -")
 
def evaluate_postfix_expr(expr):
    atoms = re.split(r"\s+", expr)
    stack = [] 
    for atom in atoms:
        if atom in ["+", "-", "*", "/", "^"]:
            try:
                op2 = stack.pop()
                op1 = stack.pop()
            except IndexError:
                raise ExpressionError("Too few operands (unbalanced)")
            logging.debug("Calculating %d %s %d" % (op1, atom, op2))
            atom = operators_table[atom](op1, op2)
        else:
            try:
                atom = int(atom)
            except ValueError:
                raise ExpressionError("Unable to parse '%s' as integer" % atom)
 
        try:
            stack.append(atom)
        except MemoryError:
            raise ExpressionError("Too long expression")
 
        logging.debug("Pushed element %d. Stack status: %s" % (atom, stack))
 
    if len(stack) == 1:
        return stack.pop()
    else:
        raise ExpressionError("Too many operands (unbalanced)")
 
if __name__ == "__main__":
    unittest.main()

08 09/06
14:56

Rolle, another mathematical key

Breaking news: Vista could divide by zero in its final release!.

Well, now serious stuff, like few posts ago, time to mention another mathematical milestone:

Let f be differentiable on the open interval (a,b) and continuous on the closed interval [a,b]. If f(a)==f(b), then there is at least one point c in (a,b) where f’(c)==0

That’s all folks!

23 03/06
21:28

Fermat’s last theorem

Time to remember one of the most famous mathematical milestone:

When n > 2 there aren’t non-zero integer solutions for x, y and z for the equation:

x^n + y^n = z^n

This theorem was enunciated near 1665 and demonstrated in 1995 by Andrew Wiles, sweets that the science gives to the humanity.