首页 > 试题广场 >

完成括号匹配

[编程题]完成括号匹配

热度指数：3761 时间限制：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

输入

][

输出

[][]

算法知识视频讲解

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)

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)

Java

X_X_aud

用栈来判断括号是否匹配

public class Main {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.nextLine();
        char[] c = s.toCharArray();
        Stack<Character> st = new Stack<Character>();
        int cnt = 0;
        for (int i = 0; i < c.length; i++) {
            if (c[i] == '[')
                st.push(c[i]);
            if (c[i] == ']') {
                if (st.isEmpty())
                    cnt++;
                else
                    st.pop();
            }
        }
        int rt_res = st.size();
        while (cnt-- > 0)
            s = '[' + s;
        while (rt_res-- > 0)
            s = s + ']';
        System.out.print(s);
    }
}

发表于 2018-07-12 20:09:17 回复(0)