Big O解析のための擬似コードを解析するコード

Question

現在、txtファイルから擬似コードを読み取り、擬似コードのBig O表記を新しいtxtファイルとして出力するプログラムをコーディングしようとしています。私は、コードの時間的複雑さを見つけるために必要な主要情報のforループを解析する方法を見つけるのに苦労しています。たとえば：

"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)) 

試してみて、私が求めているものを簡単にするためには、ここで私が行うことに割り当てられたプロジェクトの説明です：

説明： ネストされたJavaのを解析するプログラムを書く」「のために"ループし、入力ファイルに与えられたコードのBig-O表記の見積もりを提供します。特に、入力ファイルには、適切なJava構文のネストされた "for"ループが含まれており、（1） "ループ"と "for"ループのみに制限されています（ "または" do-while （2）単純な操作+（プラス）、 - （マイナス）、*（乗算）および/（除算） 「+」、「 - 」、「+ =」、「 - =」、「=」、「/ =」の略語も使用できます。簡単にするために、入力コードはJava言語の下にあり、構文エラーはなく、メソッド/関数は含まれていないと仮定できます。

入力/出力： 入力ファイル ".txt"は、最初の3行が異なる変数セットを記述するテキストファイルです。ライン＃1は、BigO推定結果に使用すべき推定変数を記述する。 2行目は、各ループの制御変数を示しています。 3行目はループ/ネストループの本体に現れる変数を記述します。出力ファイル "_BigO.txt"に ".txt"という名前のファイルのBig-O推定値を書き込みます。見積もりが得られない場合は、理由をそのファイルに説明してください。私がこれまで持って何

の上に表示 ：

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

これはパースが解決された場合でも、トリッキーかなりトリッキーになります:)

あなたがそれをしたい場合は

例適切には、トークン化のためにStreamTokenizerを使用し、上の言語全体の再帰的な降下構文解析ツールを構築することができます。

また、行単位でブロックを追加して処理することもできます。このケースでは、このスニペットを使用した「部品」にループ初期化子、条件や増分を抽出得ることができます：あなたは部品の既存の表現パーサーを使用することができますようにしたいどのように洗練されたに応じて、

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

- またはあなたが扱うことができるケースのいくつかの前提条件と一致することを確認してください。