Solving parenthesized expressions with recursion

Question

I am having problems with a recursive method that can completely solve the equations in brackets, such as ((3+2)/(1+4)) . I was able to come up with a recursive solution to solve infix expressions like +*+3421 using recursion, but for something like ((3+2)/(1+4)) I got a little stuck.

 def evalPrefix(exp): it = iter(exp) return evalPrefixInner(it) def evalPrefixInner(it): item = it.next() if isInt(item): return int(item) else: operand1 = evalPrefixInner(it) operand2 = evalPrefixInner(it) return execute(item, operand1, operand2) 

Answer 1

Your grammar:

 expr ::= int | ( expr op expr ) 

right?

So, ignoring error checking, something like ...

 def evalExpr(it): item = it.next() if isInt(item): return int(item) else: //item should = lparen operand1 = evalExpr(it) op = it.next() operand2 = evalExpr(it) rparen = it.next() return execute(op, operand1, operand2) 

Answer 2

Try the shunting-yard algorithm :

 dic={"+": lambda x, y:x+y, "-": lambda x, y:xy, "/": lambda x, y:x/y, "%": lambda x, y:x%y, "*": lambda x, y:x*y} def algo(x, op=None, nums=None): if x != "": op = op if op else [] nums = nums if nums else [] item = x[0] if item in ("+","-","%","/","*"): op.append(item) if item.isdigit(): nums.append(item) if item==")": operator = op.pop() opd1, opd2 = int(nums.pop()), int(nums.pop()) ans = dic[operator](opd1, opd2) nums.append(ans) return algo(x[1:], op, nums) else: if op and nums: operator = op.pop() opd1, opd2 = int(nums.pop()), int(nums.pop()) return dic[operator](opd1, opd2) else: return nums[-1] print algo("((3+2)/(1+4))") #output :1 print algo("((5+2)*3*(2+5))") #output :147 

Answer 3

Parse the input for valid data, and then use the compiler module to parse the expression:

 import compiler expr = compiler.compile(r'((3+2)/(4+1))', 'err', 'eval') 

and then you can use:

 eval(expr)