程序來平衡大括號

Question

嗨，我有一個字符串數組，包含值爲「{[（）]}」，「} [] {」，「{（）[]」。現在我必須平衡每個起始支撐的支撐，例如如果輸入字符串具有相同數量的開始和結束大括號，則輸出爲「是」，否則爲「否」。如果字符串在因此輸出必須是一個字符串數組，它將包含上述輸入字符串數組的這樣的值：「YES」，「NO」，「NO」。

我寫了下面的程序，它有很多的if-else條件。我不知道是否有在C＃什麼更好的辦法來解決這個問題。

static void Main(string[] args) 
{ 
    string[] arrBraces = Console.ReadLine().Split(' '); 
    string[] result = new String[arrBraces.Length]; 

    for (int i = 0; i < arrBraces.Length; i++) { 
    Console.WriteLine(arrBraces[i]); 
    int curly = 0, square = 0, round = 0; 

    foreach (char c in arrBraces[i]) { 
     if (c == '{') { 
     curly++; 
     } else if (c == '[') { 
     square++; 
     } else if (c == '(') { 
     round++; 
     } else if (c == '}') { 
     if (curly > 0) { 
      curly--; 
     } else { 
      curly = -1; 
      break; 
     } 
     } else if (c == ']') { 
     if (square > 0) { 
      square--; 
     } else { 
      square = -1; 
      break; 
     } 
     } else if (c == ')') { 
     if (round > 0) { 
      round--; 
     } else { 
      round = -1; 
      break; 
     } 
     } 
    } 

    if (curly == 0 && square == 0 && round == 0) { 
     result[i] = "YES"; 
    } else { 
     result[i] = "NO"; 
    } 
    } 

    foreach (string str in result) { 
    Console.WriteLine (str); 
    } 
    Console.ReadKey(); 
} 

我發現了一個類似的問題here，但似乎就像它也在做同樣的事情，就是這樣正在使用堆棧來存儲括號，而我的問題明確指出大括號是在一個字符串數組中。

反正任何幫助或建議，以改善代碼，將不勝感激。

Answer 1

按照下面的算法中：

1）使用堆棧

2）從左側

3）推到堆棧如果當前的讀信是開括號（讀字符串 '（'， '{'， '['）

4）如果當前讀取的字母是大括號，則從堆棧彈出。

5）檢查彈出支柱與當前讀支柱

5.A）如果配對梅開二度。好的繼續

5。b）如棧是空的，然後打印NO

5.C）如果彈出炭和讀炭沒有一雙然後打印NO

6）時被處理的所有的字符串。檢查堆棧的長度。

6.A），如果長度爲0打印YES

6.B）其他印刷NO

Answer 2

你肯定可以讓這個更簡潔：

public static bool CheckString(string input) 
{ 
    int braceSum = 0, squareSum = 0, parenSum = 0; 

    foreach(char c in input) 
    { //adjust sums 
     if (c == '{') braceSum++; 
     if (c == '}') braceSum--; 
     if (c == '[') squareSum++; 
     if (c == ']') squareSum--; 
     if (c == '(') parenSum++; 
     if (c == ')') parenSum--; 

     //check for negatives (pair closes before it opens) 
     if (braceSum < 0 || squareSum < 0 || parenSum < 0) return false; 
    } 
    return (braceSum == 0 && squareSum == 0 && parenSum == 0); 
} 

注意，在這種情況下，else s爲不是絕對必要的。您可以只爲if每個字符選項。在這裏使用else可能會有微觀的性能優勢，但我希望編譯器能夠優化任何差異。如果你不喜歡那樣，你也可以使用switch聲明。

爲了完整起見，下面是一個使用此功能的Main()：

static void Main(string[] args) 
{ 
    var input = Console.ReadLine(); 
    if (string.IsNullOrWhiteSpace(input)) 
     input = "{[()]} }[]{ {()[] {()[]} ({)}"; //get through tests faster 

    var data = input.Split(' ') 
        .Select(s => new {Input = s, Result = CheckString(s)?"YES":"NO"}); 

    foreach(var item in data) 
    { //guessing at input length here 
     Console.WriteLine("{0,-26} \t--{1,5}", item.Input, item.Result); 
    } 

    //just because the question asked for an array 
    var result = data.Select(i => i.Result).ToArray(); 

    Console.ReadKey(true); 
} 

一兩件事，是不是從這個問題清楚的是，這是否是合法的：

（{）}

這是合法的根據示例代碼，因爲這看起來像一個練習，它可能並不重要。但是，對於此練習中描述的現實世界問題，這經常（並非總是，但往往）是合法的，並且被認爲是「不平衡的」。如果這非常重要，你需要使用一個單一的Stack而不是個人的款項，以及您的CheckString()方法可能是這樣的：

public static bool CheckString(string input) 
{ //Use the closer rather than opener as the key. 
    // This will give better lookups when we pop the stack 
    var pairs = new Dictionary<char, char>() { 
     { '}','{' }, { ']','[' }, { ')','(' } 
    } 
    var history = new Stack<char>(); 

    foreach(char c in input) 
    { 
     if (pairs.ContainsValue(c)) history.Push(c); 
     if (pairs.ContainsKey(c) && (history.Count == 0 || history.Pop() != pairs[c])) 
      return false; 
    } 
    return (history.Count == 0); 
} 

Answer 3

 public static bool ValidBraces(String braces) 
     { 
      if (String.IsNullOrWhiteSpace(braces)) 
      { 
       //invalid 
       return false; 
      } 

      Stack<char> stack = new Stack<char>(); 

      for (int i = 0; i < braces.Length; i++) 
      { 
       //if its an open brace, stack 
       if (braces[i] == '{' || braces[i] == '[' || braces[i] == '(') 
       { 
        stack.Push(braces[i]); 
       } 
       else if (stack.Count != 0) 
       { 
        //if its a closed brace, compare with the complement and pop from stack 
        if (stack.Pop() != complement(braces[i])) 
        { 
         //invalid 
         return false; 
        } 
       } 
       else 
       { 
        //invalid, missing brace 
        return false; 
       } 
      } 

      if (stack.Count != 0) 
      { 
       //invalid, there are still some braces without match 
       return false; 
      } 

      //valid, success 
      return true; 
     } 

     private static char complement(char item) 
     { 
      switch (item) 
      { 
       case ')': 
        return '('; 
       case '}': 
        return '{'; 
       case ']': 
        return '['; 
       default: 
        return ' '; 
      } 
     } 

     //this is for test. Put it on some method. 
     System.Console.WriteLine("" + ValidBraces(""));//false 
     System.Console.WriteLine("()" + ValidBraces("()"));//true 
     System.Console.WriteLine("[(])" + ValidBraces("[(])"));//false 
     System.Console.WriteLine("[()]{}" + ValidBraces("[()]{}"));//true 
     System.Console.WriteLine("[({)]}" + ValidBraces("[({)]}"));//false 
     System.Console.WriteLine("[[()]{}" + ValidBraces("[[()]{}"));//false