基于栈的平衡括号题

Question

问题如下：如果可以通过在该序列中插入字符 + 和 1 来获得正确的算术表达式，则括号序列称为正则序列。例如，序列 (())()、() 和 (()(())) 是正则的，而 )(、(() 和 (()))( 则不是。我们称正则括号序列为“RBS ".

给你一个包含 n 个字符的序列 s (, ), and/or ?。此序列中正好有一个字符（且恰好有一个字符）。

你必须替换每个字符？使用 ) 或 (（不同的字符 ? 可以用不同的括号替换）。您不能重新排列字符、删除它们、插入其他字符，并且每个 ? 都必须替换。

判断这些替换后是否有可能获得平衡序列

前：

5
()
(?)
(??)
??()
)?(?

输出：

YES
NO
YES
YES
NO

这是我的代码：

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

bool checkValidString(string s) {
    stack<char>st;
    for(int i=0;i<s.length();i++)
    {
        if(!st.empty() && (((st.top() == '(') && s[i] == '?') || ((st.top() == '?') && s[i] == ')') || st.top() == '(' && s[i] == ')'))
        {
            st.pop();
        }
        else
        {
            st.push(s[i]);
        }
    }
    if(st.empty())
    {
      return true;
    }
    int si = st.size();
    bool odd = false;
    if(si%2!=0)
    {
      odd = true;
    }
    while(!st.empty())
    {
        char c = st.top();
        if(c!='?')
        {
            return false;
        }
        st.pop();
    }
    if(odd)
    {
        return false;
    }
    return true;
}

int main() {
    // your code goes here
    int n;
    cin>>n;
    while(n--)
    {
        string s;
        cin>>s;
        bool ans = checkValidString(s);
        if(ans == 1)
        {
            cout<<"YES"<<endl;
        }
        else
        {
            cout<<"NO"<<endl;
        }
    }
    return 0;
}

但是它给出了错误的答案，你能帮助我哪里出错了吗？谢谢。

Answer 1

这种问题不会通过检查有效括号的逻辑解决。

示例： 输入字符串 = (?)? 的测试用例将在您的案例中失败。但它是一个有效的字符串，因为它可以采用 (()).

的形式

那么现在，您如何解决这样的问题？

让我们弄清楚所有可能的输入字符串是什么样的。

测试用例：

如果问号为奇数，则为无效字符串。
如果左括号出现在右括号之前，并且它们之间有奇数个问号：

(???)? 或 ?(???) => 两者都是有效的字符串，因为它们可以采用 ((())).

的形式

如果左括号出现在右括号之前，并且它们之间有偶数个问号：

(????) 或 ??(??)?? => 这些字符串总是有效的。

如果左括号出现在右括号中：

?)(? => 这个字符串也是有效的，因为它可以取自 ()().

我们唯一需要担心的是)是第一个位置还是(是最后一个位置：

)??( => 始终是无效字符串。

)?(? => 始终是无效字符串。

?)?( => 始终是无效字符串。

因此，问题简化为 3 个主要条件：

字符串的长度应该是偶数：要做到这一点，字符串中 ? 个字符的数量应该是偶数。
字符串不应以 ) 开头。
字符串不应以(结尾。

查看以下在 Codeforces 上具有 Accepted 状态的代码：

#include <iostream>
#include <string>

int main(){
    
    int t;
    scanf("%d", &t);
    
    while(t--){
        
        std::string s;
        std::cin>>s;
        
        int len = s.length();
        int countQuestion = 0;
        
        for(int i=0;i<len;i++){
            
            if(s[i]=='?'){
                countQuestion++;
            }
        }    
        
        //Check 1: If question count is even?
        if(countQuestion & 1){
            
            printf("NO\n");
        }else{
            
            if(s[0] == ')' || s[len-1] == '('){
                printf("NO\n");
            }else{
                printf("YES\n");
            }
        }
    }
    
    return 0;
}

结论：

Answer 2

如果您想检查一串括号以查看它是否有效，您可以在遍历该字符串时保留一个开括号计数器。您将从 0 开始，每 ( 递增一次，每 ) 递减一次。您需要检查以确保它永远不会变为负数并且以 0 结尾。

如果把一些括号换成问号，你可以想象做同样的事情，但是在每个位置你都可以计算出计数器所有可能的非负值。如果该组值变为空，则不可能有有效的括号字符串。如果该集合不包含 0，则不可能有有效的括号字符串。

事实证明（你可以通过归纳法证明），可能值的集合总是包含两个数字 x 和 y 之间的每个 2nd 个数字。

在 ? 之后，[x,y] -> [x-1,y+1]，不包括 < 0 的数字

在 (, [x,y] -> [x+1,y+1]

之后

After ), [x,y] -> [x-1,y-1], 排除数字 < 0

所以可以通过字符串运行测试任意括号和问号序列，从[0,0]开始，根据以上每个字符的规则。确保它永远不会为空并在末尾包含 0。

bool checkValidString(string s) {
    int l=0, h=0;
    for(int i=0;i<s.length();i++) {
        switch(s[i]) {
            case '(':
            ++l;++h;
            break;

            case ')':
            if (h<=0) {
                return false;
            }
            --h;
            l += (l>0 ? -1:1);
            break;

            default:
            ++h;
            l += (l>0 ? -1:1);
            break;
        }
    }
    return l==0;
}

基于栈的平衡括号题

Balanced paranthesis question based on stack

c++

string

algorithm

stack

data-structures