C++ 打印所有通过替代通配符’?’可以得到的平衡括号字符串

平衡括号意味着如果我们有一串括号，则每个开括号都有一个对应的闭括号，并且括号对是正确嵌套的。字符串的大小应为偶数。在这个问题中，我们给出了一个包含字符’?’的括号字符串，我们的任务是通过将’?’替换为适当的括号来形成每个可能的平衡括号字符串。在给定的字符串中，只使用圆括号'(‘和’)’。

示例

Input 1: str = ‚Äú()(?)?‚Äù
Output 1: ()(())

解释

只能通过替换 ‚Äò?‚Äô 形成一个平衡的字符串。

Input 2: str = ‚Äú??????‚Äù

Output 2: ((()))
(()())
(())()
()(())
()()()

说明

有两种可能的方式来形成一个平衡的字符串。

一种方式是将索引0、1和2替换为开放括号，将其余索引替换为关闭括号。
第二种方式是将索引0、1和3替换为开放括号，将其余索引替换为关闭括号。
第三种方式是将索引0、1和4替换为开放括号，将其余索引替换为关闭括号。
第四种方式是将索引0、2和3替换为开放括号，将其余索引替换为关闭括号。
最后一种方式是将索引0、2和4替换为开放括号，将其余索引替换为关闭括号。

方法

我们已经展示了给定字符串的示例，接下来我们来看方法：

我们可以使用回溯法来解决这个问题。

让我们讨论一下下面的方法：

首先，我们将初始化一个函数’create’，用参数str和index = 0来创建替换’?’后的所有可能的字符串。
在函数中：-
- 首先，我们设置基本条件。如果我们达到字符串的末尾，则将该字符串传递给’check’函数来验证字符串是否平衡。如果平衡，则打印该字符串。
- 如果字符串的当前字符是’?’，
- 首先，将其替换为开放括号，并调用相同的函数来检查是否达到了字符串的末尾。
- 其次，将其替换为关闭括号，并再次调用相同的函数来检查是否达到了字符串的末尾。
- 最后，回溯字符串并将当前字符设置为’?’。
- 否则，字符串的当前字符是括号，然后通过调用相同的函数来移动到下一个索引。
初始化’check’函数来验证字符串是否平衡。
- 在这个函数中，我们初始化堆栈然后检查：
- 如果字符串的第一个字符是关闭括号，则返回false。
- 否则，如果当前括号是关闭的，则还有两种情况：如果堆栈为空，则返回false，因为没有对应的开放括号。否则，从堆栈中弹出对应的开放括号。
- 最后，我们检查如果堆栈为空则字符串平衡并返回true，否则还有一些括号没有配对，即字符串不平衡并返回false。

示例

以下是用回溯法获取所有平衡字符串的C++代码

#include <bits/stdc++.h>
using namespace std; 
// Function 'check' to verify whether the string is balanced or not
bool check(string str){
   stack<char> S; // created stack 

// If the first character of the string is a close bracket, then return false
   if (str[0] == ')') {
      return false;
   } 

   // Traverse the string using for loop 
   for (int i = 0; i < str.size(); i++) { 

      // If the current character is an open bracket, then push it into the stack
      if (str[i] == '(') { 
         S.push('(');
      } 

      // If the current character is a close bracket
      else { 

         // If the stack is empty, there is no corresponding open bracket return false
         if (S.empty()){
            return false;
         }

         // Else pop the corresponding opening bracket from the stack
         else
            S.pop();
      }
   } 

   // If the stack is empty, return true
   if (S.empty()){
      return true;
   }
   else {
      return false;
   }
} 

// Function 'create' to create all possible bracket strings
void create(string str, int i){ 

   // If reached the end of the string
   if (i == str.size()) { 

      // passed 'str' to the 'check' function to verify whether the string is balanced or not
      if (check(str)) { 

         // If it is a balanced string
         cout<< str << endl; // print the string
      }
      return; 
   } 

   // If the current character of the string is '?'
   if (str[i] == '?') { 
      str[i] = '('; // replace ? with (
      create(str, i + 1); // continue to next character 
      str[i] = ')'; // replace ? with )
      create(str, i + 1); // continue to next character 

      // backtrack
      str[i] = '?';
   }

   // If the current character is bracketed then move to the next index
   else {
      create(str, i + 1);
   }
} 
int main(){
   string str = "??????"; //given string 

   // Call the function
   create (str, 0);
   return 0;
}