Could this Postfix notation interpreter (reverse varnish) Python be more efficient and accurate?

Question

Here is the Postfix Python notification interpreter that uses the stack to evaluate expressions. Is it possible to make this function more efficient and accurate?

#!/usr/bin/env python import operator import doctest class Stack: """A stack is a collection, meaning that it is a data structure that contains multiple elements. """ def __init__(self): """Initialize a new empty stack.""" self.items = [] def push(self, item): """Add a new item to the stack.""" self.items.append(item) def pop(self): """Remove and return an item from the stack. The item that is returned is always the last one that was added. """ return self.items.pop() def is_empty(self): """Check whether the stack is empty.""" return (self.items == []) # Map supported arithmetic operators to their functions ARITHMETIC_OPERATORS = {"+":"add", "-":"sub", "*":"mul", "/":"div", "%":"mod", "**":"pow", "//":"floordiv"} def postfix(expression, stack=Stack(), operators=ARITHMETIC_OPERATORS): """Postfix is a mathematical notation wherein every operator follows all of its operands. This function accepts a string as a postfix mathematical notation and evaluates the expressions. 1. Starting at the beginning of the expression, get one term (operator or operand) at a time. * If the term is an operand, push it on the stack. * If the term is an operator, pop two operands off the stack, perform the operation on them, and push the result back on the stack. 2. When you get to the end of the expression, there should be exactly one operand left on the stack. That operand is the result. See http://en.wikipedia.org/wiki/Reverse_Polish_notation >>> expression = "1 2 +" >>> postfix(expression) 3 >>> expression = "5 4 3 + *" >>> postfix(expression) 35 >>> expression = "3 4 5 * -" >>> postfix(expression) -17 >>> expression = "5 1 2 + 4 * + 3 -" >>> postfix(expression, Stack(), ARITHMETIC_OPERATORS) 14 """ if not isinstance(expression, str): return for val in expression.split(" "): if operators.has_key(val): method = getattr(operator, operators.get(val)) # The user has not input sufficient values in the expression if len(stack.items) < 2: return first_out_one = stack.pop() first_out_two = stack.pop() operand = method(first_out_two, first_out_one) stack.push(operand) else: # Type check and force int try: operand = int(val) stack.push(operand) except ValueError: continue return stack.pop() if __name__ == '__main__': doctest.testmod() 

Answer 1

General recommendations:

• Avoid unnecessary type checks and rely on default exception behavior.
• has_key() has long been deprecated in favor of the in operator: use this instead.
• Profile your program before trying to optimize performance. To run zero-effort profiles of any given code, simply run: python -m cProfile -s cumulative foo.py

Specific points:

• list makes a good stack out of the box. In particular, it allows you to use the fragment notation ( tutorial ) to replace the pop / pop / append dance in one step.
• ARITHMETIC_OPERATORS can refer to operational implementations directly, without the indirectness of getattr .

Putting it all together:

 ARITHMETIC_OPERATORS = { '+': operator.add, '-': operator.sub, '*': operator.mul, '/': operator.div, '%': operator.mod, '**': operator.pow, '//': operator.floordiv, } def postfix(expression, operators=ARITHMETIC_OPERATORS): stack = [] for val in expression.split(): if val in operators: f = operators[val] stack[-2:] = [f(*stack[-2:])] else: stack.append(int(val)) return stack.pop() 

Answer 2

Lists can be used directly as stacks:

 >>> stack = [] >>> stack.append(3) # push >>> stack.append(2) >>> stack [3, 2] >>> stack.pop() # pop 2 >>> stack [3] 

You can also put operational functions directly in your ARITHMETIC_OPERATORS dict:

 ARITHMETIC_OPERATORS = {"+":operator.add, "-":operator.sub, "*":operator.mul, "/":operator.div, "%":operator.mod, "**":operator.pow, "//":operator.floordiv} 

then

 if operators.has_key(val): method = operators[val] 

The goal is not to make things more effective (although this may have such an effect), but to make them more obvious to the reader. Get rid of unnecessary levels of indirection and wrappers. This will make your code less confusing. It will also provide a (trivial) performance improvement, but don't believe that if you don't measure it.

By the way, using lists as stacks is pretty common idiomatic Python.

Answer 3

You can directly match the operators: {"+": operator.add, "-": operator.sub, ...} . It is simpler, does not require unnecessary getattr , and also allows you to add additional functions (without breaking the operator module). You can also delete several temporary variables that are used only once:

 rhs, lhs = stack.pop(), stack.pop() stack.push(operators[val](lhs, rhs)). 

In addition (less performance and more style issues, it is also subjective), I would probably not have handled errors at all in a loop and wrapped it in one try block with an except KeyError ("Unknown operand"), except IndexError block (empty stack),...

But more precisely? Does this give the wrong results?