括号匹配

[编程题]括号匹配

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

给定一个只包含左右括号的合法括号序列，按右括号从左到右的顺序输出每一对配对的括号出现的位置（括号序列以0开始编号)。

输入描述:

仅一行，表示一个合法的括号序列。 长度不超过100000。

输出描述:

设括号序列有n个右括号。则输出包括n行，每行两个整数l，r，表示配对的括号左括号出现在第l位，右括号出现在第r位。

示例1

输入

(())()

输出

1 2
0 3
4 5

算法知识视频讲解

查看答案及解析

Python

Katewutao

def test(str1):
    if len(str1)%2!=0:
        return False
    test_times=int(len(str1)/2)
    delete_list=list(range(len(str1)))
    for _ in range(test_times):
        for j in range(len(delete_list)-1):
            if str1[delete_list[j]]=="(" and str1[delete_list[j+1]]==")":
                print(f"{delete_list[j]} {delete_list[j+1]}")
                delete_list.remove(delete_list[j+1])
                delete_list.remove(delete_list[j])
                break
test(input())

发表于 2023-02-21 15:00:56 回复(0)

牛客984535158号

根本不需要保存'('本身，只需要保存位置即可

发表于 2023-01-07 17:28:29 回复(0)

C/C++

小蒲想变强

双栈解法：c代码

一个char栈保存'('和')'

一个int数组保存每一次的'('的地址。

#include<stdio.h>
#include<string.h>
int main()
{
    char a[10000000];//保证case data 足够大
    while (gets(a))
    {
        int i,j=-1,k=-1;//栈顶指针初始为-1
        char t[100000000];
        int t_[100000000];
        for(i=0;i<strlen(a);i++)
        {
            if(a[i]=='(')
            {
                t[++j]=a[i];//++j
                t_[++k]=i;//++k 先加再用，保证栈底元素从0开始
            }
            else if(a[i]==')')
            {
                printf("%d %d\n",t_[k],i);//case的输出很***，被迷惑到了
                k--;//出栈，栈顶指针减一
                j--;
            } 
        }
    }
    return 0;
}

发表于 2021-09-15 09:10:04 回复(0)