Minimum and Maximum values of an expression with * and + | Utility method to check whether a character is operator or not ; method prints minimum and maximum value obtainable from an expression ; store operator and numbers in different vectors ; storing last number in vector ; initializing minval and maxval 2D array ; initializing main diagonal by num values ; looping similar to matrix chain multiplication and updating both 2D arrays ; if current operator is ' + ' , updating tmp variable by addition ; if current operator is ' * ' , updating tmp variable by multiplication ; updating array values by tmp variables ; last element of first row will store the result ; Driver code
def isOperator ( op ) : NEW_LINE INDENT return ( op == ' + ' or op == ' * ' ) NEW_LINE DEDENT def printMinAndMaxValueOfExp ( exp ) : NEW_LINE INDENT num = [ ] NEW_LINE opr = [ ] NEW_LINE tmp = " " NEW_LINE for i in range ( len ( exp ) ) : NEW_LINE INDENT if ( isOperator ( exp [ i ] ) ) : NEW_LINE INDENT opr . append ( exp [ i ] ) NEW_LINE num . append ( int ( tmp ) ) NEW_LINE tmp = " " NEW_LINE DEDENT else : NEW_LINE INDENT tmp += exp [ i ] NEW_LINE DEDENT DEDENT num . append ( int ( tmp ) ) NEW_LINE llen = len ( num ) NEW_LINE minVal = [ [ 0 for i in range ( llen ) ] for i in range ( llen ) ] NEW_LINE maxVal = [ [ 0 for i in range ( llen ) ] for i in range ( llen ) ] NEW_LINE for i in range ( llen ) : NEW_LINE INDENT for j in range ( llen ) : NEW_LINE INDENT minVal [ i ] [ j ] = 10 ** 9 NEW_LINE maxVal [ i ] [ j ] = 0 NEW_LINE if ( i == j ) : NEW_LINE INDENT minVal [ i ] [ j ] = maxVal [ i ] [ j ] = num [ i ] NEW_LINE DEDENT DEDENT DEDENT for L in range ( 2 , llen + 1 ) : NEW_LINE INDENT for i in range ( llen - L + 1 ) : NEW_LINE INDENT j = i + L - 1 NEW_LINE for k in range ( i , j ) : NEW_LINE INDENT minTmp = 0 NEW_LINE maxTmp = 0 NEW_LINE if ( opr [ k ] == ' + ' ) : NEW_LINE INDENT minTmp = minVal [ i ] [ k ] + minVal [ k + 1 ] [ j ] NEW_LINE maxTmp = maxVal [ i ] [ k ] + maxVal [ k + 1 ] [ j ] NEW_LINE DEDENT elif ( opr [ k ] == ' * ' ) : NEW_LINE INDENT minTmp = minVal [ i ] [ k ] * minVal [ k + 1 ] [ j ] NEW_LINE maxTmp = maxVal [ i ] [ k ] * maxVal [ k + 1 ] [ j ] NEW_LINE DEDENT if ( minTmp < minVal [ i ] [ j ] ) : NEW_LINE INDENT minVal [ i ] [ j ] = minTmp NEW_LINE DEDENT if ( maxTmp > maxVal [ i ] [ j ] ) : NEW_LINE INDENT maxVal [ i ] [ j ] = maxTmp NEW_LINE DEDENT DEDENT DEDENT DEDENT print ( " Minimum ▁ value ▁ : ▁ " , minVal [ 0 ] [ llen - 1 ] , " , ▁ \ ▁ Maximum ▁ value ▁ : ▁ " , maxVal [ 0 ] [ llen - 1 ] ) NEW_LINE DEDENT expression = "1 + 2*3 + 4*5" NEW_LINE printMinAndMaxValueOfExp ( expression ) NEW_LINE