C++는 표현식에서 유효하지 않은 대괄호를 제거합니다.

괄호 시퀀스가 ​​제공되면 이제 유효하지 않은 괄호를 제거하여 가능한 모든 괄호를 인쇄해야 합니다. 예를 들어

Input : str = “()())()” -
Output : ()()() (())()
There are two possible solutions
"()()()" and "(())()"

Input : str = (v)())()
Output : (v)()() (v())()

이 질문에서는 역추적 방법을 사용하여 모든 유효한 시퀀스를 인쇄합니다. .

해결 방법

이 방법에서는 BFS를 사용하여 여는 괄호와 닫는 괄호를 하나씩 제거해 보겠습니다. 이제 각 시퀀스에 대해 유효한지 확인합니다. 유효한 경우 출력으로 인쇄하십시오.

Example

 
#include <bits/stdc++.h>
using namespace std;
bool isParenthesis(char c){
    return ((c == &#39;(&#39;) || (c == &#39;)&#39;));
}
bool validString(string str){
    // cout << str << " ";
    int cnt = 0;
    for (int i = 0; i < str.length(); i++){
        if (str[i] == &#39;(&#39;)
           cnt++;
        else if (str[i] == &#39;)&#39;)
           cnt--;
        if (cnt < 0)
           return false;
    }
    // cout << str << " ";
    return (cnt == 0);
}
void validParenthesesSequences(string str){
    if (str.empty())
        return ;
    set<string> visit; // if we checked that sting so we put it inside visit
                      // so that we will not encounter that string again
    queue<string> q; // queue for performing bfs
    string temp;
    bool level;
    // pushing given string as starting node into queue
    q.push(str);
    visit.insert(str);
    while (!q.empty()){
        str = q.front(); q.pop();
        if (validString(str)){
        //    cout << "s";
            cout << str << "\n"; // we print our string
            level = true; // as we found the sting on the same level so we don&#39;t need to apply bfs from it
        }
        if (level)
            continue;
        for (int i = 0; i < str.length(); i++){
            if (!isParenthesis(str[i])) // we won&#39;t be removing any other characters than the brackets from our string
                continue;
            temp = str.substr(0, i) + str.substr(i + 1); // removing parentheses from the strings one by one
            if (visit.find(temp) == visit.end()) { // if we check that string so we won&#39;t check it again
                q.push(temp);
                visit.insert(temp);
            }
        }
    }
}
int main(){
    string s1;
    s1 = "(v)())()";
    cout << "Input : " << s1 << "\n";
    cout << "Output : ";
    validParenthesesSequences(s1);
    return 0;
}

Output

Input : (v)())()
Output : (v())()

위 코드 설명

위 방법에서는 괄호를 하나씩 제거하고, 동일한 시퀀스를 반복적으로 확인하지 않기 위해 이전 시퀀스도 추적합니다. 유효한 시퀀스를 찾으면 유효한 가능성을 모두 인쇄하며 이것이 프로그램이 실행되는 방식입니다.

결론

이 튜토리얼에서는 유효하지 않은 괄호를 찾아 제거하는 문제를 해결했습니다. 우리는 또한 이 문제를 해결하기 위한 C++ 프로그램과 완전한 솔루션(공통 방법)을 배웠습니다. C, Java, Python 등과 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.

위 내용은 C++는 표현식에서 유효하지 않은 대괄호를 제거합니다.의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!