Using recursion to solve user entered expressions (calculator)

Question

As an assignment I have to write a calculator that will accept and solve user input such as:

3 + 7 * (!3)^2

I have to solve this excercise with recursion.

def solve(exp):
     #Recursion if statement
     for op in exp:
       if op == "*":
           ...
       elif op == "/":
           ...
       ...
     return solve(exp)

This is how I assume my code would look like, but I'm unable to decide what would be the stop condition of the recursion.
Also, I'm not sure if this kind of loop is useful, since I won't be able to handle several cases such as -3 +5, or to handle use of brackets.

I think that my basic idea on how to solve it isn't good and I would like to get suggestions on how to do this.

Answer 1

umm parsing an expression(s) using the 'standard' grammar, through recursive decent is virtually impossible:

E = E + E | E - E | ... | VALUE

this is because calling E may yield an infinite recursion, there are other issues such as operator precedence as well as associativity ...

There are two well known methods of dealing with such issues, actually the two methods are applicable to most problems.

1) Use a bottom-up approach, one example is shift-reduce parsing http://en.wikipedia.org/wiki/Shift-reduce_parser this method keeps your grammar at the expense of the codes complexity.

2) Use a top-down approach, one example is recursive-decent but with a different grammar, http://en.wikipedia.org/wiki/LL_parser one without left recursions this is usually done by modifying the original grammar and updating all rules removing any direct left recursive calls. this modifies the grammar (if possible) making it quite longer but the code is simpler.

Being that you requested the method to be recursive, maybe the second is a better approach.

we first have to define this new grammar and simply create a new function for each rule.

you gave this example: 3 + 7 * (!3)^2 so I've deduce the following operators in order of precedence in descending order.

operators: +, -, *, /, ^, -, !
values: 0,1,2,3 ...

here is a simple, well known LL(1) grammar that holds precedence ...

<arith_expr>  : <term> {+ <term>}
              | <term> {- <term>}

<term>        : <power> {* <power>}
              | <power> {/ <power>}

<power>       : <factor> <exponent>
<exponent>    : ^ <factor> <exponent> | ''

<factor>      | NUMERIC_VALUE
              | - <factor>
              | ! <factor>
              | ( <arith_expr> )

its some what equivalent to the previous grammar but has no direct left recursive calls, the process of converting a grammar to a LL(*) grammar is somewhat mechanical ...

I usually don't give out code for assignments, specially simple ones, but this is only to get you started, you should be able to implement the rest.

Because white space in general is ignore, we quantized our input into a set of values applicable to each rule of our grammar, excluding any whitespace unless our grammars dictates it's otherwise, this process is called tokinization, each value is referred to as token, while is common to use regexp for this, I preferred a manual approach for readability ... Tokinization is quite simple ...

"""
`{}` means 0 or more  
<arith_expr>  : <term> {+ <term>}
              | <term> {- <term>}

<term>        : <factor> {* <factor>}


<factor>      | NUMERIC_VALUE
              | - <factor>
              | ( <arith_expr> )
"""

import string

def evaluate(str_value):

    def tokenize(value):
        all_symbols = set(('+', '-', '*',)) | set(('(', ')'))
        white_space = set((' ', '\n', '\t'))
        tokens = []
        index = 0
        while index < len(value):
            current_char = value[index]
            if current_char in white_space:
                index += 1
                continue 
            if current_char in all_symbols:
                tokens.append(current_char)
                index += 1
                continue
            if (current_char in string.digits) or (current_char == '.'):
                numeric_value = current_char
                index += 1                
                while (index < len(value)) and ((value[index] in string.digits) or (value[index] == '.')):
                    if (values[index] == '.') and ('.' in numeric_value):
                        raise Exception('Multiple decimal points detected while tokenizing numeric value!')
                    numeric_value.append(value[index])
                    index += 1
                tokens.append(float(numeric_value) if '.' in numeric_value else int(numeric_value))
                continue
            raise Exception('Unable to tokenize symbol %s' % value[index])
        return tokens


    def factor(tokens):
        '''
        <factor>      | NUMERIC_VALUE
                      | - <factor>
                      | ( <arith_expr> )
        '''        
        if not tokens:
            return None
        if type(tokens[0]) in set((int, float)): # NUMERIC_VALUE
            return tokens.pop(0)
        if tokens[0] == '-':                     # - <factor>
            tokens.pop(0)
            return -1 * factor(tokens)  
        if tokens[0] == '(':                     # ( <arith_expr> )
            tokens.pop(0)
            value = arith_expr(tokens)
            assert tokens.pop(0) == ')'
            return value

    def term(tokens):
        '''
        <term>        : <factor> {* <factor>}

        '''
        left_value = factor(tokens)
        operators = set(('*',))
        while tokens and (tokens[0] in operators):  # {* <factor>}
            op = tokens.pop(0)
            right_value = factor(tokens)
            left_value *= right_value
        return left_value




    def arith_expr(tokens):
        '''
        <arith_expr>  : <term> {+ <term>}
                      | <term> {- <term>}
        '''

        left_value = term(tokens)
        operators = set(('+', '-'))
        while tokens and (tokens[0] in operators):
            op = tokens.pop(0)
            right_value = term(tokens)
            if op == '+':
                left_value += right_value
            else:
                left_value -= right_value
        return left_value 


    return arith_expr(tokenize(str_value))

note: this hasn't being tested!

Answer 2

Two comments:

1. Your current solution will not return anything interesting, in fact it appears to cycle infinitely, as the exp you pass to the next stage of the recursion is unchanged from that which was passed in originally, further there is no indication that any one cycle through the recursion actually has any effect on the final solution.
2. The stop condition should be an empty expression, that is, it should be "" if you are storing expressions as strings.