我要招人

去企业版

首页 > 试题广场 >

迷失的括号序列

[编程题]迷失的括号序列

热度指数：1429 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛妹有括号序列brackets，因为过了太久，导致里面有些括号看不清了，所以用 $?$ 代替，她想知道这个括号序列能不能恢复成合法的括号序列。具体操作是将 $?$ 改为'('或者')'。brackets只由'?','(',')'构成。

合法的括号序列的定义：

1.空字符为合法括号序列
2.(+合法括号序列+) 为合法括号序列
3.()+合法括号序列为合法括号序列

如果能构造出来则返回恢复后任意合法的括号序列，否则返回Impossible

示例1

输入

"()?)"

输出

"()()"

说明

把?替换为(即可

备注:

给定brackets字符串

算法知识视频讲解

LEIHongfaan

照答案逻辑

(()?()

变为

(())()

我就想知道，设 Γ 为合法括号序列（字符串）组成的集合，x 为任一合法括号序列（字符串），按

"" ∈ Γ
x ∈ Γ ⇒ "(" + x + ")" ∈ Γ
x ∈ Γ ⇒ "()" + x ∈ Γ

这三条规则，怎么得出

"(())()" ∈ Γ

？？？

附原文：

合法的括号序列的定义：
1.空字符为合法括号序列
2.(+合法括号序列+) 为合法括号序列
3.()+合法括号序列为合法括号序列

发表于 2020-03-15 01:32:03 回复(1)

嗯学

找了一天bug才发现是因为把"Impossible"打成"impossible"，改了之后就通过了。。。我真是个five。😣

发表于 2020-03-13 16:49:07 回复(0)

C/C++

李小嘻

class Solution {
public:
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param brackets string字符串 brackets
* @return string字符串
*/
string MissingBrackets(string brackets) {
// write code here
if(brackets.size()%2!=0) return "Impossible";
int leftlen=0,rightlen=0,unknown=0;
for(int i=0;i<brackets.size();i++)
{
switch(brackets[i])
{
case '(':leftlen++;break;
case ')':rightlen++;break;
}
}
if(leftlen>brackets.size()/2||rightlen>brackets.size()/2) return "Impossible";
int left_new=brackets.size()/2-leftlen;
int right_new=brackets.size()/2-rightlen;
int left=0,right=0;
for(int i=0;i<brackets.size();i++)
{
if(left<right) return "Impossible";
if(brackets[i]=='(') left++;
if(brackets[i]==')') right++;
if(brackets[i]=='?')
{
if(left_new>0)
{
brackets[i]='(';
left_new--;left++;
}else{
brackets[i]=')';
right_new--;right++;
}
}
}
return brackets;
}
};

发表于 2021-05-21 15:41:02 回复(0)

萨巴鲁酱

class Solution {
public:
    /**
     * 
     * @param brackets string字符串 brackets
     * @return string字符串
     */
    string MissingBrackets(string brackets) {
        // write code here
        if(brackets.size() & 1)
            return "Impossible";
        
        int nLeftBracket = 0;
        for(char c : brackets){
            if(c == '(')
                nLeftBracket++;
        }
        
        if(nLeftBracket > (brackets.size() >> 1))
            return "Impossible";
        
        for(int i = 0; i < brackets.size(); ++i){
            if(brackets[i] == '?'){
                if(nLeftBracket < brackets.size() / 2){
                    brackets[i] = '(';
                    nLeftBracket++;
                }
                else
                    brackets[i] = ')';
            }
        }
        
        stack<char> s;
        bool flag = true;
        for(char c : brackets){
            if(c == '(')
                s.push(c);
            else if(s.empty()){
                flag = false;
                break;
            }
            else
                s.pop();
        }
        
        return (flag == true)? brackets : "Impossible";
    }
};

发表于 2020-05-19 13:38:25 回复(0)

JaniceWu

class Solution:
    def MissingBrackets(self , brackets):
        if brackets is None:
            return brackets
        brackets = list(brackets)
        if len(brackets)%2==1:
            return "Impossible"
        countLeft = 0
        for i in range(len(brackets)):
            if brackets[i] == '(':
                countLeft+=1
        if countLeft > len(brackets)/2:
            return "Impossible"
        insertLeft = len(brackets)/2-countLeft
        for i in range(len(brackets)):
            if brackets[i] == '?' and insertLeft:
                brackets[i] = '('
                insertLeft-=1
            elif brackets[i] == '?':
                brackets[i] = ')'
        count = 0
        for s in range(len(brackets)):
            if brackets[s] == '(':
                count+=1
            else:
                count-=1
            if count<0:
                return "Impossible"
        return ''.join(brackets)

python中的str不允许直接修改其值，所以要转换为list，最后的返回结果也要用''.join()

发表于 2020-03-24 20:07:14 回复(0)

Neflibata

根据别人的思路，复现的程序

class Solution {
public:
    /**
     * 
     * @param brackets string字符串 brackets
     * @return string字符串
     */
    string MissingBrackets(string b) {
        // write code here
        int lcnt=0, len=b.size();
        for(auto c:b) lcnt+=(c=='(');
        if(len%2 || lcnt>len/2) return "Impossible";
        lcnt=len/2-lcnt;
        for(auto& c:b){
            if(c=='?'){
                if(lcnt) {c='(';lcnt--;}
                else c=')';
            }
        }
        lcnt=0;
        for(auto c:b){
            if(c=='(') lcnt++;
            else{
                lcnt--;
                if(lcnt<0) return "Impossible";
            }
        }
        return b;
    }
};

发表于 2020-03-11 17:36:05 回复(0)