遞歸和迭代方法找到丟失的括號

Question

對於此作業，規範很簡單。給你一個任意長度的文本文件 （可能有數千個字符）。要被認爲是正確的，它必須包含 括號內的匹配對{ },[ ]和()。括號內的任意數量的文本可以嵌套到任意深度（但不能太深，以至於需要擔心堆棧溢出）。不包含括號的文件 非常正確。當您發現一對不匹配的括號時，您必須報告文件中的括號及其索引。文件中的第一個字符是索引0. 例如，如果文件包含 此文件具有打開的{ and another { followed by) and }和一些文本。 由於{ at index 36 is closed by the )位於索引50，因此您的程序應報告不匹配。 您可以將文件的起始位置視爲超級opening bracket，該位置與任何 右括號不匹配。如果文件包含太多的右括號，則不匹配的opening bracket是該文件的開頭。您應該使用字符串STX（舊ascii start of text）報告此問題。例如，這個結束]沒有匹配的開放[。 在這種情況下，您的程序應報告不匹配，因爲 索引-1處的STX在索引13處由]關閉。同樣，您可以將文件末尾看作超級closing bracket，該索引與任何開頭括號不匹配。一個文件可能包含太多的開放括號。報告這一點，就好像在文件結束後，不匹配的closing bracket確實是一個（不存在的）右括號。例如，這個打開（沒有匹配）將此作爲不匹配重新指定，因爲索引10處的(在索引24處由EOF關閉。您的任務是編寫兩個方法，一個遞歸方法，recursiveMatch和一個迭代方法iterativeMatch來處理一個文件，並檢查是否括號匹配。當任一方法 檢測托架不匹配時，它應該拋出類的例外 Matchfail。在一個Matchfail對象中的信息應包括在文件中的不匹配的括號及其索引。

這裏是我的代碼至今：

import java.io.File ; 
import java.io.FileReader ; 
import java.io.IOException ; 

/** 
* Development driver for Assignment #4, matching brackets. 
* 
* @author lou 
* @param args[0] 
*   name of a file to check 
*/ 
public class Assign4 { 

public static void main(String[] args) { 
/* 
* Check that the user has supplied a file name, and that the file 
* exists and is readable. 
*/ 
if (args.length <= 0) { 
    System.out.println("Usage: java Assign4 <filename>") ; 
    System.exit(1) ; 
} 
String fileName = args[0] ; 
File handle = new File(fileName) ; 
if (!(handle.exists() && handle.canRead())) { 
    System.out.println("Please check that file \"" + fileName 
     + "\" exists and is readable.") ; 
    System.exit(2) ; 
} 
/* 
* Create an input stream of type FileReader to read the file character 
* by character. This can throw a (checked) IOException so we need to 
* wrap it in a try/catch block. 
* 
* It's good practice to always close a FileReader to avoid 
* a resource leak (resources that are allocated but not released). If 
* src is not null, resources may have been allocated even if creation of 
* the FileReader fails and we should attempt a close to free them. 
* Closing a file reader can itself throw an IOException, so we need a 
* nested try/catch block. 
*/ 
FileReader src = null ; 
try { 
    src = new FileReader(handle) ; 
} catch (IOException ex) { 
    System.out.println("Exception while opening file \"" + 
     fileName + "\" for read.") ; 
    System.out.println("Exception: " + ex) ; 
    try { 
if (src != null) src.close() ; 
    } catch (IOException closeEx) { 
System.out.println(
    "Exception while closing file \"" + fileName + "\".") ; 
System.out.println("Exception: " + closeEx) ; 
    } 
    System.exit(3) ; 
} 
/* 
* Try the recursive match method first. A MatchFail exception is 
* certainly a possibility. Allow that other exceptions might be thrown 
* but don't attempt to do anything. 
*/ 
MatchBrackets matcher = new MatchBrackets() ; 
try { 
    matcher.recursiveMatch(src) ; 
    System.out.println("Brackets match (recursive)!") ; 
} catch (MatchFail ex) { 
    System.out.println("A bracket on its own is up to no good!") ; 
    System.out.println(ex) ; 
} catch (Exception ex) { 
    System.out.println("Unexpected exception "+ex) ; 
} 
/* 
* We need to return to the beginning of the file to test the iterative 
* match. For a FileReader, this requires closing and reopening the file. 
*/ 
try { 
    System.out.println("Attempting close and reopen.") ; 
    src.close() ; 
    src = new FileReader(handle) ; 
} catch (IOException ex) { 
    System.out.println("Exception while reopening file \"" + fileName 
    + "\" for read.") ; 
    System.out.println("Exception: " + ex) ; 
    try { 
if (src != null) src.close() ; 
    } catch (IOException closeEx) { 
System.out.println(
    "Exception while closing file \"" + fileName + "\".") ; 
System.out.println("Exception: " + closeEx) ; 
    } 
    System.exit(3) ; 
} 
/* 
* Try the iterative match method. 
*/ 
try { 
    matcher.iterativeMatch(src) ; 
    System.out.println("Brackets match (iterative)!") ; 
} catch (MatchFail ex) { 
    System.out.println("A bracket on its own is up to no good!") ; 
    System.out.println(ex) ; 
} catch (Exception ex) { 
    System.out.println("Unexpected exception "+ex) ; 
} 
/* 
* Close the file and we're done. 
*/ 
try { 
    src.close() ; 
} catch (IOException ex) { 
    System.out.println(
     "Exception while closing file \"" + fileName + "\".") ; 
    System.out.println("Exception: " + ex) ; 
    System.exit(3) ; 
} 
return ; 
} 
} 

和

import java.io.FileReader ; 
import java.io.IOException ; 
import java.util.ArrayDeque ; 

/** 
    Skeleton for the MatchBrackets class. 
*/ 
public class MatchBrackets { 

    /** 
    * Make a constant so it's clear we're recognising end-of-file. 
    */ 
    private final int EOF = -1 ; 

    /** 
    * A helper method to encapsulate the activity of reading a 
    * character. 
    * 
    * The FileReader class uses a common convention in character i/o: 
    * return each character as an int; this allows the value -1 to be 
    * used to indicate EOF. This little helper routine simply hides the 
    * try/catch statement that's required to handle the possibility 
    * that FileReader.read might throw an IOException. 
    * 
    * @param source 
    *  source of characters 
    * @return EOF on end-of-file or exception, or a single character 
    *   (as an int) 
    */ 
    private int getOneChar (FileReader source) 
    { 
    int charAsInt = EOF ; 
    try { 
    charAsInt = source.read() ; 
    } catch (IOException ex) { 
    System.out.println("Exception: " + ex) ; 
    charAsInt = EOF ; 
    } 
    return (charAsInt) ; 
    } 

/** 
* Recursive method to match brackets. 
* 
* @param src 
*  source of characters 
*/ 
public void recursiveMatch (FileReader src) 
     throws MatchFail 
{ 
/* 
    You must write a proper body for recursiveMatch. The bit of code below 
    is just to show you how to use getOneChar and throw an exception. 
*/ 
int charAsInt = getOneChar(src) ; 
if (charAsInt != EOF) { 
    char firstChar = (char) charAsInt ; 
    System.out.println(
     "The first character of the file is '" + firstChar + "'.") ; 
} else { 
    System.out.println("This file is empty!") ; 
} 
throw new MatchFail("You must write recursiveMatch!",42, 
      Character.toString('}'),42) ; 
} 

/** 
* Iterative method to match brackets. 
* 
* @param src 
*  source of characters 
*/ 
public void iterativeMatch (FileReader src) throws MatchFail 
{ 
    /* 
    You must write a proper body for this method, too. 
    */ 
    throw new MatchFail() ; 
} 

} 

和

/** 
Exception class for use by the bracket matching methods. 
<p> 
When a bracket mismatch is detected, this exception object should be 
created, loaded with information about the mismatched pair of brackets, and 
thrown. 
</p><p> 
The information provided should include the opening bracket and its index in 
the file, and the closing bracket and its index in the file. 
For a file containing K characters, character indices range from 0 to K-1. 
By definition, 
<ul> 
<li> the `character' before the start of the file has index -1 and is 
represented by the string "STX" (start of text).</li> 
<li> the `character' after the end of the file has index K and is 
    represented by the string "EOF" (end of file).</li> 
</ul> 
</p><p> 
MatchFail is subclassed from Exception, hence it is a checkable exception 
and methods that might throw MatchFail must declare the exception with a 
throws clause. 
    */ 

public class MatchFail extends Exception 
{ 

/** 
Index of opening bracket of the mismatched pair. 
*/ 
private int openNdx ; 

/** 
String representation of the opening bracket of the mismatched 
pair. 
*/ 
private String openBkt ; 

/** 
Index of closing bracket of the mismatched pair. 
*/ 
private int closeNdx ; 

/** 
String representation of the opening bracket of the mismatched 
pair. 
*/ 
private String closeBkt ; 

/** 
Convenience constructor to set all attributes. 
*/ 
public MatchFail (String openBkt, int openNdx, 
     String closeBkt, int closeNdx) 
{ this.openBkt = openBkt ; 
this.openNdx = openNdx ; 
this.closeBkt = closeBkt ; 
this.closeNdx = closeNdx ; 
} 

/** 
Constructor. 
<p> 
Initialise the attributes to values that are obviously invalid so it's 
easy to detect algorithm errors. 
</p> 
*/ 
public MatchFail() 
{ 
    this("invalid",-10,"invalid",-10) ; 
} 

/** Retrieve the opening bracket. */ 
public String getOpenBkt() { return (openBkt) ; } 

/** Retrieve the index of the opening bracket. */ 
public int getOpenIndex() { return (openNdx) ; } 

/** Retrieve the closing bracket. */ 
public String getCloseBkt() { return (closeBkt) ; } 

/** Retrieve the index of the opening bracket. */ 
public int getCloseIndex() { return (closeNdx) ; } 

/** Set the opening bracket. */ 
public void setOpenBkt (String openBkt) { this.openBkt = openBkt ; } 

/** Set the index of the opening bracket. */ 
public void setOpenIndex (int openNdx) { this.openNdx = openNdx ; } 

/** Set the closing bracket. */ 
public void setCloseBkt (String closeBkt) { this.closeBkt = closeBkt ; } 

/** Set the index of the closing bracket. */ 
public void setCloseIndex (int closeNdx) { this.closeNdx = closeNdx ; } 

/** Return a string representation of the exception. */ 
public String toString() 
{ 
    String rep = "'"+openBkt+"' at index "+openNdx+" matched to '" + 
     closeBkt+"' at index "+closeNdx ; 
    return (rep) ; 
} 

} 

我遇到的問題是在爲了尋找托架和報告下落不明支架位於索引創建遞歸和迭代方法。我真的不明白我應該如何做到這一點。任何幫助都將不勝感激！ 謝謝。

Answer 1

當您解析文檔時，每次遇到啓動程序並使用當前計數器循環變量值將它們添加到堆棧中時，請創建一個新文件。

public class Bracket { 
    int location; 
    char bracket; 

    public Bracket(int loc, char b) { 
     location = loc; 
     bracket = b; 
    } 

    public char getBracket() { return bracket; } 
      public int getLoc() { return location; } 

    public static boolean isStarter(char b) { 
     return b == '(' || b == '{'; // || etc.... 
    } 

    public boolean equals(Bracket other) { 
     return bracket == other.getBracket(); 
    } 

    public char getMatching() { 
     switch(bracket) { 
      case '(': return ')'; 
      // so on and so forth 
     } 
    } 

    public boolean matches(char other) { 
     return (getMatching() == other); 
    } 
} 

然後，在您的代碼： 堆棧堆棧=新堆棧<>（）;

// in your loop 
if (Bracket.isStarter(currentCharacter)) { 
    stack.push(new Bracket(currentLocation, currentCharacter)); 
} else { 
    if (stack.peek().matches(currentCharacter)) 
    stack.pop(); 
    else { 
    Bracket b = stack.pop(); 
    System.out.println("Mismatch error " + b.getBracket() + 
     " at character position " + b.getLoc() + 
     " followed by a " + currentCharacter + 
     " at position " + currentPosition + "."); 
    } 
} // something on this order at least 

Answer 2

//Below Code is for checking if given string is well formatted with Brackets 
// 123{456}[1+2] is well formatted and a valid Input/String/Expression 
//123{[456}] is not well formatted and not a valid Input/String/Expression 
    using System; 
    using System.Collections.Generic; 
    using System.Linq; 
    using System.Text; 
    using System.Threading.Tasks; 

    namespace CodeProject 
    { 
     class JsonFormattingCheck 
     { 
      Stack<char> CheckStack; 
      public JsonFormattingCheck() 
      { 
       CheckStack = new Stack<char>(); 
      } 

      public bool ValidInput(string input) 
      { 
       bool valid = true; 
       char currentliteral; 
       if (input.Contains("(") == true || input.Contains("[") == true || input.Contains("}") == true || input.Contains(")") == true || input.Contains("]") == true || input.Contains("}") == true) 
       { 
        foreach (char literal in input) 
        { 
         if(literal == '{' || literal == '(' || literal == '[') 
         { 
          CheckStack.Push(literal); 
         } 
         else if (literal == '}' || literal == ')' || literal == ']') 
         {       
          if (CheckStack.Count() == 0) 
           valid = false; 
          else 
          { 
           currentliteral = CheckStack.Pop(); 
           for (; currentliteral != '{' && currentliteral != '(' && currentliteral == '[';) 
           { 
            currentliteral = CheckStack.Pop(); 
           } 

           switch(currentliteral) 
           { 
            case '{': 
             if (literal != '}') 
              valid = false; 
              break; 
            case '[': 
              if (literal != ']') 
               valid = false; 
              break; 
            case '(': 
              if (literal != ')') 
               valid = false; 
              break; 
           } 
          } 
         } 
         if (valid == false) 
          break; 
        } 
       } 
       return valid; 
      } 
     } 
    } 


    ---- 
    using System; 
    using System.Collections.Generic; 
    using System.Linq; 
    using System.Text; 
    using System.Threading.Tasks; 

    namespace CodeProject 
    { 
     class Program 
     { 
      static void Main(string[] args) 
      { 
       JsonFormattingCheck json = new JsonFormattingCheck(); 

       //Test Data 
       string s = "123(233){212}"; 
       s = "{{2247]}}["; 

       bool valid = json.ValidInput(s); 
       if (valid == true) 
        Console.WriteLine(s+" valid"); 
       else 
        Console.WriteLine(s + " Invalid"); 
       Console.ReadLine(); 
      } 
     } 
    }