/* Subject: Contest submission for problem #1, file 1.java */ /* twang22@imail.EECS.Berkeley.EDU */ /* Thu Sep 18 00:07:13 PDT 2003 */ /*___CONTEST_SUBMISSION___ twang22 1 */ /* Name: Ming-Hsiu Wang * Estimated Time: ~ 2 hours * Actual Time: ~ 5 hours * The biggest problem I ran into was not thinking through the design of the program * carefully enough. I drafted a design, implemented it, only to realize there were * some serious flaw in the design. So then I tried to "quick fix it", only to produce * more problems. I was successful only after abandoning sitting in front of the * computer and redo the design. I also didn't anticipate the amount of time for * the peripheral operations (getting inputs, setting up vars, parsing the * statmeents). Those took almost the same amount of time as the core algorithm itself*/ import java.io.*; import java.lang.*; import java.util.*; class P1 { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); Vector code = new Vector(); // the data-flow tree for the program String tmpStr = "", completeInput = ""; StringTokenizer st; boolean moreToProcess = true; // keeps track to see if there's more thing to process boolean canProcess = true; // true if a complete code is read int setNumber = 0, MAX_INPUT_ARRAY_SIZE = 1000; char[] input = new char[MAX_INPUT_ARRAY_SIZE]; clearArray(input, MAX_INPUT_ARRAY_SIZE); // get complete input while (br.read(input, 0, MAX_INPUT_ARRAY_SIZE) != -1) { completeInput = completeInput.concat(new String(input)); clearArray(input, MAX_INPUT_ARRAY_SIZE); } st = new StringTokenizer(completeInput, ";"); do { code = new Vector(); canProcess = false; // break the input into pieces, separated by ";" while (st.hasMoreElements()) { tmpStr = ((String) st.nextElement()).trim(); if (tmpStr.length() == 0) continue; code.add(new Statement(tmpStr.trim(), getType(tmpStr))); // if read the stop statment, go to processing if (getType(tmpStr) == Statement.TYPE_STOP) { canProcess=true; break; } } if (st.hasMoreElements()) { moreToProcess = true; } else { moreToProcess = false; } if(canProcess) { // construct the data-flow tree and intialize data preProcess(code); // perform data-flow analysis analyzeTree(code); // output result if (((Statement) code.elementAt(0)).varsUsedBeforeDefined.isEmpty()) { System.out.println("Set " + setNumber + ": No use before definition"); } else { System.out.println("Set " + setNumber + ": Possible use before definition"); } setNumber++; } } while (moreToProcess); } // clear an array public static void clearArray(char arr[], int size) { for (int i = 0; i < size; i++) arr[i] = '\0'; } // traverse the tree public static boolean analyzeTree(Vector code) { boolean hasChanged = true; boolean markedValue = true; while (hasChanged) { // check if any update in the last traversal hasChanged = analyzeTreeHelper((Statement) code.elementAt(code.size() - 1), markedValue); markedValue = !markedValue; // flip the mark value } return true; } public static boolean analyzeTreeHelper(Statement currStatement, boolean markedValue) { if (currStatement.marked == markedValue) return false; Enumeration enum = currStatement.parents.elements(); Statement tmpStatement; boolean hasChanged = false; HashSet hs = new HashSet(); currStatement.marked = markedValue; // for each children, pass the varsUsedBeforeDefined to the parents, except those defined by the parents while (enum.hasMoreElements()) { tmpStatement = (Statement) enum.nextElement(); if (tmpStatement == null) continue; hs.addAll(currStatement.varsUsedBeforeDefined); if (tmpStatement.type == Statement.TYPE_ASSIGN) hs.remove(tmpStatement.assignedToVar); if (tmpStatement.varsUsedBeforeDefined.addAll(hs)) hasChanged = true; } enum = currStatement.parents.elements(); // recursive call while (enum.hasMoreElements()) { tmpStatement = (Statement) enum.nextElement(); if (tmpStatement == null) continue; hasChanged = (analyzeTreeHelper(tmpStatement, markedValue) || hasChanged); } return hasChanged; } // initialize variable and construct the tree public static void preProcess(Vector code) { Enumeration enum = code.elements(); Statement currStatement; Statement prevParent = null; while (enum.hasMoreElements()) { currStatement = (Statement) enum.nextElement(); currStatement.addParent(prevParent); // add the previous statement as a parent currStatement.getUsedVars(); // collect the variables used by the statement prevParent = currStatement; currStatement.preProcess(code); // additional preprocessing } } // return whether the statement is a stop, if or assign statement public static int getType(String str) { str = str.trim(); int index = str.indexOf(":"); if (index < 0) return -2; if (str.substring(index + 1).trim().startsWith("if")) return Statement.TYPE_IF; if (str.substring(index + 1).trim().startsWith("stop")) return Statement.TYPE_STOP; return Statement.TYPE_ASSIGN; } } class Statement { public static int TYPE_IF = 1; public static int TYPE_STOP = -1; public static int TYPE_ASSIGN = 0; public Vector parents = new Vector(); public Vector children = new Vector(); public HashSet varsUsedBeforeDefined = new HashSet(); // collection of vars that can be used starting from this statement but hasn't been defined public String assignedToVar = null; // store the variable that is defined by this statment public boolean marked = false; public String line; public int type; // -1 = stop, 0 = assignment, 1 = if Statement(String line, int type) { this.line = line; this.type = type; } public void addParent(Statement parent) { parents.add(parent); if (parent != null) parent.children.add(this); } public String toString() { return line; } // get all the variables used by this statement public void getUsedVars() { if (type == TYPE_STOP) return; int index1; int index2; String args; StringTokenizer st; index1 = line.indexOf('('); index2 = line.indexOf(')'); args = line.substring(index1 + 1, index2).trim(); st = new StringTokenizer(args, ","); while (st.hasMoreElements()) varsUsedBeforeDefined.add(st.nextElement()); } // process the statement based on its type public void preProcess(Vector code) { int lastIndex; int index1; int index2; Statement tmpStatement; // if assigned, get the assignedToVar if (type == TYPE_ASSIGN) { index1 = line.indexOf(':'); index2 = line.indexOf('='); assignedToVar = (line.substring(index1 + 1, index2)).trim(); return; } // if stop, do nothing if (type == TYPE_STOP) { return; } // else get the goto line number lastIndex = line.lastIndexOf("goto"); index1 = Integer.valueOf(line.substring(lastIndex + 4).trim()).intValue(); tmpStatement = (Statement) code.elementAt(index1); children.add(tmpStatement); tmpStatement.parents.add(this); } }