How to take the sum when '+' is present?

Question

I'm working with post-fix notation and stacks, and I'm wondering if/how I can sum the elements of a list, stack etc. when the string '+' is present?

For the example, I'm just going to use a list instead of a stack (although if you have a solution for the stack, by all means go ahead).

So, maybe if I had:

string = '1 2 3 +'

and turned this into a list:

['1','2','3','+']

if correct would evaluate to:

6

Here's what I had thought would work (Note: The valid() function I made checks if it can be changed into a float based off the string. It's working fine):

def post_fix(string):
     lst = []
     for i in string:
         if '(' in lst:
             pass
         elif valid(i) is True:      
             int(i)
             lst.append(i)
         elif '+' in string:
             '+' == sum(lst)
             print(sum(lst))

  post_fix('1 2 3 +')

How could I get this working so that if '+' or '-' etc. is present, it will do the appropriate operation?

Note: For simplicity, you can just assume that the operator will always be at the end. So don't worry about something like '12+34*', although if you have a solution for this, it would be much appreciated.

Answer 1

You evaluate postfix notation using a stack. When you see a number, you push it onto the stack. When you see an operator, you pop off enough numbers to satisfy it and push the result. At the end, the stack should have only one item and you print it.

Now usually + is a binary operator: it takes two operands. In your case you want it to consume whatever is on the stack. That's an unconventional meaning for +, but it's simple enough to implement.

def postfix(tokens):
    stack = []
    tokens = tokens.split() if isinstance(tokens, str) else tokens
    for token in tokens:
        if token.isdigit() or token.startswith("-") and token[1:].isdigit():
            stack.append(int(token))
        elif token == "+":
            assert stack    # need at least one item
            result = 0
            while stack:
               result += stack.pop()
            stack.append(result)
        else:
            raise ValueError("invalid token {}".format(token))
    assert len(stack) == 1
    return stack[0]

print(postfix("1 2 3 +"))

This structure is easily extended to handle other operations. For example, you could use + for binary addition and ++ for sum all.

elif token == "++":   # sum all
    result = 0
    while stack:
       result += stack.pop()
    stack.append(result)
elif token == "+":    # binary additon
    stack.append(stack.pop() + stack.pop())