Программа для балансировки фигурных скобок

Question

Привет, у меня есть строковый массив, который содержит значения как «{[()]}", "} [] {", "{() []". Теперь мне нужно сбалансировать фигурные скобки, например, для каждой начальной фигурной скобки, например. {или [или (должна быть закрывающая скобка). Если входная строка имеет одинаковое количество открывающих и закрывающих фигурных скобок, тогда выход «ДА» еще «НЕТ». Также, если строка имеет закрывающую фигуру перед Соответствующая открывающая скобка, а также выход будет «НЕТ». Таким образом, в основном вывод должен быть строковым массивом, который будет содержать такие значения, как это для вышеупомянутого массива входных строк: «ДА», «НЕТ», «НЕТ».

я написал следующую программу, которая имеет много если-то еще условие. Мне было интересно, если есть лучший способ в 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

Следуйте приведенным ниже Algo:

1) Использование стека

2) прочитать строку слева

3) нажать, чтобы стек, если текущее письмо чтения открыта скобка ('(', '{', '[')

4) pop из стека, если текущее прочитанное письмо близко.

5) Проверьте выскочил бандаж с текущим чтением скобкой

5.a), если это спаривание скобки. ok продолжить

5.б) если стек был пуст, то не печатать NO

5.c), если совал полукокса и читать символ не пара, то не печатать NO

6), когда все строки обрабатываются. проверьте длину стека.

6.a), если длина 0 печать ДА

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