LinkBack URL
About LinkBacks
Having trouble figuring out how to recursively do this.
It's me. I had posted here but that issue of the readin was done so I marked the thead as solved, or I'm going to soon. However, now I'm wondering how to recursively calcualate something. I'm going to post the whole program but the chief concern right now is with the getEpsilon() method and also you'd need to know about the ms ArrayList.
import java.util.Scanner; import java.io.File; import java.io.FileNotFoundException; import java.util.ArrayList; import java.util.HashSet; import java.util.Iterator; public class fsm { private static class FileParser { } private static class MySet { private ArrayList<Integer> intList; public MySet() { intList = new ArrayList<Integer>(); } public void add(Integer data) { intList.add(data); } public void remove() { intList.remove(0); } public int size() { return intList.size(); } public Integer get(int index) throws NullPointerException { return intList.get(index); } public ArrayList<Integer> getList() { return intList; } } static MySet[][] ms; static int characters; static HashSet<HashSet<Integer>> sos; public static void main(String[] args) { Scanner s = null; Scanner s2 = null; ArrayList<Integer> stateList = new ArrayList<Integer>(); ArrayList<Character> alphabet = new ArrayList<Character>(); ArrayList<String> transitionLines = new ArrayList<String>(); ArrayList<String[]> splitArray = new ArrayList<String[]>(); int numOfStates = 0; try { s = new Scanner(new File(args[0])); } catch (ArrayIndexOutOfBoundsException aioobe) { System.out.println("Error!"); System.exit(1); } catch (FileNotFoundException fnfe) { System.out.println("Error!"); System.exit(1); } numOfStates = s.nextInt(); System.out.println(numOfStates); String[][] splits = new String[numOfStates][2]; String line = s.nextLine(); if (line.equals("")) line = s.nextLine(); System.out.println(line); char[] chars = line.toCharArray(); char empty = ' '; String tab = "\t"; char tab2 = tab.charAt(0); for (int i =0; i < chars.length; i++) { if (chars[i]!= empty && chars[i]!=tab2) { alphabet.add(chars[i]); } } alphabet.add('¸'); System.out.println(alphabet.toString()); characters = alphabet.size(); for (int i=0; i < numOfStates; i++) { transitionLines.add(s.nextLine()); } System.out.println(transitionLines.toString()); for (int i =0; i < splits.length; i++) { splits[i] = transitionLines.get(i).split(":"); } for (int i =0; i < splits.length; i++) { for (int j=0; j < splits[i].length; j++) { System.out.println(splits[i][j]); } } // String[][] test = ArrayList<String[]> fredBowling = new ArrayList<String[]>(); for (int i =0; i < splits.length; i++) { fredBowling.add(splits[i][1].split("}")); } splits[0][1].split("}"); ArrayList<Integer> state = new ArrayList<Integer>(); for (int i=0; i < splits.length; i++) { state.add(Integer.parseInt(splits[i][0])); } // System.out.println(java.util.Arrays.toString(test)); // String smaller[] = new String[test.length]; ArrayList<ArrayList<String>> smaller = new ArrayList<ArrayList<String>>(); for (int i =0; i < fredBowling.size(); i++) { smaller.add(new ArrayList<String>()); for (int j = 0; j < fredBowling.get(i).length; j++) { int temp = fredBowling.get(i)[j].indexOf("{"); smaller.get(i).add(fredBowling.get(i)[j].substring(temp + 1)); } } // System.out.println(java.util.Arrays.toString(smaller)); // ArrayList<String[]> finale = new ArrayList<String[]>(); ArrayList<ArrayList<String[]>> finale = new ArrayList<ArrayList<String[]>>(); // for (int i =0; i < smaller.length; i++) // { // finale.add(smaller[i].split(",")); // } for (int i =0; i < smaller.size(); i++) { finale.add(new ArrayList<String[]>()); for (int j =0; j < smaller.get(i).size(); j++) { finale.get(i).add(smaller.get(i).get(j).split(",")); } } for (int i =0; i < finale.size(); i++) { for (int j =0; j < finale.get(i).size(); j++) { for (int k =0; k < finale.get(i).get(j).length; k++) { System.out.println("MySet[" + i + "]["+j +"].get(" + k + ") = " +finale.get(i).get(j)[k]); } } } ms = new MySet[finale.size()][finale.get(0).size()]; for (int i =0; i < finale.size(); i++) { // begin for for (int j =0; j < finale.get(i).size(); j++) { // begin for try{ ms[i][j] = new MySet(); for (int k =0; k < finale.get(i).get(j).length; k++) { // begin for if (finale.get(i).get(j)[k] != null && !finale.get(i).get(j)[k].equals("")) { // begin if ms[i][j].add(Integer.parseInt(finale.get(i).get(j)[k])); } // end if } // end for } // end try catch(ArrayIndexOutOfBoundsException aioobe) { System.err.println("Index " + i + "," + j + " is out of bounds."); } } // end for } // end for for (int i =0; i < ms.length; i++) { for (int j =0; j < ms[i].length; j++) { for (int k =0; k < ms[i][j].size(); k++) { System.out.println("ms[" + i + "]["+j +"].get(" + k + ") = "+ ms[i][j].get(k)); } } } int startingState = s.nextInt(); System.out.println("s:" + startingState); String fs = s.nextLine(); if (fs.equals("") || fs == null) fs = s.nextLine(); String[] firstHalf = fs.split("}"); int temp = firstHalf[0].indexOf("{"); String secondHalf = firstHalf[0].substring(temp+1); String[] finalHalf = secondHalf.split(","); ArrayList<Integer> finalState = new ArrayList<Integer>(); for (int i =0; i < finalHalf.length; i++) { if (finalHalf[i] != null && !finalHalf[i].equals("")) { finalState.add(Integer.parseInt(finalHalf[i])); } } System.out.println("Accepting state: " + finalState.toString()); System.out.println(getFinalStateFrom(0, 0).toString()); System.out.println(recursion1(0,0).toString()); System.out.println(getEpsilon().toString()); try { s2 = new Scanner(new File(args[1])); } catch (ArrayIndexOutOfBoundsException aioobe) { System.out.println("Error!"); System.exit(1); } catch (FileNotFoundException fnfe) { System.out.println("Error!"); System.exit(1); } } public static HashSet<Integer> getEpsilon() { HashSet<Integer> hs = new HashSet<Integer>(); ArrayList<Integer> temp = new ArrayList<Integer>(); // this is only here to store stuff and access it easier without an evil iterator hs.add(0); temp.add(0); // int i = 0; // used for the while loop below Integer temp2 = 0; // used to check if the next item in epsilon is null. MySet ms3 = new MySet(); ms3 = ms[0][ms[0].length -1]; if (ms3 == null) return hs; else { for (int i =0; i < ms3.size(); i++) hs.add(ms3.get(i)); } for (int i =0; i < ms3.size(); i++) { while (ms[ms3.get(i)][ms[0].length-1] !=null) { } } return hs; } public static HashSet<Integer> getLambdas(Integer state) { HashSet<Integer> hs = new HashSet<Integer>(); if (ms[state][characters - 1] != null) { for (int i =0; i < ms[state][characters - 1].size(); i++) { if (ms[state][characters - 1].get(i) != null) { hs.add(ms[state][characters -1].get(i)); } } } return hs; } public static HashSet<Integer> getFinalStateFrom(Integer state, Integer character) { ArrayList<Integer> al = new ArrayList<Integer>(); HashSet<Integer> hs = new HashSet<Integer>(); if (ms[state][character] != null) { for (int i =0; i < ms[state][character].size(); i++) { if (ms[state][character].get(i) != null) { hs.add(ms[state][character].get(i)); } } } // hs.addAll(getFinalStateFrom(state, characters - 1); System.out.println("Added: " + hs.toString()); hs.addAll(getLambdas(state)); System.out.println("Added: " + hs.toString()); return hs; } public static HashSet<Integer> recursion1(Integer state, Integer character) { HashSet<Integer> hs = new HashSet<Integer>(); for (Iterator<Integer> it = getFinalStateFrom(state,character).iterator(); it.hasNext();) { try { hs.addAll(getFinalStateFrom(getFinalStateFrom(it.next(), characters -1).iterator().next(), character)); } catch(java.util.NoSuchElementException nsee) { System.out.println("This element doesn't exist!"); } } return hs; } }
In the method
public static HashSet<Integer> getEpsilon()
{
HashSet<Integer> hs = new HashSet<Integer>();
ArrayList<Integer> temp = new ArrayList<Integer>(); // this is only here to store stuff and access it easier without an evil iterator
hs.add(0);
temp.add(0);
// int i = 0; // used for the while loop below
Integer temp2 = 0; // used to check if the next item in epsilon is null.
MySet ms3 = new MySet();
ms3 = ms[0][ms[0].length -1];
if (ms3 == null)
return hs;
else
{
for (int i =0; i < ms3.size(); i++)
hs.add(ms3.get(i));
}
for (int i =0; i < ms3.size(); i++)
{
while (ms[ms3.get(i)][ms[0].length-1] !=null)
{
}
}
return hs;
}
What I was going for is if there is an epsilon transition, basically if ms[0][ms[0].length-1] isn't empty to add the states in there. You always add 0 to start I think even if ms[0][ms[0].length-1] = null. Anyway, you add those states. Then for each of those states, you further loop to check each of the epsilon things in them. So if state 2 (a.k.a. ms[1]) and the epsilon has say 3, 5 as its closures, a.k.a. the values in the MySet my[1][ms[0].length-1] have more closures, say 4 and 1, then you add 2, 3, 5, 4, 1 and all the ones for ms[3][ms[0].length-1] and the closures of those, etc, until you either run out of closures, or you encounter a part where the only sets being added are already there, i.e. if one of them had a loop to 0 for instance.
To kind of summarize what I said,
ms[0][ms[0].length-1] = {1,2,3,4,5.....}
ms[1][ms[0].length-1] = {10, 11, 12, 13, 14}
ms[10][ms[0].length-1] = {15} // had to end it somewhere, though it could in theory go on much longer
ms[15][ms[0].length-1] = {};
ms[2][ms[0].length-1] = {8,9};
ms[8][ms[0].length-1] = {};
ms[9][ms[0].length-1] = {}; // I'm making it brief here
ms[3][ms[0].length -1] = {.......}
add (0, 1, 2, 3, 4, 5, 10, 11, 12, 13, 14, 15, 8, 9, .......);
This thread has been cross posted here:Although cross posting is allowed, for everyone's benefit, please read:
Java Programming Forums Cross Posting Rules
The Problems With Cross Posting
As I said, I've dealt with the read in issue. Now it's the recursive parts that are giving me confusion.
WARNING: Compiling that as is may possibly cause an infinite loop as there's nothing to change ms3. But how to change ms3 without changing the actual thing. Do I need a deep copy every time in the loop? ARGH!
Also, this isn't the only recursive issue I've got, only the start.
Reply With Quote
Related threads:
Re: Having trouble figuring out how to recursively do this.
