Stack calculator (postfix, Python)

Question

The question I'm having problem on is calculating the postfix form expressions: for example, (1, 2, '+', 3, '*').

By calculating the expression using the following algorithm: 1. If the expression only contains an integer, return that integer. 2. Otherwise, maintain a stack. Loop through the tuple and push every element to the stack. If the element is an operator, pop the first two element out of the stack, calculate the result and push the result into the stack. To illustrate, we take the example above. Initially, the stack is empty. The test case is

calculate((1, 2, '*', 3, '-', 2, '*', 5, '+'))  
3

whereas my first code was no good (hardcoded and all >< ):

def calculate(inputs):
    if len(inputs) ==1:
        return inputs[0]
    elif len(inputs) == 5:
        s= []
        push_stack(s, inputs[0])
        push_stack(s, inputs[1])
        if inputs[2] == '*':
            A = s.pop() * s.pop()
        elif inputs[2] == '+':
            A = s.pop() + s.pop()
        elif inputs[2] == '-':
            A= s.pop() - s.pop()
        elif inputs[2] == '/':
            A = s.pop() / s.pop()
        s.clear()
        s= [A]
        push_stack(s, inputs[3])
        if inputs[4] == '*':
            A = s.pop() * s.pop()
        elif inputs[4] == '+':
            A = s.pop() + s.pop()
        elif inputs[4] == '-':
            A= s.pop() - s.pop()
        elif inputs[4] == '/':
            A = s.pop() / s.pop()
        return A
    else:
        s= []
        push_stack(s, inputs[0])
            push_stack(s, inputs[1])
        if inputs[2] == '*':
            A = s.pop() * s.pop()
        elif inputs[2] == '+':
            A = s.pop() + s.pop()
        elif inputs[2] == '-':
            A= s.pop() - s.pop()
        elif inputs[2] == '/':
            A = s.pop() / s.pop()
        s.clear()
        s= [A]
        push_stack(s, inputs[3])
        if inputs[4] == '*':
            A = s.pop() * s.pop()
        elif inputs[4] == '+':
            A = s.pop() + s.pop()
        elif inputs[4] == '-':
            A= s.pop() - s.pop()
        elif inputs[4] == '/':
            A = s.pop() / s.pop()
        s.clear()
        s= [A]
        push_stack(s, inputs[5])
        if inputs[6] == '*':
            A = s.pop() * s.pop()
        elif inputs[6] == '+':
            A = s.pop() + s.pop()
        elif inputs[6] == '-':
            A= s.pop() - s.pop()
        elif inputs[6] == '/':
            A = s.pop() / s.pop()
        s.clear()
        s= [A]
        push_stack(s, inputs[7])
        if inputs[8] == '*':
            A = s.pop() * s.pop()
        elif inputs[8] == '+':
            A = s.pop() + s.pop()
        elif inputs[8] == '-':
            A= s.pop() - s.pop()
        elif inputs[8] == '/':
            A = s.pop() / s.pop()
        return A

Sorry for making you read that! Then I changed the style to

def calculate(inputs):
    if len(inputs) ==1:
        return inputs[0]
    else:
        s =[]
        for i in inputs:
            if type(i) == int:
                return push_stack(s, i)
            elif i is '*' or '/' or 'x' or '+':
                A = s.pop()
                B =s.pop()
                know = operator(i, A, B)
                C = push_stack(s, know)
        return C

def operator(sign, one, two):
    if sign == '*':
        A = one * two
    elif sign == '+':
        A = one + two
    elif sign == '-':
        A= one - two
    elif sign == '/':
        A = one / two
    return A

Am I getting closer to the idea and how does my code improve?

** Edit ** Using IDLE:

>>> calculate((1, 2, '*', 3, '-'))
[1]
>>> calculate((1, 2, '+', 3, '*'))
[1]
>>> calculate((1, 2, '*', 3, '-', 2, '*', 5, '+'))
[1]

which is not the answer I'm looking for. It should be 1 then 9 then 3.

Related question: http://stackoverflow.com/questions/15112125/if-x-or-y-or-z-blah – Also: You should not compare strings using `is`; `is` checks for *identity*, not *equality*. — poke, Mar 22 '14 at 16:10

arshajii · Accepted Answer · 2014-03-22T15:19:32.533

There is a problem with

elif i is '*' or '/' or 'x' or '+':

which is treated as

elif (i is '*') or ('/') or ('x') or ('+'):

which is not what you want (it's always true). You can instead use something like:

elif i in ('*', '/', 'x', '+'):

Also:

if type(i) == int:
    return push_stack(s, i)

You shouldn't be returning there. You simply want:

if type(i) == int:
    push_stack(s, i)

Lastly, I think a better approach would be to always use the stack, and just return the top of the stack at the end of your function. This saves you from having to create a special case for 1-element arguments to calculate(). Putting this all together, something along the lines of this should work:

def calculate(inputs):
    stack = []
    for a in inputs:
        if type(a) is int:
            stack.append(a)
            continue

        op1, op2 = stack.pop(), stack.pop()

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

    return stack.pop()

Right now this does no error-checking (e.g. for malformed expressions), but it's easy to add.

Thanks! However the main answer still remains [1] for all test cases though. — user3251511, Mar 22 '14 at 15:02

score 4 · Answer 2 · answered Mar 23 '14 at 00:38

Part of the problem, which you seem to have realized, is that you are trying to make one function do everything. If you take a look at what the code is doing, and try to separate out the responsibilities, you end up with something like the following:

There are some crucial differences between Python 2.x and 3.x. Where these differences would cause problems, it's easiest to introduce helper functions and define them appropriately for each version:

import sys
if sys.hexversion < 0x3000000:
    # Python 2.x
    is_str = lambda s: isinstance(s, basestring)
    inp = raw_input
else:
    # Python 3.x
    is_str = lambda s: isinstance(s, str)
    inp = input

You do a fair bit of stack maintenance; this can be avoided by making a Stack class which knows how to pop and push multiple items. (It should also help your out-of-order arguments problem; 4 2 - should be 4 - 2, not 2 - 4)

class Stack(list):
    def pop_n(self, n):
        """
        Pop n items off stack, return as list
        """
        assert n >= 0, "Bad value {}: n cannot be negative".format(n)
        if n == 0:
            return []
        elif n <= len(self):
            res = self[-n:]
            del self[-n:]
            return res
        else:
            raise ValueError("cannot pop {} items, only {} in stack".format(n, len(self)))

    def push_n(self, n, items):
        """
        Push n items onto stack
        """
        assert n == len(items), "Expected {} items, received {}".format(n, len(items))
        self.extend(items)

Rather than having a single "do-any-operation" function, we can let each operator have its own self-contained code. This makes it much easier to change or add operators without funny side-effects. First we make an Operator class

class Op:
    def __init__(self, num_in, num_out, fn):
        """
        A postfix operator

        num_in:     int
        num_out:    int
        fn:         accept num_in positional arguments,
                    perform operation,
                    return list containing num_out values
        """
        assert num_in  >= 0, "Operator cannot have negative number of arguments"
        self.num_in = num_in
        assert num_out >= 0, "Operator cannot return negative number of results"
        self.num_out = num_out
        self.fn = fn

    def __call__(self, stack):
        """
        Run operator against stack (in-place)
        """
        args = stack.pop_n(self.num_in)         # pop num_in arguments
        res = self.fn(*args)                    # pass to function, get results
        stack.push_n(self.num_out, res)         # push num_out values back

then we define the actual operators as

ops = {
    '*':  Op(2, 1, lambda a,b: [a*b]),          # multiplication
    '/':  Op(2, 1, lambda a,b: [a//b]),         # integer division
    '+':  Op(2, 1, lambda a,b: [a+b]),          # addition
    '-':  Op(2, 1, lambda a,b: [a-b]),          # subtraction
    '/%': Op(2, 2, lambda a,b: [a//b, a%b])     # divmod (example of 2-output op)
}

Now that the support structure is in place, your evaluation function is simply

def postfix_eval(tokens):
    """
    Evaluate a series of tokens as a postfix expression;
    return the resulting stack
    """
    if is_str(tokens):
        # if tokens is a string, treat it as a space-separated list of tokens
        tokens = tokens.split()

    stack = Stack()
    for token in tokens:
        try:
            # Convert to int and push on stack
            stack.append(int(token))
        except ValueError:
            try:
                # Not an int - must be an operator
                # Get the appropriate operator and run it against the stack
                op = ops[token]
                op(stack)         # runs Op.__call__(op, stack)
            except KeyError:
                # Not a valid operator either
                raise ValueError("unknown operator {}".format(token))
    return stack

and to make it easier to test, we can make it interactive:

def main():
    while True:
        expr = inp('\nEnter a postfix expression (or nothing to quit): ').strip()
        if expr:
            try:
                print("  => {}".format(postfix_eval(expr)))
            except ValueError as error:
                print("Your expression caused an error: {}".format(error))
        else:
            break

if __name__=="__main__":
    main()

This runs like

Enter a postfix expression (or nothing to quit): 1 2 * 3 -
=> [-1]
Enter a postfix expression (or nothing to quit): 1 2 + 3 *
=> [9]
Enter a postfix expression (or nothing to quit): 1 2 * 3 - 2 * 5 +
=> [3]
Enter a postfix expression (or nothing to quit): 5 2 /%
=> [2, 1]

score -2 · Answer 3 · edited Mar 22 '14 at 18:08

-2

If you are doing calculator, or something like that, you should use function eval(). It will return result of expression.

edited Mar 22 '14 at 18:08

Omar

32,302
9
69
112

answered Mar 22 '14 at 17:47

gcx11

128
4

That's not what the OP is after. Please re-read the question. – arshajii Mar 22 '14 at 18:39

Stack calculator (postfix, Python)

3 Answers3