Return to Answer

• 1

• 1.3k
• 8
• 25

Good job on adding the test suites; they make testing code extremely easy.

Recursion often results in a clean solution. However, I think that this problem can be solved just as well with an iterative approach.

The key to innermost_parens is to return the text between the last ( and the first ). Recursion is a viable solution, but I find that this for loop does the job better and in a cleaner way:

def innermost_parens(text):
 """
 Returns the innermost parenthesis.
 >>> innermost_parens('* 1 2')
 '* 1 2'
 >>> innermost_parens("1 + (2 * (4 - 1))")
 '(4 - 1)'
 >>> innermost_parens("1 + (2 * (4 * (2 + (8 * 7)) - 1))")
 '(8 * 7)'
 >>> innermost_parens("(1 + 2) * (3 + 4)")
 '(1 + 2)'
 """
 start = 0
 end = len(text)
 for (i, c) in enumerate(text):
 if c == '(':
 start = i
 if c == ')':
 end = i + 1
 break
 return text[start:end]

Take note that this function will return the first innermost expression with brackets. The reason for this will be clear later.

As for polish_eval, your program doesn't follow the standard Polish notation. In the standard Polish notation you can only perform operations on two numbers. It is also unclear what 'start' does. I modified your code to do the above and added tests for subtraction and division:

def polish_eval(expr):
 """
 Reduced Polish notation.
 >>> polish_eval('+ 4 1')
 5.0
 >>> polish_eval('* 4 5')
 20.0
 >>> polish_eval('- 20 3')
 17.0
 >>> polish_eval('/ 20 5')
 4.0
 """
 oper, a, b = expr.split()
 return OP_FOR_SYMBOL[oper](float(a), float(b))

I'll leave the documentation of the Polish notation to you. No changes were made to infix_eval.

Finally, we're on to full_eval. Since there's been a major change in the notation we support, we'll have to rewrite the code. First, to start off with the tests:

>>> full_eval("* (* 4 5) (+ 4 1)", polish_eval)
100.0
>>> full_eval("* 4 (/ 1 10)", polish_eval)
0.4
>>> full_eval("1 + (5 * 2)", infix_eval)
11.0

Rewriting Polish notation without brackets would require the use of a stack. This will not fit nicely in your full_eval function, so I will not implement the notation without brackets. In this function, the use of recursion is unnecessary and a while loop will fit the problem nicely.

def full_eval(expr, eval_type):
 """
 Evals by the rules of eval_type starting from the inner
 parenthesis.
 >>> full_eval("* (* 4 5) (+ 4 1)", polish_eval)
 100.0
 >>> full_eval("* 4 (/ 1 10)", polish_eval)
 0.4
 >>> full_eval("1 + (5 * 2)", infix_eval)
 11.0
 """
 while len(expr.split()) != 1:
 inn = innermost_parens(expr)
 result = eval_type(inn.strip('(').strip(')').strip())
 expr = expr.replace(inn, str(result))
 return float(expr)

Before I evaluate inn, I first strip off the brackets which enclose the expression, as well as any remaining whitespace.

The reason why I wrote innermost_parens as shown above is to allow for the easy replacement of the expression. Here's a trace of an expression in Polish:

 * (/ 9 3) (+ (/ 3 5) (- 20 5))
= * (/ 9 3) (+ 0.6 (- 20 5)) # '(/ 3 5)' -> '0.6'
= * (/ 9 3) (+ 0.6 15.0) # '(- 20 5)' -> '15.0'
= * 3.0 (+ 0.6 15.0) # '(/ 9 3)' -> '3.0'
= * 3.0 15.6 # '(+ 0.6 15.0)' -> '15.6'
= 46.8 # '* 3.0 15.6' -> '46.8'

and the same expression in infix:

 (9 / 3) * ((3 / 5) + (20 - 5))
= (9 / 3) * (0.6 + (20 - 5)) # '(3 / 5)' -> '0.6'
= (9 / 3) * (0.6 + 15.0) # '(20 - 5)' -> '15.0'
= 3.0 * (0.6 + 15.0) # '(9 / 3)' -> '3.0'
= 3.0 * 15.6 # '(0.6 + 15.0)' -> '15.6'
= 46.8 # '3.0 * 15.6' -> '46.8'

Extensions:

1. Write your program such that it can parse Polish notation without brackets. That's what Polish notation is invented for.
2. Handle edge cases such as ((* 3 15)) (Polish).
3. Write test suites to ensure that the expressions are evaluated correctly. While addition and multiplication is commutative, subtraction and division are not, and the order of the numbers matter.
4. Follow suggestions in l0b0's answer, which are cosmetic. I did not make any cosmetic suggestions as I thought that it was more important to settle the logic of the program first.
5. Have your program create an abstract syntax tree instead of doing string operations (such as replacing innermost expression with its value).

Feel free to ask questions in the comments.