8
\$\begingroup\$

I created this small Python calculator after abstaining from writing code for a while now. I would love seasoned programmers input.

#!/usr/bin/env python

" A Simple calculator "

class Calculator(object):
    """ Example input:
        expression: (12+4)*2^4-(10-3*(15/5))
        steps:
        1) compile it to a list of ops and numbers: [ [12,+,4],*,2,^,4,-,[10,-,3,*,[15,/,5]] ]
        2) calculate starting with the highest operators first:

        [ [12, +, 5], *, 16, -, [10,-,3,*,[15,/,5]] ]
        [ 17, *, 16, -, [10,-,3,*,3] ]
        [ 17, *, 16, -, [10-9] ]
        [ 17, *, 16, -, 1]
        [ 272, -, 1 ]
        [ 271 ]

        TODO:
          * add floating point support

    """
    _stack = []

    " Flag that signfies if it's the first character in the expression "
    INITIAL = True

    " exit perenthesis "
    EXIT_PE = False
    " in number "
    IN_NU = False
    " in operator "
    IN_OP = False

    OPERATORS = ('+', '-', '*', '/', '^')
    OP_ORDER = (('^',), ('*', '/'), ('+', '-'))

    def compile(self, input_eq):
        for c in input_eq:
            try:
                " check if its a number "
                current = int(c)
                self.IN_OP = False
                " if it's a new digit to a previous number "
                if self.IN_NU:
                    " add it to the previous number "
                    self._add_new_num(current)
                else:
                    " it's a new number add it to stack "
                    self._add_new_num(current)
                    self.IN_NU = True
            except ValueError:
                self.IN_NU = False
                " if it's an operator "
                if c in self.OPERATORS:
                    if not self._stack:
                        raise Exception("You can't start an expression with an operator")
                    if self.IN_OP:
                        raise Exception("illegal expression")
                    else:
                        self._append_element(c)
                        self.IN_OP = True
                elif c == '(':
                    self._add_new_perentheses()
                    self.IN_OP = True
                elif c == ')':
                    self.EXIT_PE = True
                    self.IN_OP = False
                else:
                    raise Exception("Bad input")


            if self.INITIAL:
                self.INITIAL = False

    def _get_last_position(self):
        " Returns the last inner most list in the stack "

        list_ref = list_prev = self._stack
        try:
            " While there's a list "
            while list_ref[-1] or list_ref[-1] == []:
                if isinstance(list_ref[-1], list):
                    " make a reference to the list "
                    list_prev = list_ref
                    list_ref = list_ref[-1]
                else:
                    break

            if self.EXIT_PE == True:
                self.EXIT_PE = False
                return list_prev
            else:
                self.EXIT_PE = False
                return list_ref
        except IndexError:
            if self.EXIT_PE == True:
                self.EXIT_PE = False
                return list_prev
            else:
                self.EXIT_PE = False
                return list_ref

    def _append_element(self, el):
        last_pos = self._get_last_position()
        last_pos.append(el)

    def _add_new_num(self, num):
        " if its the first character in an expression "
        if not self._stack or self._get_last_position() == []:
            self._append_element(num)
        else:
            prev_c = self._get_last_position()[-1]
            " check if previous char is a number "
            is_int = isinstance(prev_c, int)

            if is_int:
                self._add_to_previous_num(num, self._stack)
            elif prev_c in self.OPERATORS:
                self._append_element(num)
            else:
                is_list = isinstance(self._stack[-1], list)
                " if it's a list search the last element in the list's children "
                if is_list:
                    list_ref = self._get_last_position()
                    self._add_to_previous_num(num, list_ref)
                else:
                    raise Exception("something is broken")

    def _add_to_previous_num(self, num, stack):
        try:
            last_pos = self._get_last_position()
            last_pos[-1] = last_pos[-1]*10+num
        except IndexError:
            last_pos.append(num)

    def _add_new_perentheses(self):
        last_pos = self._get_last_position()
        last_pos.append([])

    def calculate(self, expr):
        self.compile(''.join(expr.split()))

        result = self._rec_calc(self._stack)
        " initialize the stack "
        self._stack = []

        return result

    def _rec_calc(self, stack):
        while len(stack) > 1:
            for op in xrange(len(self.OP_ORDER)):
                for el in xrange(len(stack)):
                    try:
                        if isinstance(stack[el], list):
                            result = self._rec_calc(stack[el])
                            del stack[el]
                            stack.insert(el, result)
                        elif stack[el] in self.OP_ORDER[op]:
                            result = self._calc_binary(stack, el, stack[el])
                            " delete all three elements that were used in the binary operation "
                            del stack[el-1]
                            del stack[el-1]
                            del stack[el-1]
                            stack.insert(el-1, result)
                    except IndexError:
                        break
                else:
                    continue
                break

        return stack[0]

    def _calc_binary(self, stack, index, op):
        out = stack[index-1]
        next = stack[index+1]

        if op == '+':
            out += next
        elif op == '-':
            out -= next
        elif op == '*':
            out *= next
        elif op == '/':
            out /= next
        elif op == '^':
            out **= next

        return out

if __name__ == '__main__':
    calc = Calculator()
    print calc.calculate("12^2-(5*(2+2)))")
    print calc.calculate("2*32-4+456+(1+2)+3+(1/2*3+3+(1+2))")
    print calc.calculate("2 * (7+1) / (2 + 5 + (10-9)) ")

Edit: This is the modified version using Sean Perry's comments.

#!/usr/bin/env python

" A Simple calculator "

class Calculator(object):
    """ Example input:
        expression: (12+4)*2^4-(10-3**(15/5))
        steps:
        1) compile it to a list of ops and numbers: [ [12,+,4],*,2,^,4,-,[10,-,3,*,[15,/,5]] ]
        2) calculate starting with the highest operators first:

        [ [12, +, 5], *, 16, -, [10,-,3,*,[15,/,5]] ]
        [ 17, *, 16, -, [10,-,3,*,3] ]
        [ 17, *, 16, -, [10-9] ]
        [ 17, *, 16, -, 1]
        [ 272, -, 1 ]
        [ 271 ]

        TODO:
          * add floating point support

    """
    _stack = []

    # Flag that signfies if it's the first character in the expression
    INITIAL = True

    # exit perenthesis
    EXIST_PARENS = False
    # in number
    IN_NUM = False
    # in operator
    IN_OPERATOR = False

    OPERATORS = {
        '+': lambda x,y: x+y,
        '-': lambda x,y: x-y,
        '*': lambda x,y: x*y,
        '/': lambda x,y: x/y,
        '^': lambda x,y: x**y
    }

    OPS_ORDER = (('^',), ('*', '/'), ('+', '-'))

    class ErrorInvalidExpression(Exception):
        pass

    def compile(self, input_eq):
        """
        Compile the expression to a python representation
        of a list of numbers, operators and lists (parentheses)
        """
        for c in input_eq:
            try:
                # check if its a number
                current = int(c)
            except ValueError:
                # its not a number 
                self.IN_NUM = False
                # if it's an operator 
                if c in self.OPERATORS.keys():
                    if not self._stack:
                        raise ErrorInvalidExpression("You can't start an expression with an operator")

                    if self.IN_OPERATOR:
                        raise ErrorInValidExpression("More than one operator in a sequance")
                    else:
                        self._append_element(c)
                        self.IN_OPERATOR = True
                elif c == '(':
                    self._add_new_parentheses()
                    self.EXITS_PARENS = False
                elif c == ')':
                    self.EXIST_PARENS = True
                else:
                raise ErrorInvalidExpression("Syntax Error")

                continue

            # runs when its a number

            self.IN_OPERATOR = False

            # add the number to the stack
            self._add_new_num(current)

            # if its a new number
            if not self.IN_NUM:
                self.IN_NUM = True

            if self.INITIAL:
                self.INITIAL = False

    def _get_last_position(self):
        """ Returns the last inner most list in the stack """

        list_ref = list_prev = self._stack
        try:
            # While there's a list
            while list_ref[-1] or list_ref[-1] == []:
                if isinstance(list_ref[-1], list):
                    # make a reference to the list
                    list_prev = list_ref
                    list_ref = list_ref[-1]
                else:
                    break
        except IndexError:
            pass

        if self.EXIST_PARENS == True:
            self.EXIST_PARENS = False
            return list_prev
        else:
            return list_ref

    def _append_element(self, el):
        last_pos = self._get_last_position()
        last_pos.append(el)

    def _add_new_num(self, num):
        # if its the first character in an expression
        if not self._stack or self._get_last_position() == []:
            self._append_element(num)
        else:
            prev_c = self._get_last_position()[-1]
            # check if previous char is a number
            is_int = isinstance(prev_c, int)

            if is_int:
                self._add_to_previous_num(num, self._stack)
            elif prev_c in self.OPERATORS.keys():
                self._append_element(num)
            else:
                is_list = isinstance(self._stack[-1], list)
                # if it's a list search the last element in the list's children
                if is_list:
                    list_ref = self._get_last_position()
                    self._add_to_previous_num(num, list_ref)
                else:
                    # this should never happen
                    raise Exception("A fatal error has occured")

    def _add_to_previous_num(self, num, stack):
        try:
            last_pos = self._get_last_position()
            last_pos[-1] = last_pos[-1]*10+num
        except IndexError:
            last_pos.append(num)

    def _add_new_parentheses(self):
        last_pos = self._get_last_position()
        last_pos.append([])

    def calculate(self, expr):
        self.compile(''.join(expr.split()))
        # do the actual calculation
        result = self._rec_calc(self._stack)
        # initialize the stack
        self._stack = []

        return result

    def _rec_calc(self, stack):
        while len(stack) > 1:
            for ops in self.OPS_ORDER:
                for el in xrange(len(stack)):
                    try:
                        if isinstance(stack[el], list):
                            result = self._rec_calc(stack[el])
                            del stack[el]
                            stack.insert(el, result)
                        elif stack[el] in ops:
                            result = self._calc_binary(stack, el)
                            # delete all three elements that were used in the binary operation
                            del stack[el-1]
                            del stack[el-1]
                            del stack[el-1]
                            stack.insert(el-1, result)
                    except IndexError:
                        break
                else:
                    continue
                break

        return stack[0]

    def _calc_binary(self, stack, index):
        op = stack[index]
        prev = stack[index-1]
        next = stack[index+1]

        for symbol, action in self.OPERATORS.items():
            if symbol == op:
                return action(prev, next)


if __name__ == '__main__':
    calc = Calculator()
    print calc.calculate("12^2-(5*(2+2)))") # 124
    print calc.calculate("2*32-4+456+(1+2)+3+(1/2*3+3+(1+2))") # 528
    print calc.calculate("2 * (7+1) / (2 + 5 + (10-9)) ") # 2
\$\endgroup\$
5
  • 2
    \$\begingroup\$ I also once wrote a Python calculator: calculate = lambda x:eval(x). Works like a charm. \$\endgroup\$
    – ebarr
    Commented Apr 9, 2014 at 6:51
  • 2
    \$\begingroup\$ @ebarr calc("__import__('os').system('run evil command')"); Besides I didn't do it to get the functionality (writing a calculator is a pretty futile tasks considering the alternatives) I just wanted to brush up on my python. \$\endgroup\$ Commented Apr 9, 2014 at 8:02
  • \$\begingroup\$ Don’t use == with booleans; use if self.EXIST_PARENS is True: or even just if self.EXIST_PARENS:. \$\endgroup\$
    – alexwlchan
    Commented Apr 9, 2014 at 10:35
  • \$\begingroup\$ @user1179901 I merely jest. This is actually a pretty good exercise to get dug into a language. \$\endgroup\$
    – ebarr
    Commented Apr 9, 2014 at 12:47
  • \$\begingroup\$ The modified version has indentation error on line 76. \$\endgroup\$ Commented Apr 10, 2014 at 16:59

3 Answers 3

5
\$\begingroup\$

Use actual comments for comments. All of those strings are kept by the interpreter. If you have to use a string as a documentation item then you should use the triple quote variety.

Use full words or at least standard abbreviations. 'EXIT_PE' <-- no one else knows what this is. The proper spelling is 'parenthesis' singular or 'parentheses' plural. 'EXITS_PARENS' would be a good name. Same goes for 'IN_NU'. 'IN_NUM' would be acceptable.

Limit the scope of your try/except blocks. In compile you are catching ValueError but is it from the call to int() or the internal methods?

Make your own exceptions. Use these instead of just throwing Exception. It helps your reader (or debugger) know where to look.

You repeat yourself in _get_last_position.

In general, simplify your code and don't be afraid to use a few extra characters.

Here is a more pythonic approach. I am not 100% happy with it because I repeat myself a little. There is always room for improvement :-)

import operator
import string

class EvaluationError(Exception):
    pass


class InvalidNumber(Exception):
    pass


class InvalidOperator(Exception):
    pass


class UnbalancedParens(Exception):
    pass


def cast(value):
    """Attempt to turn a value into a number."""
    if isinstance(value, (int, float)):
        return value

    try:
        return int(value)
    except ValueError:
        pass
    try:
        return float(value)
    except ValueError:
        pass

    raise InvalidNumber(value)


class Operator(object):
    def __init__(self, op, precedence):
        self._op = op
        self._prec = precedence

    def __call__(self, *args):
        return self._op(*args)

    def __lt__(self, op):
        return self._prec < op._prec

    def __gt__(self, op):
        return self._prec > op._prec

    def __eq__(self, op):
        return self._prec == op._prec

    def __repr__(self):
        return repr(self._op)

    def __str__(self):
        return str(self._op)


class Calculator(object):
    operators = {
        '+' : Operator(operator.add, 1),
        '-' : Operator(operator.sub, 1),
        '*' : Operator(operator.mul, 2),
        '/' : Operator(operator.div, 2),
        '^' : Operator(operator.pow, 3),
    }

    def __init__(self):
        pass

    def calculate(self, expr):
        """Parse and evaluate the expression."""
        tokens = self.parse(expr)
        result = self.evaluate(tokens)
        return result

    def evaluate(self, tokens, trace=False):
        """Walk the list of tokens and evaluate the result."""
        stack = []
        for item in tokens:
            if isinstance(item, Operator):
                if trace:
                    print stack

                b, a = cast(stack.pop()), cast(stack.pop())
                result = item(a, b)
                stack.append(result)

                if trace:
                    print stack
            else:  # anything else just goes on the stack
                if item.endswith('.'):
                    raise InvalidNumber(item)
                stack.append(item)

        if len(stack) > 1:
            raise EvaluationError(str(stack))

        return stack[0]

    def parse(self, expr, trace=False):
        """Take an infix arithmetic expression and return the expression parsed into postfix notation.
        Note the numbers are left as strings to be evaluated later.
        """
        tokens = []
        op_stack = []

        last = None

        for c in expr:
            if c in string.whitespace:
                last = c
            elif c in string.digits:
                value = str(c)
                if last and last in string.digits:  # number continues, just append it
                    value = tokens.pop() + value

                last = c
                tokens.append(value)
            elif c == '.':
                if last and last in string.digits:  # looks like a decimal
                    tokens.append(tokens.pop() + ".")
                else:
                    raise InvalidParse("misplaced decimal")
            elif c == '(':
                op_stack.append('(')
            elif c == ')':
                if not op_stack:
                    raise UnbalancedParens(c)

                # closing parens found, unwind back to the matching open
                while op_stack:
                    curr = op_stack.pop()
                    if curr is '(':
                        break
                    else:
                        tokens.append(curr)
            else:  # not a number or a parens, must be an operator
                op = self.operators.get(c, None)
                if op is None:
                    raise InvalidOperator(c)

                while op_stack:
                    curr = op_stack[-1]
                    # the 'is' check prevents comparing an Operator to a string
                    if curr is '(':  # don't leave the current scope
                        break
                    elif curr < op:
                        break
                    tokens.append(op_stack.pop())

                op_stack.append(op)
                last = c

            if trace:
                print "----"
                print tokens
                print op_stack
                print "----"

        while op_stack:
            op = op_stack.pop()
            if op is '(':
                raise UnbalancedParens()
            tokens.append(op)

            if trace:
                print "----"
                print tokens
                print op_stack
                print "----"

        return tokens

if __name__ == '__main__':
    import sys

    calc = Calculator()

    if len(sys.argv) == 2:
        print calc.calculate(sys.argv[1])
        raise SystemExit(0)

    try:
        calc.calculate("(2 * 4 + 5")
    except UnbalancedParens:
        pass
    try:
        calc.calculate("2.")
    except InvalidNumber:
        pass
    try:
        calc.calculate("5 % 2")
    except InvalidOperator:
        pass

    print calc.calculate("2 * 3.14 * 5") # 31.4
    print calc.calculate("12^2-(5*(2+2)))") # 124
    print calc.calculate("2*32-4+456+(1+2)+3+(1/2*3+3+(1+2))") # 528
    print calc.calculate("2 * (7+1) / (2 + 5 + (10-9)) ") # 2

(code fixed, sorry for that. Joys of cut and paste.)

By transforming the input the state munging goes away and the stacks become part of the solution. The Operator class makes the operator handling simpler and clear. You can debug the pieces of this or use them independently.

Note the calculator class has no internal state. This also makes debugging easier. All of the state is in the stacks within the methods.

Enjoy.

\$\endgroup\$
8
  • \$\begingroup\$ Thanks for the tips, though I was aware of those issues except for the spelling part :). I was looking more for algorithm tips and code structure advice. And about the strings, my vim theme uses italic text in comments which isn't comfortable that's why I used those types of strings, but I will fix in the next version. Thanks again for your input. \$\endgroup\$ Commented Apr 9, 2014 at 7:30
  • \$\begingroup\$ Change OPERATORS to be a dict containing the symbol and the actions. Apply the input operator using the dict. This makes it easy to update the calculator and even add operators on the fly. \$\endgroup\$
    – Sean Perry
    Commented Apr 9, 2014 at 8:26
  • \$\begingroup\$ Python's list has a pop method. No need to use the magic -1. \$\endgroup\$
    – Sean Perry
    Commented Apr 9, 2014 at 8:29
  • \$\begingroup\$ I don't see where pop would be helpful since I don't want to modify the list. \$\endgroup\$ Commented Apr 9, 2014 at 8:53
  • \$\begingroup\$ I implemented the dictionary in OPERATORS though I think it only makes the code more complicated. \$\endgroup\$ Commented Apr 9, 2014 at 9:02
5
\$\begingroup\$

I generally have issues reading your code. As Sean suggests, you should simplify it. This could partly be due to the fact you're doing something unnecessarily low-level. In python, the way to go is import the modules you need and let them do the work. That decreases the amount of code you write yourself and makes it overall easier. That's one of the major reasons why I love python. But of course, this is an exercise.

I personally avoid using continue or break. I prefer refactoring the loop. It generally simplifies the logic and makes your methods more readable.

In the same readability spirit, I also never used the for: ... else: ... construct. I know it's technically fine, but I don't like it. I would prefer:

if len(arr) == 0:
    print 'no elements'
else:
    for item in arr:
        do_stuff_with(item)

It's more code, but it's simpler. And it's only the latter that counts.

I would also reconsider the order of your methods. The main method is calculate and it's kind of hidden between other methods. That makes searching for the logic hard.

I don't like the method name compile. It's too vague. I would go for something like split_in_chunks.

I find it personally very hard to judge your algorithm. But I would suggest you use a regular expression to find the innermost brackets. All you need then is one method to resolve expressions that don't contain brackets:

import re
expression = '(3 * (1 + 4) - 9) * (5 + (3 * (2 - 1)))'

def resolve_expr_without_brackets(expr):
    """ Replace this method by something that actually resolves the expression """
    return 'Hi!'

inner_brackets_found = True

while inner_brackets_found:
    m = re.search('\([^\(\)]+\)', expression)
    if m != None:
        # fetch a resolvable expression, and immediately drop its outer brackets
        expr_with_brackets = expression[m.start():m.end()]
        expr = expr_with_brackets[1:-2]
        result = resolve_expr_without_brackets(expr)
        expression = expression.replace(expr_with_brackets, result)
        # print expression for demonstrative purposes
        print expression
    else:
        inner_brackets_found = False
        total_result = resolve_expr_without_brackets(expression)

print total_result

Note how running the above script resolves expressions iteratively. It produces the following output:

(3 * Hi! - 9) * (5 + (3 * (2 - 1)))
Hi! * (5 + (3 * (2 - 1)))
Hi! * (5 + (3 * Hi!))
Hi! * (5 + Hi!)
Hi! * Hi!
Hi!

It should be noted though that regular expressions are often hard to debug.

\$\endgroup\$
3
\$\begingroup\$

This is a while loop that can exit three ways: by IndexError, by break or normally by the while condition.

    try:
        # While there's a list
        while list_ref[-1] or list_ref[-1] == []:
            if isinstance(list_ref[-1], list):
                # make a reference to the list
                list_prev = list_ref
                list_ref = list_ref[-1]
            else:
                break
    except IndexError:
        pass

Much simpler would be just to make the while condition check what you are really after. This loop does exactly the same as above. Note how the short-circuiting behavior of and avoids the IndexError:

    while list_ref and isinstance(list_ref[-1], list):
        list_prev = list_ref
        list_ref = list_ref[-1]

Variables defined directly under the class declaration are attributes of the class and shared between instances. When you assign eg. self.IN_NUM = False inside a method, you create an instance attribute that shadows the class attribute. This can a source of subtle bugs. Only use class attributes for data that is to be shared between instances, and initialize instance attributes in __init__. Also, only use ALL_CAPS naming convention for constants. In your case OPERATORS and OPS_ORDER seem to be constants, so I propose this:

class Calculator(object):
    OPERATORS = {
        '+': lambda x,y: x+y,
        '-': lambda x,y: x-y,
        '*': lambda x,y: x*y,
        '/': lambda x,y: x/y,
        '^': lambda x,y: x**y
    }

    OPS_ORDER = (('^',), ('*', '/'), ('+', '-'))

    def __init__(self):
        self._stack = []
        # Flag that signfies if it's the first character in the expression
        self.initial = True
        # exit parenthesis
        self.exist_parens = False
        # in number
        self.in_num = False
        # in operator
        self.in_operator = False
\$\endgroup\$
2
  • \$\begingroup\$ I used your first method in the beginning but it didn't catch cases where list_ref was an empty list, that's why I choose the method I choose. I'm not sure about your second point, what do you mean by class attributes as data to be shared between instances? \$\endgroup\$ Commented Apr 11, 2014 at 9:14
  • \$\begingroup\$ while list_ref will certainly stop looping when list_ref is an empty list. The second point relates to the fact that in Python classes themselves are objects too, but the objects one normally works with instances of classes. \$\endgroup\$ Commented Apr 11, 2014 at 9:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.