Parse string récursivement avec StringTokenizer

Question

J'essaye d'analyser une chaîne récursivement avec StringTokenizer. La chaîne représente un arbre, sous la forme:

[(0,1),[(00,01,02),[()],[()]]] 

où l'information du noeud est stocké à l'intérieur de la parenthèse, tandis que les crochets sont les enfants d'un noeud, séparés par des virgules. Par exemple, cette chaîne représente cet arbre:

Si un nœud a quelque chose dans la parenthèse, il est un noeud normal, si elle n'a rien, il est une feuille.

J'ai écrit le code ci-dessous pour l'analyser, et cela fonctionne bien mais quand la récursivité se termine, il semble que le tokenizer n'a aucun autre jeton à analyser. Le problème est que lorsqu'il rencontre les dernières parenthèses (]]]) il saute directement au dernier en sautant les autres.

import java.util.*; 

public class ParseString 
{ 

public void setParameters(String parameters) throws Exception { 
    setParameters(new StringTokenizer(parameters, "[(,)]", true)); 

} 

public void setParameters(StringTokenizer tokenizer) throws Exception{ 

    String buf; 
    try{ 
     if (!(buf = tokenizer.nextToken()).equals("[")) 
     throw new Exception("Malformed string, found " + buf + "instead of ["); 
     boolean isLeaf = setWeights(tokenizer); 
     System.out.println("Leaf: " + isLeaf); 
     while (!(buf = tokenizer.nextToken()).equals("]")) { 
     do{ 
      setParameters(tokenizer); 
     }while (!(tokenizer.nextToken().equals("]"))); 
     if (!(buf = tokenizer.nextToken()).equals(",")) 
      break; 
     } 
    }catch(Exception e){e.printStackTrace();} 
    } 


    public boolean setWeights(StringTokenizer tokenizer) throws 
Exception{ 
     String buf; 
     if(!(buf = tokenizer.nextToken()).equals("(")) 
     throw new Exception("Malformed string, found "+ buf + "instead of ("); 
    do{ 
     buf = tokenizer.nextToken(); 
     if(buf.equals(")")){ 
     return true; 
    } 
    if(!buf.equals(",")) 
     System.out.println(buf); 
    }while(!tokenizer.nextToken().equals(")")); 
    return false; 
    } 


    public static void main(String[] args) 
    { 
    ParseString ps = new ParseString();  
    try{ 
     ps.setParameters("[(0,1),[(00,01,02),[()],[()]]]"); 
    }catch(Exception e){e.printStackTrace();} 
    } 
} 

C'est la sortie je l'exécuter:

0 
1 
Leaf: false 
00 
01 
02 
Leaf: false 
Leaf: true 
Leaf: true 
java.util.NoSuchElementException 
    at java.util.StringTokenizer.nextToken(StringTokenizer.java:349) 
    at ParseString.setParameters(ParseString.java:22) 
    at ParseString.setParameters(ParseString.java:7) 
    at ParseString.main(ParseString.java:51) 

Une autre chose: l'analyseur doit être en mesure d'analyser un arbre générique, non seulement celui-ci. Si quelqu'un peut résoudre ce problème, je serai heureux.

Answer 1

Vous appelez tokenizer.nextToken() sans vérifier si un jeton suivant est disponible (cela peut être vérifié en appelant tokenizer.hasMoreTokens()). Vous devez vérifier si d'abord, et si hasMoreTokens() renvoie false, il suffit de quitter la méthode en appelant return;.

Mais l'OMI, il est préférable de mettre tous les jetons dans une première liste, vous pouvez itérer à travers elle d'une manière plus facile:

String s = "[(0,1),[(00,01,02),[()],[()]]]"; 
StringTokenizer strtok = new StringTokenizer(s, "[(,)]", true); 
// put tokens in a list 
List<String> list = new ArrayList<>(); 
while (strtok.hasMoreTokens()) { 
    list.add(strtok.nextToken()); 
} 
// parse it, starting at position 0 
parse(list, 0); 

// parse method 
public void parse(List<String> list, int position) { 
    if (position > list.size() - 1) { 
     // no more elements, stop 
     return; 
    } 

    String element = list.get(position); 
    if (")".equals(element)) { // end of node 
     // is leaf if previous element was the matching "(" 
     System.out.println("Leaf:" + "(".equals(list.get(position - 1))); 
    } else if (!("[".equals(element) || "(".equals(element) || "]".equals(element) || ",".equals(element))) { 
     // print only contents of a node (ignoring delimiters) 
     System.out.println(element); 
    } 

    // parse next element 
    parse(list, position + 1); 
} 

La sortie est:

0 
1 
Leaf:false 
00 
01 
02 
Leaf:false 
Leaf:true 
Leaf:true 

---

Si vous voulez une sortie imbriquée/identifiée, vous pouvez ajouter une variable level à la méthode parse:

public void parse(List<String> list, int position, int level) { 
    if (position > list.size() - 1) { 
     return; 
    } 
    String element = list.get(position); 
    int nextLevel = level; 

    if ("[".equals(element)) { 
     nextLevel++; 
    } else if ("]".equals(element)) { 
     nextLevel--; 
    } else if (")".equals(element)) { 
     for (int i = 0; i < nextLevel; i++) { 
      System.out.print(" "); 
     } 
     System.out.println("Leaf:" + "(".equals(list.get(position - 1))); 
    } else if (!("(".equals(element) || "]".equals(element) || ",".equals(element))) { 
     for (int i = 0; i < nextLevel; i++) { 
      System.out.print(" "); 
     } 
     System.out.println(element); 
    } 

    parse(list, position + 1, nextLevel); 
} 

Ensuite, si je l'appelle (en utilisant la même liste que ci-dessus):

// starting at position zero and level zero 
parse(list, 0, 0); 

La sortie sera:

0 
    1 
    Leaf:false 
    00 
    01 
    02 
    Leaf:false 
     Leaf:true 
     Leaf:true 

Tous les éléments du même niveau auront la même indentation.

Answer 2

Je pense que vous pourriez consommer ] deux fois dans les boucles imbriquées dans certains cas, en consommant potentiellement la parenthèse fermante du parent.

Je venais de rendre la structure plus évidente, peut-être de la façon suivante:

// Precondition: '[' expected 
// Postcondition: Matching ']' consumed 
void parseNode(StringTokenizer st) { 
    if (!st.nextToken().equals("[")) { 
    throw new RuntimeException("[ expected parsing node."); 
    } 
    boolean leaf = parseWeights(st); 
    System.out.println("isleaf: " + leaf); 

    // Behind ')': Parse children if any. 

    String token = st.nextToken(); 
    while (token.equals(",")) { 
    parseNode(st); 
    token = st.nextToken(); 
    } 
    if (!token.equals("]")) { 
    throw new RuntimeException("] expected."); 
    } 
} 

// Precondition: '(' expected 
// Postcondition: Matching ')' consumed 
boolean parseWeights(StringTokenizer st) { 
    if (!st.nextToken().equals("(")) { 
    throw new RuntimeException("(expected parsing node weights."); 
    } 
    String token = st.nextToken(); 
    if (token.equals(")") { 
    return true; 
    } 
    while(true) { 
    System.out.println(token); 
    token = st.nextToken(); 
    if (token.equals(")") { 
     break; 
    } 
    if (!token.equals(",") { 
     throw new RuntimeException(", or) expected parsing weights."); 
    } 
    token = st.nextToken(); 
    } 
    return false; 
}