Wie finden Sie das passende paar von geschweiften Klammern in einem string?

Den Stack ist eine gute Idee, aber wie Sie wollen, um zu sehen, wenn der komplette string ist umgeben mit parens, ich schlage vor, Sie setzen die index der angetroffenen öffnung Klammer auf der Stack. So, jedes mal, wenn Sie pop ein Element auf den stack, überprüfen Sie, ob es 0, die Bedeutung der Eröffnung Teil, entspricht diesem abschließenden Teil wurde auf den Anfang der Zeichenkette. Das Ergebnis dieser überprüfung für die Letzte schließende Klammer wird Ihnen sagen, wenn Sie brauchen, um hinzuzufügen, parens.

Beispiel:

String s = "((paid for) + (8 working hours) + (company rules))";
var stack = new Stack<int>();
bool isSurroundedByParens = false;
for (int i = 0; i < s.Length; i++) {
    switch (s[i]) {
    case '(':
        stack.Push(i);
        isSurroundedByParens = false;
        break;
    case ')':
        int index = stack.Any() ? stack.Pop() : -1;
        isSurroundedByParens = (index == 0);
        break;
    default:
        isSurroundedByParens = false;
        break;
    }
}
if (!isSurroundedByParens) {
    //surround with parens
}

InformationsquelleAutor Botz3000

Tests

static void Main()
{
    Console.WriteLine("Expected: {0}, Is: {1}", false, IsSurrounded(""));
    Console.WriteLine("Expected: {0}, Is: {1}", false, IsSurrounded("("));
    Console.WriteLine("Expected: {0}, Is: {1}", false, IsSurrounded(")"));
    Console.WriteLine("Expected: {0}, Is: {1}", true, IsSurrounded("()"));
    Console.WriteLine("Expected: {0}, Is: {1}", false, IsSurrounded("(()"));
    Console.WriteLine("Expected: {0}, Is: {1}", false, IsSurrounded("())"));
    Console.WriteLine("Expected: {0}, Is: {1}", true, IsSurrounded("(.(..)..(..)..)"));
    Console.WriteLine("Expected: {0}, Is: {1}", false, IsSurrounded("(..)..(..)"));
    Console.WriteLine("Expected: {0}, Is: {1}", false, IsSurrounded("(..)..(..)..)"));
    Console.WriteLine("Expected: {0}, Is: {1}", false, IsSurrounded("(.(..)..(..)"));
}

Methode

Sehr schnell

• Keine stack
• Keine Schleife durch die gesamte Zeichenfolge

Wenn die erste öffnende Klammer hat das schließende Gegenstück, dann kann das Ergebnis doch nicht wahr sein. Gleiche Sache über die Letzte schließende Klammer.

static bool IsSurrounded(string text)
{
    if (text.Length < 2 || text.First() != '(' || text.Last() != ')')
        return false;

    for (var i = 1; i < text.Length - 1; i++)
    {
        if (text[i] == ')')
            return false;

        if (text[i] == '(')
            break;
    }

    for (var i = text.Length - 2; i > 0; i--)
    {
        if (text[i] == '(')
            return false;

        if (text[i] == ')')
            break;
    }

    return true;
}

Einschränkungen

Sollte nicht verwendet werden, wenn es gibt mehrere rekursive Klammern wie ((..)) + ((..))

InformationsquelleAutor Ryszard Dżegan

Können Sie die richtige Anzahl von parenthesises, indem Sie so etwas wie ein stack. Zählen Sie für jede Eröffnung und count-down für jede schließende Klammer. Die gleiche Anzahl von öffnenden und schließenden geschweiften Klammern bedeutet, dass es passt. Wenn Sie stoßen immer eine schließende geschweifte Klammer, während Ihre Anzahl gleich null ist, das ist ein Missverhältnis. Wenn Sie wissen möchten, ob Ihr string ist komplett umschlossen von paranthesises, prüfen Sie, ob alle von Ihnen passen, dann überprüfen Sie, wenn die Zeichenfolge beginnt mit einem.

static void BraceMatch(string text)
{
  int level = 0;

  foreach (char c in text)
  {
    if (c == '(')
    {
      //opening brace detected
      level++;
    }

    if (c == ')')
    {
      level--;

      if (level < 0)
      {
        //closing brace detected, without a corresponding opening brace
        throw new ApplicationException("Opening brace missing.");
      }
    }
  }

  if (level > 0)
  {
    //more open than closing braces
    throw new ApplicationException("Closing brace missing.");
  }
}

InformationsquelleAutor nvoigt