首页 > 试题广场 >

完成括号匹配

[编程题]完成括号匹配

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

合法的括号匹配序列被定义为:
1. 空串""是合法的括号序列
2. 如果"X"和"Y"是合法的序列,那么"XY"也是一个合法的括号序列
3. 如果"X"是一个合法的序列,那么"[X]"也是一个合法的括号序列
4. 每个合法的括号序列都可以由上面的规则生成
例如"", "[]", "[][][]", "[[][]]", "[[[[]]]]"都是合法的。
牛牛现在给出一个括号序列s,牛牛允许你执行的操作是:在s的开始和结尾处添加一定数量的左括号('[')或者右括号(']')使其变为一个合法的括号匹配序列。牛牛希望你能求出添加最少的括号之后的合法的括号匹配序列是什么。

输入描述:

输入包括一个字符串s,s的长度length(1 ≤ length ≤ 50),s中只包含'['和']'。

输出描述:

输出一个字符串,表示括号完全匹配的序列。

示例1

输入

][

输出

[][]

算法知识视频讲解

33445

发表于 2018-08-15 10:45:44 回复(1)

空山新雨后c

"""
@author : liang
"""
def solution(s):
    if s=="":
        return ""
    count=0
    t=""
    for i in s:
        if i=="[":
            count+=1
        else:
            count-=1
        if count<0:
            t="["+t
            count=0
    while count>=1:
        s+="]"
        count-=1
    return t+s
s=raw_input().strip()
print solution(s)

发表于 2018-07-18 16:41:08 回复(0)

Java

tornado123

// 参考题解，从左到右寻找"]",然后找到最近的匹配符（如果找不到，直接在第一个的位置插入"["），
// 然后将两者用花括号代替，最后再将花括号替换成相应的 [、]
import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        StringBuilder sb = new StringBuilder(sc.nextLine());
        while(sb.indexOf("]") != -1) {
            int j = sb.indexOf("]");
            sb.setCharAt(j, '}');
            int i = j - 1;
            while(i >= 0 && sb.charAt(i) != '[') {
                i--;
            }
            if(i < 0) {
                sb.insert(0, '{');
            }else {
                sb.setCharAt(i, '{');
            }
        }
        // 有可能输入：[[
        int num = 0;
        // 替换输出
        for(int i = 0; i < sb.length(); i++) {
            if(sb.charAt(i) == '{') {
                sb.setCharAt(i, '[');
            }else if(sb.charAt(i) == '}') {
                sb.setCharAt(i, ']');
            }else {
                // 这里就是 [[ ，前面没有匹配到的左括号
                num ++;
            }
        }
        while(num-- > 0) {
            sb.append(']');
        }
        System.out.print(sb.toString());
    }
}

发表于 2021-03-17 17:38:54 回复(0)

Benjaminpcm

class Solution:
    def isVaild(self, s):

        stack = []
        stack.append(s[0])
        for i in range(1, len(s)):
            if len(stack) > 0:
                if s[i] == ']' and '[' == stack[-1]:
                    stack.pop()
                else:
                    stack.append(s[i])
            else:
                stack.append(s[i])
        s = list(s)
        for i in stack:
            if i == ']':
                s.insert(0, '[')
            else:
                s.append(']')
        return ''.join(s)
so = Solution()
s = input()
res = so.isVaild(s)
print(res)

发表于 2019-04-02 11:00:40 回复(0)

日向家宁次少爷

#include<iostream>
#include<string>
#include<stack>
using namespace std;
void Func2(string &str)
{
    size_t len =str.length();
    stack<char> s;
    for(int i =0;i<len;i++)
    {
        if(str[i]=='[')
            s.push(str[i]);
        else
        {
            if(!s.empty()&&s.top()=='[')
                s.pop();
            else
                s.push(']');
        }
    }
    while(!s.empty())
    {
        if(s.top()=='[')
            str.append("]");
        else
            str.insert(0,"[");
        s.pop();
        
    }
    return;
}
int main()
{
    string str;
    cin>>str;
    Func2(str);
    cout<<str<<endl;
    return 0;
}

发表于 2019-03-18 21:04:17 回复(0)

为啥要起名字

while True:
    try:
        s=raw_input()
        res,count=0,0
        if len(s)==0:
            print('')
        for i in s:
            if i=='[':
                count+=1
            else:
                if count==0:
                    res+=1
                else:
                    count-=1
        while count>0:
            s+=']'
            count-=1
        while res>0:
            s='['+s
            res-=1
        print(s)
    except:
        break


先计算出不能匹配的'['和']'的个数，然后分别在左右两边进行添加

发表于 2018-08-03 10:51:00 回复(0)

wylu

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

/**
 * @author wylu
 */
public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        char[] str = br.readLine().toCharArray();

        int count = 0;
        StringBuilder sb = new StringBuilder();
        for (char ch : str) {
            if (ch == '[') count++;
            else {
                if (count == 0) sb.insert(0, '[');
                else count--;
            }
            sb.append(ch);
        }
        for (int i = 0; i < count; i++) sb.append(']');
        System.out.println(sb);
    }
}

发表于 2019-01-17 23:12:24 回复(2)

milumilum

python 代码

从左边开始遍历，如果遇到【，就记录个数，如果遇到】，与左括号匹配，如果左括号存在，就消掉一个，如果没有，结果resleft必须加一个左括号（因为之后再出现的左括号无法与之匹配）。遍历完成后，没有消掉的左括号必须加上与之相等的右括号才能消掉。
不能直接统计个数，因为与左右括号出现的顺序有关。只有右括号出现在左括号的右侧，才能凑成一对。

import sys
for line in sys.stdin:
    line = line.strip()
    left = 0  # 记录已经出现的左括号
    resleft = 0   # 记录结果需要加几个左括号
    n = len(line)
    if n <= 0:
        print("")
    else:
        for i in line:
            if i == ']' and left == 0:
                resleft += 1
            elif i == ']':
                left -= 1
            else:
                left += 1
        strresl = ''
        strresr = ''
        strresl += '[' * resleft
        strresr += ']' * left
        print(strresl + line + strresr)

编辑于 2021-03-29 11:33:08 回复(0)

Java

雨果伽利略

import java.util.Scanner;

/**

@author wylu

/
public class Main {
public static void main(String[] args) {

  // ①如果缺乏左括号，直接添加对应的左括号；
  // ②在结束后，加入缺少的右括号；
  String str = new Scanner(System.in).nextLine();
  // 存储缺少的'['
  StringBuffer left = new StringBuffer();
  // 存储缺少的']'
  StringBuffer right = new StringBuffer();
  int count = 0;
  for (int i = 0; i < str.length(); i++) {
      if (str.charAt(i) == '[') {
          count++;
      } else {
          count--;
      }
      if (count < 0) {
          count++;
          left.append('[');
      }
  }
  for (int i = 0; i < count; i++) {
      right.append(']');
  }
  // 最终的结果连接
  //如：]]][[[[[
  //left：[[[
  //str:]]][[[[[
  //rigth:]]]]]
  //如：]][[]][[]]
  //将左括号放到left中+str+末尾需要的右括号的个数
  System.out.println(left.toString() + str + right.toString());

}
}

发表于 2019-03-02 09:50:09 回复(0)

C++

青春Java少年不会梦到C艹学姐

#include <bits/stdc++.h>
using namespace std;
string s;
int l, r;
vector<char> v;

int main() {
    cin >> s;
    for (auto c : s) {
        if (!v.empty() && v.back() == '[' && c == ']') {
            v.pop_back();
        } else {
            v.push_back(c);
        }
    }
    for (auto c : v) {
        if (c == '[') l++;
        else r++;
    }
    while (r--) cout << '[';
    cout << s;
    while (l--) cout << ']';
}

发表于 2025-03-25 15:13:44 回复(0)

C++

牛客187183257号

#include <iostream>
#include<stack>
using namespace std;
int lc = 0, rc = 0;//补充的符号数
char list[50] = {0};
bool ismatch(char a, char b) {
    if (a == '[' && b == ']' ) return true;
    else return false;
}
void match(char a) {
    if (a == '[') rc++;
    else if (a == ']') lc++;
}

int main() {
    stack<char> s;
    int i = 0;//字符串大小
    while (true) {
        char key = getchar();
        if (key == '\n') break;
        list[i++] = key;
        if (s.empty()) s.push(key);
        else if (ismatch(s.top(), key)) s.pop();  
        else s.push(key);
    }
    while (!s.empty()) {
        char tmp  = s.top();
        s.pop();
        match(tmp);
    }
    for (int j = 0; j < lc + rc + i; j++) {
        if (j < lc) cout << '[';
        else if (j < i + lc) cout << list[j - lc];
        else cout << ']';
    }
}

发表于 2025-03-14 11:48:53 回复(0)

Python2

慰藉

import sys

try:
    while True:
        line = sys.stdin.readline().strip()
        if line == '':
            break
        # lines = line.split()
        # print(int(lines[0]) + int(lines[1]))
        need_right = 0
        need_left = 0
        for char in line:
            if char == "[":
                need_right += 1
            elif char == "]":
                if need_right > 0:
                    need_right -= 1
                else:
                    need_left += 1
        print((need_left * "[") + line + ("]" * need_right))

        
except:
    pass

发表于 2025-03-05 18:09:21 回复(0)

牛客648054015号

import sys

result=input()
flag=0#flag记未匹配的左括号数
for i in result:
    if i=="]" and flag==0:#最前面的右括号未被匹配就在最前面加
        result="["+result
    if i=="[" :#有左括号就技术
        flag+=1
    if i=="]" and flag>0:#对应右括号就匹配
        flag-=1

if flag>0:#没匹配完的最后补充加
    result=result+("]"*flag)
print(result)

发表于 2025-02-12 19:08:39 回复(0)

牛客71116271号

答案不唯一啊，如：

[]]]

[[[]]]、[][][]、[[]][]

标准答案取的第一种

发表于 2024-09-09 18:18:21 回复(0)

宋姝逸

#include <stdio.h>

#include <string.h>

void m(char *s, char *result);

int main() {

char s[51];

char result[102];

if (scanf("%50s", s) != 1) {

printf("Input error\n");

return 1;

}

m(s, result);

printf("%s\n", result);

return 0;

}

void m(char *s, char *result) {

int left = 0;

int right = 0;

int balance = 0;

int i = 0;

int j = 0;

for (i = 0; s[i] != '\0'; i++) {

if (s[i] == '[') {

balance++;

} else {

balance--;

}

if (balance < 0) {

left++;

balance = 0;

}

right = balance;

int p = 0;

while (left--) {

result[p++] = '[';

}

int len = strlen(s);

strcpy(result + p, s);

while (right--) {

result[len + (p++)] = ']';

}

result[len+p] = '\0';

}

发表于 2024-08-17 01:09:53 回复(0)

JavaScript Node

郭郭不吃糖

 console.log(c(line));
        function c(str) {
            let str1 = str;
            while (/\[\]/.test(str1)) {
                str1 = str1.replace(/\[\]/g, "");
            }
            let arr = str1.split("");
            let obj = arr.reduce((acc, curr) => {
                if (acc[curr]) {
                    acc[curr]++;
                } else {
                    acc[curr] = 1;
                }
                return acc;
            }, {});
            if (obj["]"]) {
                let brr = new Array(obj["]"]).fill("[").join("");
                str = brr + str;
            }
            if (obj["["]) {
                let brr = new Array(obj["["]).fill("]").join("");
                str += brr;
            }
            return str;
        }

发表于 2023-11-18 21:17:22 回复(0)

小谷围做题家

package main

import (
    "fmt"
    "strings"
)

func main() {
    var s string
    fmt.Scan(&s)
    stk:=[]byte{}
    var l,r int
    for _,ch:=range []byte(s){
        if len(stk)>0&&stk[len(stk)-1]=='['&&ch==']'{
            l--
            stk=stk[:len(stk)-1]
        }else{
            if ch=='['{
                l++
            }else{
                r++
            }
            stk=append(stk,ch)
        }
    }
    s=strings.Repeat("[",r)+s+strings.Repeat("]",l)
    fmt.Print(s)
}

发表于 2023-03-21 09:37:37 回复(0)

C/C++

codewind

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

int main(void) {
    string s;
    cin>>s;
    string res;
    int cnt=0;
    string res_front;
    for(char f: s) {
        if(f=='[') cnt++;
        else {
            cnt--;
            
        }
        if(cnt < 0) res_front +="[" ,cnt++ ;
        res.push_back(f);   
    }
   // cout <<cnt<<endl;
    while(cnt--) res.push_back(']');
    //while(cnt--) res.push_back(']');
   // for(int i=0;i<cnt;++i) res+= ']';
    cout << res_front+ res <<endl;
    
    
    
    
    
    
    
    return 0;
}

发表于 2021-04-10 11:32:36 回复(0)

Python

白色纯度

有一个取巧的方法，先将原字符串中所有的‘[]’替换为空，留下来的就是无法匹配的。在依次在左边或者右边添加相应的符号即可。

if __name__=='__main__':
    string = input().strip()
    s= string
    length = len(s)
    temp = float('inf')
    while length!=temp:
        length = temp
        s = s.replace('[]','')
        temp = len(s)
    left = []
    right = []
    for i in s:
        if i==']':
            left.append('[')
        else:
            right.append(']')
    ans1 = ''.join(left[::-1])
    ans2 = ''.join(right[::-1])
    res = ans1 + string+ans2
    print(res)

发表于 2019-09-15 15:51:43 回复(0)

sakuuura

s = readline();
var res = [];
var tem = [];
var count = 0;
for(var i = 0;i<s.length;i++){
    if(s[i] == '['){
        count++;
    }
    else{
        count--;
    }
    if(count<0){
        count++;
        res.push('[');
    }
}
for(var i=0;i<count;i++){
    tem.push(']');
}
print(res.join('')+s+tem.join(''));

发表于 2019-09-01 11:23:31 回复(0)