import java.util.*;

public class MaxValueOfExpression{

static boolean isOperator(char op) { return (op == '+' || op=='-' || op == '*'); }

static Map getValExp(String expression, Map> dataCalculated){

if( dataCalculated.containsKey(expression)) return dataCalculated.get(expression);

Map res = new HashMap(); for (int i = 0; i resPre = getValExp(expression.substring(0,i), dataCalculated); Map resSuf = getValExp(expression.substring(i+1), dataCalculated);

// Combine all possible combination for(String resPreKey: resPre.keySet()){ for(String resSufKey: resSuf.keySet()){ if (expression.charAt(i) == '+') res.put("("+ resPreKey + "+" + resSufKey + ")", resPre.get(resPreKey) + resSuf.get(resSufKey)); else if (expression.charAt(i) == '-') res.put("("+ resPreKey + "-" + resSufKey + ")", resPre.get(resPreKey) - resSuf.get(resSufKey)); else if (expression.charAt(i) == '*') res.put("("+ resPreKey + "*" + resSufKey + ")", resPre.get(resPreKey) * resSuf.get(resSufKey)); } } } }

// if expression contains only number then save that // into res vector if (res.size() == 0) res.put("" + expression + "", Integer.parseInt(expression));

// Store in memo so that expression string is not // processed repeatedly dataCalculated.put(expression, res);

return res; }

public static void printMaxValueExp(String expression){ Map> dataCalculated = new HashMap(); getValExp(expression, dataCalculated); Map requiredData= dataCalculated.get(expression);

String maxExpression = ""; int maxData = -9999; for(String key: requiredData.keySet()){ if( requiredData.get(key) > maxData){ maxExpression = key; maxData = requiredData.get(key); } } System.out.println("The maximum value for the given expression "+expression+ " is obtained by " + maxExpression + " and the value is " + maxData);

}

public static void main(String[] args) { String expression = "1+2*3+4*5"; printMaxValueExp(expression);

expression = "1+3-7*6-4"; printMaxValueExp(expression); }

}

ii

Please i need big O analysis of above code and result

Write a Java program that given a sequence of n numbers with n - 1 signs of operations +, -, and * (times) in between (e.g., 1+3 - 7* 6 - 4) puts parentheses in a way that maximizes the value of the resulting expression. Your program needs to print the expression after adding the parenthesis that maximizes the result, and the expression result Input 1 +3 - 7* 6-4 Output (1 + ((3 7)*(6 - 4))) -7 You need to make sure that your program is efficient in terms of complexity. Hint: Note that the number of parenthesis equals to the number of operators. Your submission need to be one word file that include: The java program Screenshot of the following test cases along with the output from your program 1 +3 - 7* 6-4 1 * 2- 7 * 4-8 al - 20 - 10 + 60 The Big-O analysis of your program and its time complexity o O Please i need this