Code, der durch Pseudo-Code für große O-Analyse analysiert

Question

Ich versuche derzeit, ein Programm zu programmieren, das Pseudocode aus einer TXT-Datei liest und die Big-O-Notation für den Pseudocode als neue TXT-Datei ausgibt. Ich bemühe mich, eine Möglichkeit zu finden, die for-Schleifen für die Schlüsselinformationen zu analysieren, die benötigt werden, um die zeitliche Komplexität des Codes zu finden. Zum Beispiel:

"input02.txt" 
n m /* The estimate variable */ 
i j /* The control variable in the for loop */ 
tmp x j /* Variable(s) appeared in the loop body */ 
for (i=0; i<n*m; i*=2) { 
    for (j=0; j<n; j++) { 
     tmp = tmp + 3; 
     x--; 
     j++; 
    } 
} 
"input02_BigO.txt" 
O(n * log(n*m)) 

Um zu versuchen und zu vereinfachen, was ich fragen, ist hier die Beschreibung des Projekts ich tun zugewiesen wurde:

Beschreibung: Schreiben Sie ein Programm auf Java‘verschachtelt Analyze„für "Schleifen und liefern die Big-O-Notation Schätzung für die bereitgestellten Code in der Eingabedatei gegeben. Insbesondere enthält die Eingabedatei die verschachtelten "for" -Schleifen in einer geeigneten Java-Syntax und ist auf (1) höchstens 2 "for" -Schleifen und nur für "for" -Schleifen beschränkt (also nicht "while" oder "do-while "Schleifen" (2) einfache Operationen + (Plus), - (Minus), * (Multiplikation) und/(Division). Beachten Sie, dass Shorthanded-Operationen "++", "-", "+ =", "- =", "=" und "/ =" ebenfalls zulässig sind. Der Einfachheit halber können Sie davon ausgehen, dass der Eingabecode in Java geschrieben ist und keine Syntaxfehler sowie keine beteiligten Methoden/Funktionen enthält.

Eingabe/Ausgabe: Eingabedatei ".txt" ist eine Textdatei, in der die ersten drei Zeilen unterschiedliche Variablensätze beschreiben. Zeile # 1 beschreibt die Schätzvariablen, die im Ergebnis der BigO-Schätzung verwendet werden sollten. Zeile # 2 beschreibt die Kontrollvariablen in jeder Schleife. Zeile 3 beschreibt Variablen, die im Schleifen-/Nested-Loop-Body erscheinen. Ausgabe Schreiben Sie in die Datei "_BigO.txt" die Big-O-Schätzung des Codes in der Datei ".txt". Wenn Sie den Kostenvoranschlag nicht angeben können, erläutern Sie in dieser Datei die Gründe.

Beispiel: oben

gezeigt

Was ich habe, so weit:

import java.util.*; 
import java.io.*; 
public class Big_O_Analysis { 
    public static void main(String[] args) throws FileNotFoundException { 
     /* ASKS USER TO INPUT NAME OF TXT FILE TO BE READ */ 
     Scanner keyboard = new Scanner(System.in); 
     System.out.println("Enter file name (without '.txt': "); 

     /* STORES FILE NAME TO READ INPUT FILE AND CREATE OUTPUT FILE*/ 
     String fileName = keyboard.nextLine(); 
     String inputFile = fileName + ".txt"; 
     String outputFile = fileName + "_BigO.txt"; 

     /* READS INPUT FILE AND ANALYZES FOR LOOPS AND ASSIGNMENT STATEMENTS */ 
     File file = new File(inputFile); 
     Scanner input = new Scanner(file); 
     String line = input.nextLine(); 
     String[] complexity = new String[10];         // Holds time complexity 
     while (input.hasNext())             // Search for line with for loop 
     { 
      while (!line.startsWith("for")) 
      { 
       line = input.nextLine(); 
      } 

      // PARSE THROUGH LOOP 
      String[] forLoop = line.split(";");         // Splits loop into 3 parts by the ';', ex: "for (i=0", "i<10","i++)" 

      // Keeps control variable part of for loop 
      String[] forLoopStart = forLoop[0].split("(");      // Splits "for (i=0" into "for " and "i=0" 
      String initialization = forLoopStart[1];       // Stores the start of the for loop "i=0" 
      char control = initialization.charAt(0);       // Stores control variable 'i' 
      int start = Integer.parseInt(initialization.substring(2));   // Stores start value of control '0' 


      // Keeps estimate variables 
      String termination = forLoop[1].substring(2);      // Stores termination of loop. "i<10" -> "10" or "i<n" -> "n" or "i<n*m" -> "n*m" 
      int end;               // Initializes termination value for loop 
      int index = 0; 
      for (int i = 0; i<termination.length(); i++)      // Gets termination value when it is a number: "i<10" 
      { 
       index++; 
      } 
      end = Integer.parseInt(termination); 


      // Keeps increment values 
      String increment = forLoop[2].substring(0,forLoop[2].length()-1); // Stores increment section of loop. "i++)" -> "i++" or "i+=10" or "i*=i" 
      String inc = increment.substring(1,3);        // Stores increment. "++", "*=", etc 
      if (inc == "++" || inc == "--") 
       complexity[1] = termination; 
      else if(inc == "*=" || inc == "/=")         // Log 
       complexity[1] = "log(" + termination + ")"; 
      else if (inc == "+=" || inc == "-=")        // Jump 
       complexity[1] = termination + "/" + increment.substring(3); 


      String factor = "";             // Stores factor of increment. "2", "10", "n" 
      boolean factorDigits = false;          // The following boolean values test to see if the factor is just a number, variable by itself, or variable with number 
      boolean factorVar = false; 
      boolean factorMix = false; 
      int fac;               // If factor is just a number 
      for (int i = 3; i<increment.length(); i++) 
      { 
       if (Character.isDigit(increment.charAt(i))) 
        factorDigits = true; 
       else if (Character.isLetter(increment.charAt(i))) 
        factorVar = true; 
      } 
      if (factorDigits == true && factorVar == false) 
      { 
       factor = factor + increment.substring(3); 
       fac = Integer.parseInt(factor); 
      } 
      else if (factorDigits == false && factorVar == true) 
      { 
       factor = factor + increment.substring(3); 
      } 
      else if (factorDigits == true && factorVar == true) 
      { 
       factorMix = true; 
       factor = factor + increment.substring(3); 
      } 




      // Reads for assignment statements 
      line = input.nextLine(); 
      int assignments = 0; 
      while (input.hasNext() && !line.startsWith("for")) 
      { 
       assignments++; 
       line = input.nextLine(); 
      } 
      complexity[0]= Integer.toString(assignments); 

      // Analyzes loop 


     } 

     /* FORMS COMPLEXITY */ 
     String timeComplexity = ""; 

     /* FORMS COMPLEXITY INTO BIG O NOTATION */ 
     String bigO = "O(" + timeComplexity + ")"; 

     /* CREATES AND WRITES A FILE OF THE BIG O ESTIMATE */ 
     PrintWriter output = new PrintWriter(outputFile); 
     output.print(bigO); 
    } 
} 

Answer 1

Dieser schwierig sein wird ziemlich schwierig, auch wenn das Parsen gelöst :)

Wenn Sie es tun wollen richtigerweise könnte man einen StreamTokenizer für die Tokenisierung verwenden und einen rekursiven Descent-Parser für die gesamte oben stehende Sprache erstellen.

Alternativ können Sie einige zusätzliche Annahmen treffen und Blöcke zeilenweise behandeln. In diesem Fall könnten Sie erhalten die Schleife initializer extrahieren, Zustand und Schritt auf „Teile“ mit diesen Schnipsel:

if (line.startsWith("for") { 
    int cut0 = line.indexOf('('); 
    int cut1 = line.lastIndexOf(')'); 
    String parts = line.substring(cut0+1, cut1).split(";"); 
    ... 

Je nachdem, wie hoch entwickelt möchten Sie Sie einen vorhandenen Ausdruck Parser auf die Teile verwenden könnte sein - oder stellen Sie einfach sicher, dass sie einigen Annahmen für die Fälle entsprechen, mit denen Sie umgehen können ...