首页 > 试题广场 >

完成括号匹配

[编程题]完成括号匹配
  • 热度指数:3748 时间限制: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

输入

][

输出

[][]
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 回复(1)
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)
var s = readline();
var news = [], count = 0,needr = 0, needl = 0;
    for (var i in s){
        if(s[i]=="]"){
            var index = news.indexOf("[") // 数组中是否有可以匹配的右括号
            if(index>=0){
                news.splice(index,1); // 有,删除数组中的右括号
                needl--; //最后所需的用来匹配右括号的左括号也因此减1
            }
            else{
                news.push(s[i]);// 没有,将改左括号插入数组
                needr++;//最后所需的用来匹配该左括号的右括号也因此加1
            }
        }
        else if(s[i]=="["){
            news.push(s[i]); //如果是右括号,插入
            needl++;    //所需要的左括号加1
        }
}
var l = "";
for (var k =0; k<needl;k++){
 l +="]"  //共需要几个左括号
}
var r = "";
for (var k =0; k<needr;k++){
 r +="["  //共需要几个右括号
}
 print(r+s+l);
发表于 2018-08-15 10:45:44 回复(1)
"""
@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)
// 参考题解,从左到右寻找"]",然后找到最近的匹配符(如果找不到,直接在第一个的位置插入"["),
// 然后将两者用花括号代替,最后再将花括号替换成相应的 [、]
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)
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)

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

分别用 lb 和 rb 记录左右括号。每遇到一个左括号 lb++,没遇到一个右括号就消除一个左括号或者rb++。最后这两个就分别代表了多出来的左括号和右括号。

#include <iostream>
#include <string>
using namespace std;

int main()
{
    string str;
    while (getline(cin, str))
    {
        int lb = 0, rb = 0;
        for (char ch : str)
        {
            if (ch == '[')
                lb++;
            else if (ch == ']')
            {
                if (lb > 0)
                    --lb;
                else
                    ++rb;
            }
        }
        for (int i = 0; i < rb; ++i)
            cout << '[';
        cout << str;
        for (int i = 0; i < lb; ++i)
            cout << ']';
        cout << endl;
    }
}
发表于 2019-06-18 15:11:18 回复(0)
import copy

if __name__ == '__main__':
    data = input()
    D = copy.copy(data)
    stack_l = []
    for i in data:
        if i == '[':
            stack_l.append(i)
        else:
            if len(stack_l) == 0:
                D = '[' + D
            else:
                stack_l.pop()
    D += ']'*len(stack_l)
    print(D)
发表于 2019-06-08 16:36:25 回复(0)
发表于 2019-05-26 11:54:39 回复(0)
1、正序寻找']',求需要添加'['的个数;
2、倒序寻找'[',求需要添加']'的个数。
#include<iostream>
#include<string>
using namespace std;
int main()
{
    string str;      cin>>str;    int k1=0,x=0,y=0,k2=0;    int len=str.length();
    for(int i=0;i<len;i++)    {        if(str[i]==']')            x++;        else             y++;        if(x-y>k1)            k1++;    }
    x=0;y=0;
    for(int i=len-1;i>=0;i--)    {        if(str[i]=='[')            x++;        else             y++;        if(x-y>k2)            k2++;    }
    for(int i=0;i<k1;i++)        cout<<"[";    cout<<str;    for(int i=0;i<k2;i++)        cout<<"]";
    cout<<endl;
}

发表于 2019-04-26 16:58:54 回复(0)
import java.util.Scanner;
import java.util.Stack;

public class Main{
    public static void main(String[] args){
        Scanner scanner = new Scanner(System.in);
        String str = scanner.next();
        
        Stack<Character> stack = new Stack();
        for(int i = 0; i < str.length(); i++){
            if(stack.isEmpty()){
                stack.push(str.charAt(i));
            }else{
                if(str.charAt(i) == ']'){
                    if(stack.peek() == '['){
                        stack.pop();
                    }else{
                        stack.push(']');
                    }
                }else{
                    stack.push('[');
                }
            }
        }
        while(!stack.isEmpty()){
            if(stack.peek() == ']'){
                str = "[" + str;
            }
            if(stack.peek() == '['){
                str = str + "]";
            }
            stack.pop();
        }
        System.out.println(str);
    }
}
发表于 2019-03-08 17:24:27 回复(0)
#include<cstdio>
int main(){
    char a[200];
    int n=50;
    char ch;
    scanf("%c",&ch);
    while(ch!='\0'&&ch!='\n'){
        a[n]=ch;
        scanf("%c",&ch);
        n++;
    }
    int right=0;
    int laddr=0;
    int raddl=0;
    for(int i=50;i<n;i++){
        if(a[i]==']'&&right==0)
        {
            laddr++;
        }
        if(a[i]==']'&&right>0){
            right--;
        }
        if(a[i]=='['&&a[i+1]=='['){
            right++;
        }
        if(a[i]=='['&&a[i+1]==']'){
            i++;
        }
        if(a[i]=='['&&i+1>=n){
            raddl++;
        }   
    }
    for(int i=laddr;i>0;i--){
        a[50-i]='[';
    }
    int k=right+raddl;
    int j=k;
 
    for(;k>0;k--){
        a[n+k-1]=']';
    }

    for(int i=50-laddr;i<n+j;i++){
        printf("%c",a[i]);
    }
    return 0;
}
发表于 2019-03-01 22:14:34 回复(0)