Python Mathematical Formula computation

Question

I'm writing a python program to calculate formula. I read in a list of strings which hold the values, operators and functions.

The code shown below receives a string for example:

['not', 1.0, 2.0, '=', 'power', 2.0, 3.0, '+']

The code above is a postfix version of the mathematical problem: power(2,3)+not(2=1) The program should calculate not(2=1) first, resulting in 1 and then calculate power(2,3) giving 9 and then 8+0 resulting in a return of 8.

So far my code to calculate the answers

stack = []
    def calculate(inputs): 
        if (inputs[0] == "sum"):
        inputs.remove("sum")
    for a in inputs:
        if (a) == "not":
            inputs.remove(a)
            op1, op2 = inputs[0], inputs[1]
            inputs.remove(op1)
            inputs.remove(op2)
            if op1 != op2:
                stack.append('0')
            else:
                stack.append('1') 
            continue  
        if (a) == 'power':
            inputs.remove(a)
            continue       
        if type(a) is float:
            stack.append(a)
            continue 
        op1, op2 = stack.pop(), stack.pop()
        #if a == 'power':

        if a == '+':
            stack.append(op2 + op1)
        elif a == '-':
            stack.append(op1 - op2)
        elif a == '*':
            stack.append(op2 * op1)
        elif a == '/':
            stack.append(op1 / op2)
        elif a == '=':
            if op1 != op2:
                stack.append('0')
            else:
                stack.append('1')  


    if (len(stack) > 1):
        lenStack = len(stack)-1
        for x in range(0, lenStack):
            stack.append('+')
        stack.append(_calcSum(stack))
    return stack.pop()

def _calcSum(stack):
    newStack = []
    for a in stack:
        if type(a) is float:
            newStack.append(a)
            continue
        op1, op2 = newStack.pop(), newStack.pop()
        if a == '+':
            newStack.append(op2 + op1)
        elif a == '-':
            newStack.append(op1 - op2)
        elif a == '*':
            newStack.append(op2 * op1)
        elif a == '/':
            newStack.append(op1 / op2)
    return newStack.pop()

However I'm having trouble with the NOT and POWER statement; I can't figure out how to automatically check for these. Could anyone possibly point me in the right direction or assist with my code? When I try to check for 'power' it simply skips the rest of my code and attempts to print stack - which is empty causing an error.

Answer 1

On the theme of redundant refinement, here's a variant of tobias_k's solution restructured for fewer special cases:

from operator import add, sub, mul, truediv, pow, eq, not_

ops = {"+": add, "-": sub, "*": mul, "/": truediv, 
       "power": pow, "=": eq, "not": not_}
# Mark how many inputs are needed
ops = {k:(1 if f is not_ else 2, f) for (k,f) in ops.items()}

def calculate(tokens):
    stack = []
    for token in tokens:
        try:
            args,func = ops[token]
            stack[-args:] = [func(*stack[-args:])]
        except KeyError:
            stack.append(float(token))
    return float(stack[-1])

Example:

>>> calculate("2 1 = not 2 3 power +".split())
9.0
>>> calculate("2 1 = not".split())
1.0
>>> calculate("2 3 power".split())
8.0

Yes, I'm using that Python's bool type is a subtype of int, so True is in fact 1. The difference of whether to produce 9 or 10 comes simply from the order of the power arguments (2**3==8 or 3**2==9).

The root of the problem remains that your original input expression isn't valid postfix notation, which makes evaluation order clear and therefore operator precedence redundant. If not comes before its argument, how can you tell when to evaluate it? not(1), not(1==2), and not((1==2)+(3**2) all look like possible interpretations, and it's no better for power.

Answer 2

Building upon IXI's answer, you can reduce the complexity and amount of code significantly by making use of functional programming: Create a mapping from symbols to operations to be performed, and then just look up the symbols in the input in that mapping. Doing this, you will see that power and not are not special at all, and additional unary and binary operators can be added with ease. You could even extend it to support ternary operators, such as ... if ... else ... (although you'd have to write them in postfix form).

BIN_OP = {"+": lambda x, y: x + y,
          "-": lambda x, y: x - y,
          "*": lambda x, y: x * y,
          "/": lambda x, y: x / y,
          "power": lambda x, y: x**y,
          "=": lambda x, y: int(x == y)}
UN_OP = {"not": lambda x: int(not x)}

def calculate(tokens):
    stack = []
    for token in tokens:
        if token in BIN_OP:
            op1, op2 = stack.pop(), stack.pop()
            operation = BIN_OP[token]
            stack.append(operation(op1, op2))
        elif token in UN_OP:
            op1 = stack.pop()
            operation = UN_OP[token]
            stack.append(operation(op1))
        else:
            stack.append(float(token))
    return stack.pop()

Example:

>>> calculate(['2', '1', '=', 'not', '2', '3', 'power', '+'])
10.0

Answer 3

I think that the following code might be what you want:

import math

test_input = ['2', '1', '=', 'not', '2', '3', 'power', '+']

def calculate(input):
    newStack = []
    for a in input:
        print newStack

        if a == '+':
            op1, op2 = newStack.pop(), newStack.pop()
            newStack.append(op2 + op1)
        elif a == '-':
            op1, op2 = newStack.pop(), newStack.pop()
            newStack.append(op1 - op2)
        elif a == '*':
            op1, op2 = newStack.pop(), newStack.pop()
            newStack.append(op2 * op1)
        elif a == '/':
            op1, op2 = newStack.pop(), newStack.pop()
            newStack.append(op1 / op2)
        elif a == '=':
            op1, op2 = newStack.pop(), newStack.pop()
            if op1 == op2:
                newStack.append(1)
            else:
                newStack.append(0)
        elif a == 'not':
            op = newStack.pop()
            if op > 0:
                newStack.append(0)
            else:
                newStack.append(1)
        elif a == 'power':
            op1, op2 = newStack.pop(), newStack.pop()
            newStack.append(math.pow(op1, op2))
        else:
            newStack.append(float(a))

    return newStack.pop()

As PeterE pointed out in his comment your postfix code is wrong. I assume that your wanted postfix code probably is 2 1 = not 2 3 power +. Also note that the end value then would be 9+1 = 10 and not 8+0 = 8.

Wikipedia has a nice page on postfix code: http://en.wikipedia.org/wiki/Reverse_Polish_notation.

In the python code one function actually should be enough to push and pop all the needed stuff onto a stack. To achieve a basic implementation you can then simply check all your different operator cases and perform any needed operations. If none of the provided operators matches the current element, you can assume that the element is a numeric value and simply push the parsed float value.

Note that this is a very quick and dirty implementation, but it might lead you on the right track.