Find all possible outcomes of a given expression

*Source: Geeks4Geeks

Given an arithmetic expression, find all possible outcomes of this expression. Different outcomes are evaluated by putting brackets at different places.

We may assume that the numbers are single digit numbers in given expression.

Example:

Input:  1+3*2
Output: 8  7
Explanation
(1 + 3)*2     = 80
(1 + (3 * 2)) = 70

Input:  1*2+3*4
Output: 14 20 14 20 20
 (1*(2+(3*4))) =  14
 (1*((2+3)*4)) =  20 
 ((1*2)+(3*4)) =  14
 ((1*(2+3))*4) =  20
 ((1*2)+3)*4)  =  20

The idea is to iterate through every operator in given expression. For every operator, evaluate all possible values of its left and right sides. Apply current operator on every pair of left side and right side values and add all evaluated values to the result.

1) Initialize result 'res' as empty.
2) Do following for every operator 'x'.
    a) Recursively evaluate all possible values on left of 'x'.
       Let the list of values be 'l'.  
    a) Recursively evaluate all possible values on right of 'x'.
       Let the list of values be 'r'.
    c) Loop through all values in list 'l'  
           loop through all values in list 'r'
               Apply current operator 'x' on current items of 
               'l' and 'r' and add the evaluated value to 'res'   
3) Return 'res'.

Implementation: Python2.7

"""
    Calculate all possible outcomes of a given expression
    Constraint: All numbers in the expression must be 1-digit number
"""
def evaluate(number1, operator, number2):
    """
        return value of number1 operator number2
        example: 1 + 2
    """
    expression = str(number1) + ' ' + operator + ' ' +  str(number2)
    return eval(expression)

def evaluate_all(expression, low, high):
    """
        Evaluate all possible values of the expression
    """
    res = [] #store all possible outcomes
    if low == high: #only one character, it must be a digit
        res.append(int(expression[low]))
        return res

    #if there are only 3 characters
    #middle one must be operator and corner ones must be operands
    if low == (high-2):
        res.append(evaluate(expression[low], expression[low+1], expression[low+2]))
        return res

    #every i refers to an operator
    for i in range(low+1, high+1, 2):
        #left refers to all the possible values
        #in the left of operator expression[i]
        left = evaluate_all(expression, low, i-1)
        #right refers to all the possible values
        #in the right of operator expression[i]
        right = evaluate_all(expression, i+1, high)
        print left, expression[i], right
        #take above evaluated all possible
        #values in left side of 'i'
        for s1 in range(len(left)):
            #take above evaluated all possible
            #values in right side of 'i'
            for s2 in range(len(right)):
                res.append(evaluate(left[s1], expression[i], right[s2]))
    return res

if __name__ == '__main__':
    EXPR = '1*2+3*4'
    ALL_POSSIBLE_OUTCOMES = evaluate_all(EXPR, 0, len(EXPR)-1)
    for outcome in ALL_POSSIBLE_OUTCOMES:
        print outcome

Advertisements