は、私のアルゴリズムは正しいのでしょうか？ここ

Question

は、この問題に対する私の分析である：{{()}}、{}[]<>、<{}[]>、{<>[]}<> を私はちょうどこれらの4つの一致の形を考えるのであれば、それは複雑かもしれない：括弧が一致している条件の4種類があります。だから、角括弧がいつ一致しているかを調べようとします。 {と}をペアにすると、1つの括弧が奇数の位置にあり、そのペアが偶数の位置になければなりません。 {<>[]}<>を例にとると、{は奇数位置の第1の位置にあり、}は偶数位置の第6の位置にある。したがって、私はそれらをマークするために数字を使用します。'()'--1,9; '[]'--2,8; '<>' --3,7; '{}' --4,6したがって、2つの数字が加算されると10に等しい場合、これら2つの数字はペアを表します。次に、それらの数字をブラケット構造を表すために使用します。私は奇数の位置で括弧を引っ張り、偶数の位置に括弧をつけて（それらを表す番号を使用します）、奇数の位置と偶数の位置にそれぞれの項目を追加して、一致するものが10かどうかを確認します。私はそれがマッチだと言う。私のコードは以下の通りです：

/** Matching Brackets 
    * Tony 
    */ 
import java.util.*; 

public class Solution19 { 

    public static String process(String n) { 
    /** build a condition combination: */ 
    String newString = ""; 
    for (int i = 0; i < n.length(); i++) { 
     if (n.charAt(i) == '(' || n.charAt(i) == ')' || n.charAt(i) == '[' || n.charAt(i) == ']' 
      || n.charAt(i) == '<' || n.charAt(i) == '>' || n.charAt(i) == '{' || n.charAt(i) == '}') { 
     newString += n.charAt(i); 
     } 
    } 
    return newString; 
    } 


    public static String numForm(String s) { 
    String newone = ""; 
    for (int i = 0; i < s.length(); i++) { 
     switch(s.charAt(i)) { 
     case '(': newone += "1 ";break; 
     case ')': newone += "9 ";break; 
     case '[': newone += "2 ";break; 
     case ']': newone += "8 ";break; 
     case '<': newone += "3 ";break; 
     case '>': newone += "7 ";break; 
     case '{': newone += "4 ";break; 
     case '}': newone += "6 ";break; 
     } 
    } 
    return newone; 
    } 

    public static int[] intArray(String m) { 
    String[] stringArray = m.split(" "); 
    int[] intArr = new int[stringArray.length]; 
    for (int i = 0; i < stringArray.length; i++) { 
     intArr[i] = Integer.parseInt(stringArray[i]); 
    } 
    return intArr; 
    } 

    public static void printArray (int[] array) { 
    for (int n : array) { 
     System.out.print(n + " "); 
    } 
    } 

    public static int[] oddPosition (int[] array) { 
    int [] oddNumbers = new int[array.length/2]; 
    int j = 0; 
    for (int i = 0; i < array.length; i++) { 
     if ((i + 1) % 2 != 0) { 
     oddNumbers[j] = array[i]; 
     j ++; 
     } 
    } 
    return oddNumbers; 
    } 

    public static int[] evenPosition (int[] array) { 
    int [] evenNumbers = new int[array.length/2]; 
    int j = 0; 
    for (int i = 0; i < array.length; i++) { 
     if ((i + 1) % 2 == 0) { 
     evenNumbers[j] = array[i]; 
     j ++; 
     } 
    } 
    return evenNumbers; 
    } 

    public static boolean addsUpten (int [] array) { 
    boolean conditionSum = false; 
    boolean conditionSingle = false; 
    for (int i = 0; i < array.length; i++) { 
     int d = 0; 
     while (i + d < array.length) { 
     if (array[i] + array[i+d] == 10) { 
      conditionSingle = true; 
     } 
     conditionSum = (conditionSum || conditionSingle); 
     d ++; 
     } 
    } 
    return conditionSum; 
    } 




    public static void main(String[] args) { 

    Scanner sc = new Scanner(System.in); 
    int times = sc.nextInt(); 
    String voider = sc.nextLine(); 

    for (int i = 0; i < times; i ++) { 
     String formula = sc.nextLine(); 
     String processed = process(formula); 

     String numFormed = numForm(processed); 
     // System.out.println(numFormed); 
     int[] numArray = intArray(numFormed); 

     if (numArray.length % 2 != 0) { 
     System.out.print("0 "); 
     } 
     else { 
     int[] oddNumbers = oddPosition(numArray); 

     int[] evenNumbers = evenPosition(numArray); 


     if (addsUpten(oddNumbers) || addsUpten(evenNumbers) == true) { 
      System.out.print("0 "); 
     } 
     else { 
      System.out.print("1 "); 
     } 
     } 
    } 
    } 
} 

私は予想通り、それは動作するはずですし、それが動作したときに、私は入力：それは私に出力を与える

4 
(a+[b*c]-{d/3}) 
(a + [b * c) - 17] 
(((a * x) + [b] * y) + c 
auf(zlo)men [gy<psy>] four{s} 

：1 0 0 1（1 0、それが試合で表しますそれはマッチではないと表現する）。しかし、私が[^]<t>(z){<[^]<w>[{f}c]y[-][v]{<y>g<+()>(c){w{a{t}}}}>((a)w)}のようなものを長く入力すると、それはマッチですが、それは私に0を与えます。マッチかどうかを判断する方法は間違いありませんか？私は何を取りこぼしたか？長いコードを申し訳ありません、ちょうど("I find out if one bracket is on the odd position then his pair must be in a even position, vice versa.")ブラケットの一致を説明するこの方法が間違っているかどうか疑問に思っていますか？どうも！

Answer 1

あなたのアプローチには根本的な問題があります。ネストをうまくサポートしていません。

あなたは括弧のスタックを作成することによってこの問題を解決することができます

• あなたは閉じ括弧が表示されたらあなたは左括弧が表示されたら、あなたはスタック
• にそれをプッシュする、あなたはその左括弧をポップペアが一致しない場合は、スタックの試合からのペアは、
• を継続、またはスタックが空の場合は、STA場合不一致
• を報告し、それをスタック
• をオフにペアリングすることになっていますckはループの最後に空ではなく、不一致も報告します。