平衡牙套的程序

Question

您好，我有一个字符串数组，其中包含值“{[()]}”、“}[]{”、“{()[]”。现在我必须像每个起始大括号一样平衡大括号，例如{ 或 [ 或 (，必须有一个右大括号。如果输入字符串的左大括号和右大括号的数量相同，则输出为 "YES" else "NO"。另外，如果字符串有在匹配的左大括号之前，右大括号也会输出 "NO"。所以基本上，输出必须是一个字符串数组，其中包含上述输入字符串数组的值："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

你当然可以使它更简洁：

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 并不是绝对必要的。您可以 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);
}

问题中不清楚的一件事是这是否合法：

({)}

根据示例代码，这是合法的，因为这看起来像是练习，所以可能并不重要。但是，对于本练习描述的现实世界问题，这通常（并非总是，但经常）是不合法的，并且被认为是 "unbalanced"。如果确实重要，您需要使用单个 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 2

遵循以下算法：

1) 使用堆栈

2) 从左边读取字符串

3) 如果当前读取的字母是左大括号 ('(','{','[')

4) 如果当前读取的字母是右括号，则从堆栈中弹出。

5) 用当前读取的大括号检查弹出的大括号

5.a) 如果是配对大括号。好的继续

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

5.c) 如果弹出的字符和读取的字符不是一对则打印 NO

6) 当所有的字符串都处理完毕。检查堆栈的长度。

6.a) 如果长度为 0 打印 YES

6.b) 否则打印 NO

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

Answer 4

在每种情况下，平衡情况下的内部项目应该是 ()、{} 或 []

Usage  
...........................
string text = "()[][][((()))]{}";
bool isBalanced = IsBalanced(text);
...........................

Method
...........................
bool IsBalanced(string s)
{
int textCount = 0;

do
{
s = s.Replace("[]", string.Empty).Replace("{}", string.Empty).Replace("()", string.Empty);
if (textCount==s.Length)
{
return false;
}
else
{
textCount = s.Length;
}

} while (s.Length>0);

return true;
}

Answer 5

我会这样使用队列和堆栈

        var dictionary = new Dictionary<string, string>() {
            { "{", "}" },
            {"[", "]" },
            {"(",")" }
        };


        var par = "{()}";
        var queue = new Queue();
        var stack = new Stack();

        bool isBalanced = true;

        var size = par.ToCharArray().Length;

        if(size % 2 != 0)
        {
            isBalanced = false;
        }
        else
        {
            foreach (var c in par.ToCharArray())
            {
                stack.Push(c.ToString());
                queue.Enqueue(c.ToString());
            }

            while (stack.Count > size/2 && queue.Count > size/2)
            {
                var a = (string)queue.Dequeue();
                var b = (string)stack.Pop();

                if (dictionary.ContainsKey(a) && b != dictionary[a])
                {
                    isBalanced = false;

                }


            }


        }

        Console.WriteLine(isBalanced?"balanced!":"Not Balanced");

        Console.ReadLine();

举个例子，第一次迭代 a = '{' and b ='}'

Answer 6

  public boolean isValid(String input) {

    Map<Character, Character> map = new HashMap<>();
        map.put('<', '>');
        map.put('{', '}');
        map.put('[', ']');
        map.put('(', ')');

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

     for(char ch : input.toCharArray()){
         if(map.containsKey(ch)){
             stack.push(ch);
         } else if(!stack.empty() && map.get(stack.peek())==ch){
             stack.pop();
         } else {
             return false;
         }
     }
     return stack.empty();
 }

Answer 7

可以这样做...

public static Boolean isBalanced(String input){

  return Regex.Replace(input, @"[^\[\]\{\}()]", "").Replace("[]", "").Replace("{}","").Replace("()","").Length > 0 ? false : true;

}

平衡牙套的程序

Program to balance the braces

c#

arrays

string

conditional

if-statement