与えられた文字列が悪いかどうかをチェックするC++プログラム

n文字の文字列Sがあるとします。 Sには、小文字の英字と'）'文字が含まれます。最後の文字数'）'が残りの文字数よりも厳密に多い場合、文字列は正しくありません。 Sが悪いかどうかを確認する必要があります。

したがって、入力がS ="fega））））））"のような場合、4文字と6'）があるのでこれは悪いので、出力はTrueになります。

ステップ

これを解決するには、次の手順に従います-

ans := 0
n := size of S
i := n - 1
while (i >= 0 and S[i] is same as ')'), do:
   (decrease i by 1)
z := n - 1 - i
ans := 2 * z - n
if ans > 0, then:
   return true
Otherwise
   return false

例

理解を深めるために、次の実装を見てみましょう-

#include <bits/stdc++.h>
using namespace std;

bool solve(string S) {
   int ans = 0;
   int n = S.size();
   int i = n - 1;
   while (i >= 0 && S[i] == ')')
      i--;
   int z = n - 1 - i;
   ans = 2 * z - n;
   if (ans > 0)
      return true;
   else
      return false;
}
int main() {
   string S = "fega))))))";
   cout << solve(S) << endl;
}

入力

"fega))))))"

出力

1