程序来平衡大括号

Question

嗨我有一个字符串数组,其值包含"{[()]}","} [] {","{()[]".现在我必须平衡每个起始大括号的大括号,例如{或[或(必须有一个右大括号.如果输入字符串具有相同数量的开始和结束括号,则输出为"是"否则" 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();
}

我在这里发现了一个类似的问题,但似乎它也在做同样的事情,只是它使用堆栈来存储括号,而我的问题明确指出括号是在一个字符串数组中.

无论如何,任何帮助或建议,以改善代码将不胜感激.

Answer 1

遵循以下算法:

1)使用堆栈

2)从左边读取字符串

3)如果当前读取的字母是开括号('(','{','['),则推送到堆栈

4)如果当前读取的字母是紧密支撑,则从堆栈弹出.

5)用当前的读支架检查弹出的支架

5.a)如果是配对支架.好的继续

5.b)如果堆栈为空,则打印NO

5.c)如果弹出char并且读取char不是一对则打印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);
}

请注意,在这种情况下,elses不是严格必需的.你可以只选择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);
}