列表

详情


BD8. 完成括号匹配

描述

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

输入描述

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

输出描述

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

示例1

输入:

][

输出:

[][]

原站题解

C 解法, 执行用时: 1ms, 内存消耗: 376KB, 提交时间: 2021-04-24

#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>

int main(){
    

    char str[51] = {0};
    scanf("%s",str);
    int n = 0;
    int count = 0;
    for(int i=0;'\0'!=str[i];++i){
        if('[' == str[i]){
	    // Push(s,'[');
	    ++n;
	} else if(']' == str[i]){
	    if(/*GetSize(s)*/ n == 0){
	        ++count;
	    }else{
	        // Pop(s);
		--n;
	    }
	}
    }
    for(int i=0;i<count;++i){
        printf("[");
    }

    printf("%s",str);

    // int n = GetSize(s);
    for(int i=0;i<n;++i){
        printf("]");
    }
    printf("\n");

}

C 解法, 执行用时: 2ms, 内存消耗: 324KB, 提交时间: 2019-02-17

#include<stdio.h>
int main()
{
    char s[51];
    scanf("%s",s);
    int i=0,left=0,right=0;
    while(s[i] != '\0')
    {
        if(s[i] == '[')
            left++;
        else if(left > 0)
            left--;
        else right++;
        i++;
    }
    
    for(right; right>0; right--)
        printf("[");
    printf("%s",s);
    for(left; left>0; left--)
        printf("]");
    
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 348KB, 提交时间: 2022-07-21

#include <stdio.h>

int main()
{
    char input[50];
    int i = 0;
    int stack_index = 0;
    int left_count = 0;
    int right_count = 0;
    scanf("%s", input);
    //printf("input:%s\n",input);
    
    for(i = 0; (i < 50)&&((input[i] == '[') || (input[i] == ']')); i++) {
        if (input[i] == '[') {
            stack_index++;
        } else {
            if (stack_index >= 1) {
                stack_index--;
            }else {
                left_count++;   //右括号未匹配,则左边加上一个左括号
                stack_index=0;
            }
        }
    }
    right_count = stack_index;
    
    for(i = 0; i < left_count; i++) {
        printf("[");
    }
    for(i = 0; (i < 50)&&((input[i] == '[') || (input[i] == ']')); i++) {
        printf("%c", input[i]);
        //printf("c");
    }
    for(i = 0; i < right_count; i++) {
        printf("]");
    }
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 368KB, 提交时间: 2019-05-26

#include<stdio.h>
int main()
{
    char s[51];
    scanf("%s",s);
    int i=0,left=0,right=0;
    while(s[i] != '\0')
    {
        if(s[i] == '[')
            left++;
        else if(left > 0)
            left--;
        else right++;
        i++;
    }
     
    for(right; right>0; right--)
        printf("[");
    printf("%s",s);
    for(left; left>0; left--)
        printf("]");
     
    return 0;
}

C 解法, 执行用时: 2ms, 内存消耗: 372KB, 提交时间: 2020-12-23

#include <stdio.h>
#include <string.h>

int main(){
    char* str = (char*)malloc(51*sizeof(char));
    while(scanf("%s", str) != EOF){
        char* stake = (char*)malloc(51*sizeof(char));
        int index = 0;
        int len = strlen(str);
        if(len == 0)break;
        for(int i = 0; i < len; i++){
            stake[index] = str[i];
            if(index == 0){
                index++;
                continue;
            }
            if((stake[index - 1] == '[')&&(stake[index] == ']')){
                index = index - 1;
            }else{
                index = index + 1;
            }
        }
        int flag = 0;
        if(index == 0){
            printf("%s\n", str);
            flag = 1;
        }
        for(int i = 0; i < index; i++){
            if(stake[i] == ']'){
                printf("%c", '[');
                continue;
            }
            if(stake[i] == '['){
                if(flag == 0){
                    printf("%s", str);
                    flag = 1;
                }
                printf("%c", ']');
            }
        }
        if(flag == 0){
            printf("%s\n", str);
        }else{
            printf("\n");
        }
    }
    return 0;
}

上一题