动态规划求表达式最大值

import acm.program.*; import acm.util.*; import java.util.*; public class DynamicOnExpression extends ConsoleProgram{ private static Character PLUS= '+'; private static Character MULTI = '*'; public static void main(String args[]){ new DynamicOnExpression().start(args); } public void run(){ setFont("Times New Roman-18"); //String str = readLine("Please input your expression:"); //String str = "1+2*3+-1"; //String str = "1+2*-2*1+2*-2"; println("When you input the word exist, the program is over!"); println(); while(true){ String str = readLine("Please input your expression:"); if (str.equalsIgnoreCase("exit")) break; ArrayList<Integer> number = new ArrayList<Integer>(); ArrayList<Character> operation = new ArrayList<Character>(); dealWithStr(number,operation,str); Node[][] matrix = initialMatrix(number); fillMatrix(matrix,number,operation); println("The max is " + matrix[0][number.size()-1].getMax()); Traceback(0,number.size()-1,matrix,number,operation,true);//true represent to search the max; println();println(); } println("The input process is over!"); } public void dealWithStr(ArrayList<Integer> number, ArrayList<Character> operation,String str){ int index = -1; while (true){ int index1 = str.indexOf(PLUS,index + 1); int index2 = str.indexOf(MULTI,index + 1); if (index1 == -1 && index2 == -1) break; if (index1 != -1 && index2 !=-1){ int start = index + 1; index = (index1 < index2) ? index1 : index2; int temp = Integer.parseInt(str.substring(start, index)); number.add(temp); operation.add(str.charAt(index)); }else{ int start =index + 1; index = (index1 == -1)? index2: index1; int temp = Integer.parseInt(str.substring(start,index)); number.add(temp); operation.add(str.charAt(index)); number.add(Integer.parseInt(str.substring(index+1))); } } } public Node[][] initialMatrix(ArrayList<Integer> number){ int size = number.size(); Node[][] matrix = new Node[size][size]; for (int i = 0; i < size; i++) { Node node = new Node(number.get(i)); matrix[i][i] = node; } return matrix; } public void fillMatrix(Node[][] matrix,ArrayList<Integer> number, ArrayList<Character> operation){ int size = number.size(); for (int r = 2; r <= size; r++){ for (int i = 0; i <= size - r; i++){ int j = i + r -1; Node node1 = matrix[i][i].opWithAnother(matrix[i+1][j], i, operation.get(i)); int max = node1.getMax(); int k_max = node1.getk_Max(); int f_max = node1.getf_Max(); int min = node1.getMin(); int k_min = node1.getk_Min(); int f_min = node1.getf_Min(); for (int k = i+1; k < j ; k++){ Node node2= matrix[i][k].opWithAnother(matrix[k+1][j], k, operation.get(k)); if (max < node2.getMax()){ max = node2.getMax(); k_max = node2.getk_Max(); f_max = node2.getf_Max(); } if (min > node2.getMin()){ min = node2.getMin(); k_min = node2.getk_Min(); f_min = node2.getf_Min(); } } matrix[i][j] = new Node(max,min,k_max,k_min,f_max,f_min); println("(i=" + i + "j=" + j +"):" +matrix[i][j].toString()); } } } public void Traceback(int i ,int j, Node[][] matrix, ArrayList<Integer> number,ArrayList<Character> operation,Boolean flag){ if(i==j){ if(number.get(i) >= 0){ print(number.get(i)); } else{ print("(" + number.get(i) + ")"); } }else{ int k;int f; if (flag == true){ k = matrix[i][j].getk_Max(); f = matrix[i][j].getf_Max(); }else { k = matrix[i][j].getk_Min(); f= matrix[i][j].getf_Min(); } print("("); switch(f){ case 0:{ Traceback(i,k,matrix,number,operation,true); print(operation.get(k)); Traceback(k+1,j,matrix,number,operation,true); }break; case 1:{ Traceback(i,k,matrix,number,operation,true); print(operation.get(k)); Traceback(k+1,j,matrix,number,operation,false); }break; case 2:{ Traceback(i,k,matrix,number,operation,false); print(operation.get(k)); Traceback(k+1,j,matrix,number,operation,true); }break; case 3:{ Traceback(i,k,matrix,number,operation,false); print(operation.get(k)); Traceback(k+1,j,matrix,number,operation,false); }break; } print(")"); } } }