Recursive math expression eval

Question

It has been very hard to use recursion, but I think that it made the code shorter and cleaner.

import doctest
import operator as op

START_FOR_SYMBOLS = {'+': 0,
                     '*': 1,
                     '/':1,
                     '-':0
                     }

OP_FOR_SYMBOL = {'+': op.add,
                 '*': op.mul,
                 '/': op.truediv,
                 '-': op.sub
                 }


def innermost_parens(text):
    """
    Returns the text inside the innermost parenthesis.

    >>> innermost_parens("1 + (2 * (4 - 1))")
    '4 - 1'
    >>> innermost_parens("1 + (2 * (4 * (2 + (8 * 7)) - 1))")
    '8 * 7'
    """
    if not '(' in text and not ')' in text:
        return text
    open_ = text.index('(')
    close_ = text.rindex(')')
    return innermost_parens(text[open_+1:close_])

def polish_eval(expr,start=None):
    """
    Unlimited polish eval, works for any number of arguments.

    >>> polish_eval('+ 4 1 6')
    11.0
    >>> polish_eval('* 4 5 5')
    100.0
    """
    tokens = expr.split(' ')
    if start is None:
        start = START_FOR_SYMBOLS[tokens[0]]
    if len(tokens) == 1:
        return start
    return polish_eval(' '.join(tokens[:-1]),
                       start = OP_FOR_SYMBOL[tokens[0]](start,float(tokens[-1]))
                       )

def infix_eval(expr):
    """
    Reduced infix eval, only works with 2 numbers.

    >>> infix_eval('9 + 4')
    13.0
    >>> infix_eval('2 * -6')
    -12.0
    """
    a, oper, b = expr.split()
    return OP_FOR_SYMBOL[oper](float(a),float(b))

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 (/ 10))", polish_eval)
    0.4
    >>> full_eval("(1 + (5 * 2))", infix_eval)
    11.0
    """
    if len(expr.split(' ')) == 1:
        return float(expr)
    inn = innermost_parens(expr)
    new_expr = expr.replace('('+str(inn)+')',str(eval_type(inn)))
    return full_eval(new_expr, eval_type)

def interface():
    which_expr = input("Polish or infix? ")
    if 'polish' in which_expr.lower():
        evaller = lambda expr: full_eval(expr, polish_eval)
    else:
        evaller = lambda expr: full_eval(expr, infix_eval)
    while True:
        result = evaller(input('> '))
        print(result)

if __name__ == "__main__":
    doctest.testmod()
    interface()

Answer 1

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.

Answer 2

Some suggestions:

• Rather than ask whether all the following expressions are going to be in Polish or infix notation, you can simply check whether the first non-parenthesis character is a number or an operator.
• START_FOR_SYMBOLS could be renamed to OPERATION_IDENTITIES for mathematical clarity.

Open issues:

• Why doctest.testmod() on every run?
• There isn't always a unique innermost parenthesis, for example in the case of (1 + 2) * (3 + 4). You probably want to return a list and process each of them in turn.