首页 > 试题广场 >

完成括号匹配

[编程题]完成括号匹配

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

输入

][

输出

[][]

算法知识视频讲解

小谷围做题家

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)