c# - 文字列内で一致する中かっこのペアを見つける方法は?

Question

文字列 "(支払った) + (8 労働時間) + (社内規則)" があるとします。ここで、この完全な文字列が括弧で囲まれているかどうかを確認したいと思います。基本的に、文字列が次のようになっているかどうかを確認したい：「（（有給）+（8労働時間）+（会社規則））」。すでに括弧で囲まれている場合はそのままにします。それ以外の場合は、出力が次のようになるように、文字列全体に括弧を適用します。 " . 括弧の数を数えても、この問題は解けません。

誰でも解決策を提案できますか?

Answer 1

はStack良い考えですが、完全な文字列が括弧で囲まれているかどうかを確認したいので、遭遇した開始括弧のインデックスStackを に置くことをお勧めします。そうすれば、アイテムをスタックにポップするたびに、それが であるかどうかを確認し0ます。これは、この閉じ括弧に対応する開き括弧が文字列の先頭にあったことを意味します。最後の閉じ括弧に対するこのチェックの結果は、括弧を追加する必要があるかどうかを示します。

例：

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
}

Answer 2

スタックを使用します..（ブラケットを押して、見ると）スタックをポップします..最後に、文字列が完全に解析されると、スタックは空になります...これにより、ブラケットが欠落していないことが保証されます..

あなたの場合、スタックが空になると、文字列全体を囲む括弧はありません

例: 入力文字列の場合:

(有給) + (実働8時間) + (社内規定)

最初の (プッシュされ、 ) に遭遇するとスタックがポップされます。解析する文字列が他にもあり、スタックが空でないかどうかを確認します。スタックが空の場合、文字列全体が括弧で囲まれていないことを意味します。

一方、文字列の場合:

((有給) + (8 労働時間) + (会社規定))

最後の ) が表示されるまで、スタックは空になりません。

お役に立てれば...

Answer 3

テスト

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("(.(..)..(..)"));
}

---

方法

とても早い

• スタックなし
• 文字列全体をループしません

最初の開き括弧に対応する閉じ括弧がある場合、結果は真にはなりません。最後の閉じ括弧についても同じです。

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;
}

---

制限事項

次のような再帰的な括弧がある場合は使用しないでください。((..)) + ((..))

Answer 4

かっこがあることを確認するには、単純に追加できます。

text = "(" + text + ")"

それ以外の場合は、Botz3000 によって提案されたスタック:

string text = "(paid for)";

Stack<int> parenthesis = new Stack<int>();
int last = 0;

for (int i = 0; i < text.Length; i++)
{
    if (text[i] == '(')
        parenthesis.Push(i);
    else if (text[i] == ')')
    {
        last = parenthesis.Pop();
    }
}

if (last == 0)
{
    // The matching parenthesis was the first letter.
}

Answer 5

スタックのようなものを使用して、正しい括弧の数を確認できます。開き括弧ごとにカウントアップし、閉じ括弧ごとにカウントダウンします。左中括弧と右中括弧の数が同じであれば、一致することを意味します。カウントが 0 のときに右中括弧に遭遇したことがある場合、それは不一致です。文字列が括弧で完全に囲まれているかどうかを知りたい場合は、それらがすべて一致するかどうかを確認してから、文字列が括弧で始まるかどうかを確認します。

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.");
  }
}