arbitrary operation on list

["add",["subtract",["multiply",2,["add",1,3]], 4 ] , 5 ]

how can I do these operation

when prog see "add" it adds 1 and 3 and return 4 new list became

["add",["subtract",["multiply",2, 4 ], 4 ] , 5 ]

when prog see "multiply" it does 2*4 nd return 8 new list 开发者_StackOverflow社区became

["add",["subtract",8, 4 ] , 5 ]

after one recursion

["add",4 , 5 ]

after last recursion

return 9

You should write a recursive function that goes through the lists and do the operations.

It's actually fairly trivial, but I don't want to just hand you the answer, especially since it sounds like homework. :) So update your question with what you tried to do, and we'll tell you where you are going wrong.

import operator

def do_math(op):
    try:
        return getattr(operator, op[0][:3])(*[do_math(arg) for arg in op[1:]])
    except TypeError:
        return op

L = ["add",["subtract",["multiply",2,["add",1,3]], 4 ] , 5 ]
print do_math(L)

The first thing to do is sketch it out visually as a tree:

If you look at the left child (subtract, multiply / 4, etc) you see it is also a tree; and so is the left half of that (multiply, 2 / add, etc).

In fact, you can think of each node with its descendants as being a tree, consisting of either (a) an operator, with a left sub-tree and right sub-tree, or (b) a value (leaf node, no more descendants).

to evaluate a tree:
  if it is a value:
    you have the final value; return it
  otherwise, it is an operator:
    evaluate the left sub-tree
    evaluate the right sub-tree
    do operation(left-tree-value, right-tree-value)
    return the result

You will notice that 'evaluate tree' calls itself to operate on the sub-trees - this is recursion, where solving a problem depends on solving smaller versions of the same problem and then combining the results.

So the final evaluation order looks like:

what is tree value?
    add: {tree1} + {tree2}
    what is tree1?
        subtract: {tree3} - {tree4}
        what is tree3?
            multiply: {tree5} * {tree6}
            what is tree5?
            2
            what is tree6?
                add: {tree7} + {tree8}
                what is tree7?
                1
                what is tree8?
                3
                add: 1 + 3
            4
            multiply: 2 * 4
        8
        what is tree4?
        4
        subtract: 8 - 4
    4
    what is tree2?
    5
    add: 4 + 5
9