首页 > 试题广场 >

括号匹配深度

[编程题]括号匹配深度

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

一个合法的括号匹配序列有以下定义:
1、空串""是一个合法的括号匹配序列
2、如果"X"和"Y"都是合法的括号匹配序列,"XY"也是一个合法的括号匹配序列
3、如果"X"是一个合法的括号匹配序列,那么"(X)"也是一个合法的括号匹配序列
4、每个合法的括号序列都可以由以上规则生成。
例如: "","()","()()","((()))"都是合法的括号序列
对于一个合法的括号序列我们又有以下定义它的深度:
1、空串""的深度是0
2、如果字符串"X"的深度是x,字符串"Y"的深度是y,那么字符串"XY"的深度为max(x,y) 3、如果"X"的深度是x,那么字符串"(X)"的深度是x+1
例如: "()()()"的深度是1,"((()))"的深度是3。牛牛现在给你一个合法的括号序列,需要你计算出其深度。

输入描述:

输入包括一个合法的括号序列s,s长度length(2 ≤ length ≤ 50),序列中只包含'('和')'。

输出描述:

输出一个正整数,即这个序列的深度。

示例1

输入

(())

输出

算法知识视频讲解

Bapee

import java.util.Scanner;

public class Main {
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        int stack=0,max=0;
        for(int i=0;i<str.length();i++){
            if(str.charAt(i)=='('){
                stack++;
                max = max>stack?max:stack;
            }
            if(str.charAt(i)==')')        stack--;
        }
        System.out.println(max);
        in.close();
    }
}

编辑于 2017-12-05 00:12:15 回复(0)

元气の悟空

#include<stdio.h>
#include<stack>
using namespace std;
#define max(a,b) a>b?a:b
int main(){
    char s[100];
    stack<char> stk;
    int i,Max=0;
    for(scanf("%s",s),i=0;s[i]!='\0';i++)
        if(s[i]=='(') stk.push(s[i]),Max=max(Max,stk.size());
        else stk.pop();
    printf("%d",Max);
}

发表于 2017-11-29 13:30:52 回复(1)

C/C++

nbgao

#include <bits/stdc++.h>
using namespace std;

int main(){
    string s;
    cin>>s;
    int Max=0, l=0;
    for(auto &c :s){
        if(c==')'){
            Max = max(Max, l);
            l--;
        }else
            l++;
    }
    printf("%d\n", Max);
    return 0;
}

发表于 2020-10-17 00:16:09 回复(0)

Java

Mono_Chrome

import java.util.Scanner;

public class Main {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        String str = sc.next();
        int need = 0;
        int max = 0;
        for (int i = 0; i < str.length(); i++) {
            if (str.charAt(i) == '(') {
                need++;
                max = max > need ? max : need;
            } else {
                need--;
            }
        }
        System.out.println(max);
    }
}

发表于 2019-06-17 20:05:21 回复(0)

C/C++

懵哒懵

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

int Depth(string s)
{
int depth = 0;
int max = 0;
stack<char> st;
for(int i=0; i<s.length(); i++)
{
if(s[i] == '(')
{
st.push(s[i]);
}
else
{
depth = st.size();
st.pop();
if(max<depth)
{
max = depth;
}
}
}
return max;
}

int main()
{
string s;
cin>>s;
int depth = Depth(s);
cout<<depth<<endl;
}

发表于 2019-05-11 14:25:25 回复(0)

Java

成程晨

栈的思想
import java.util.*;
public class Main{
    public static void main(String[] args){
        try(Scanner in = new Scanner(System.in)){
            System.out.println(helper(in.nextLine()));
        }
    }
    public static int helper(String s){
        if(s.equals("")) return 0;
        char[] cs = s.toCharArray();
        int count = 0,max = 0;
        for(char c:cs){
            if(c == '('){
                count++;
                max = Math.max(max,count);
            }else{
                count--;
            }
        }
        return max;
    }
}

发表于 2019-02-11 19:43:53 回复(1)

Python

华科平凡

python解法

思路太简单了。
用一个中间数组保存左括号的数量，不断遍历字符串，碰到左括号就扔到这个数组里，碰到右括号就从数组里取出来一个左括号与之平衡掉。
在放入左括号时，每次都要计算数组的长度，其中最大的长度就是深度

a = input()
arr, res = [], 0
for i in a:
    if i == "(":  # 如果为左括号，直接扔进arr数组
        arr.append("(")
        res = max(res, len(arr))
    else:  # 此时为右括号
        arr.pop(-1)
print(res)

发表于 2019-03-02 14:28:55 回复(0)

fixit

s=raw_input()
if len(s)==0:
    print(0)
a=[]
max1=0
for i in s:
    if i=='(':
        a.append(i)
        max1=max(len(a),max1)
    else:
        a.pop()
print(max1)

发表于 2017-12-10 16:16:26 回复(0)

霍七

本套3道题的C++代码已挂到了我的GitHub(https://github.com/shiqitao/NowCoder-Solutions)，牛客网上的其他题目解答也在持续更新。

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;
int main()
{
    string sequence; cin >> sequence;
    int depth = 0, maxDepth = 0;
    for (int i = 0; i < sequence.length(); i++) {
        if (sequence[i] == '(') {
            depth++;
            maxDepth = max(maxDepth, depth);
        }
        else depth--;
    }
    cout << maxDepth << endl;
    return 0;
}

发表于 2017-12-21 10:38:25 回复(0)

pandaC222

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int INF = 0x3f3f3f3f3f3f3f3f;

void solve(){
    stack<char> st;
    string s;cin>>s;
    int ans=0;
    for(auto i:s){
        if(i=='(') st.push(i);
        else if(i==')') st.pop();
        else ans=max(ans,(int)st.size()+(i-'0'));
        ans=max(ans,(int)st.size());
    }
    cout<<ans;
}
signed main(){
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(nullptr);
    int t=1;
    // cin>>t;
    while(t--){
        solve();
    }return 0;
}

发表于 2026-02-05 13:30:14 回复(0)

Java

比企苦

import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.time.YearMonth;
import java.time.format.DateTimeFormatter;
import java.util.*;
import java.io.*;

public class Main {
	public static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	public static StreamTokenizer st = new StreamTokenizer(br);

	
	public static void main(String[] args) throws IOException {
		char[] c=br.readLine().toCharArray();
		char[] stack=new char[c.length];
		int flot=0;
		int[] arr=new int[50]; 
		for(int i=0;i<c.length;i++) {
			if(flot==0) {
				stack[flot]=c[i];
				flot++;
			}else {
				if(c[i]==')') {
					arr[flot-1]=Math.max(arr[flot]+1,arr[flot-1]);
					arr[flot]=0;
					flot--;
				}else {
					stack[flot]=c[i];
					flot++;
				}
			}
		}
		System.out.println(arr[flot]);
	}
}

发表于 2026-04-15 16:32:46 回复(0)

C++

eat_yumi

如果括号只有 ' $($ ' 和 ' $)$ '，那么有一种 $\text{Trick}$ ：用 $+1$ 表示' $($ '，用 $-1$ 表示' $)$ '。
此时我们从左往右累加会发现当最后的和为 $0$ ，并且之前的累加和都 $\ge 0$ 时候的括号序列是合法的。
继续观察，发现深度的最大值就是累加和的最大值（保证是合法括号序列的前提）。由此我们直接遍历计算即可。时间复杂度为 $O(n)$ 。

#include <iostream>
using namespace std;

int main() {
    string s;
    cin >> s;
    int ans = 0, tmp = 0;
    for(int i = 0;i < s.length();i++){
        if(s[i] == '(') tmp++;
        else   tmp--;
        ans = max(ans, tmp);
    }
    cout << ans << "\n";
}

发表于 2026-02-05 01:59:01 回复(0)

C++

巴拉巴拉hhz

#include <iostream>
using namespace std;

int main() {
    int a, b;
    string str;
    cin>>str;
    // char *p=str;
    int length=str.length();
    int maxdeep=0,deeping=0;
    for(int i=0;i<length;++i){
        if(str[i]=='(')  ++deeping;
        else{
            if(maxdeep<deeping) maxdeep=deeping;
            --deeping;
        }
    }
    cout<<maxdeep<<endl;
}

发表于 2026-01-08 18:30:17 回复(0)

Python3

TS9527

栈+贪心

class MainActivity:

    def main(self):
        # Read the data
        s = input()
        # Initialization
        stack = []
        result = 0
        # Traverse
        for char in s:
            if stack:
                if char == '(':
                    stack.append('(')
                else:
                    if stack and stack[-1] == '(':
                        stack.pop()
            else:
                stack.append(char)
            result = max(result, len(stack))
        print(result)


if __name__ == '__main__':
    M = MainActivity()
    M.main()

发表于 2024-08-26 17:50:13 回复(0)

小谷围做题家

package main

import (
    "fmt"
)

func main() {
    var s string
    fmt.Scan(&s)
    ans:=0
    stk:=[]byte{}
    for _,ch:=range []byte(s){
        if len(stk)>0&&stk[len(stk)-1]=='('&&ch==')'{
            stk=stk[:len(stk)-1]
        }else{
            stk=append(stk,ch)
        }
        if len(stk)>ans{
            ans=len(stk)
        }
    }
    fmt.Print(ans)
}

发表于 2023-03-21 22:28:45 回复(0)

Python3

牛客991380985号

s = input()

# write code here
stack = []
max_num = 0
for i in s:
    if i == "(":
        stack.append(i)
        if len(stack) > max_num:
            max_num = len(stack)
    elif i == ")":
        if stack:
            stack.pop()

print(max_num)

发表于 2023-02-22 14:15:01 回复(0)

支点

#include <iostream>
using namespace std;

int main()
{
	string str; cin >> str;
	
	int sum, max=0;
	for(int i=0; i<str.size(); i++)
	{
		if(str[i] == '(') 
		{
			sum++;
			if(sum > max)
				max = sum;
		}
		else if(str[i] == ')')
			sum--;
		else{}
	}
	
	cout << max << endl;
}

发表于 2022-09-02 20:41:12 回复(0)

Java

kakatalon

搞点走捷径的方法：循环把（）替换为空，记录循环次数即为深度了

import java.util.*;
public class Main {
    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int count = 0;
        while ( s.length()>1 ){
            s = s.replace("()" , "");
            count++;
        }
        System.out.println(count);
    }        
}

发表于 2022-06-08 09:00:18 回复(0)

Java

Leo兵

import java.util.*;

public class Main{
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
int solution = solution(s);
System.out.println(solution);
}

public static int solution(String s) {
int n = s.length();
if (n == 0) {
return 0;
}
Deque<Character> deque = new ArrayDeque<>();
deque.addLast(s.charAt(0));
int i = 1;
int maxSize = 0;
while (i < n) {
char c = s.charAt(i);
if (c == '(') {
deque.addLast(c);
maxSize = Math.max(maxSize, deque.size());
} else if (c == ')') {
deque.pop();
}
i++;
}
return maxSize;
}
}

发表于 2022-05-03 10:38:18 回复(0)

给个大厂offfer吧

import java.util.Scanner;
import java.util.Stack;
import java.lang.Math;
public class Main{
    public static void main(String[] args){
        int res = 0;
        Scanner sc = new Scanner(System.in);
        Stack<Character> stack = new Stack<>();
        String s = sc.next();
        char[] chars = s.toCharArray();
        for(int i = 0;i<chars.length;i++){
        char c = chars[i];
            if(c == '('){
                stack.push(c);
                res = Math.max(res,stack.size());
            }
            else{
                if(!stack.isEmpty())
                    stack.pop();
            }
        }
        System.out.println(res);
    } 
}

发表于 2021-12-01 15:02:27 回复(0)

提交观点

问题信息

字符串穷举栈算法工程师爱奇艺 2018 递归

来自：爱奇艺2018秋季校招...

上传者：小小

难度：

62条回答 77收藏 19708浏览

通过挑战的用户

查看代码

在做核酸的布莱...

2023-03-08 20:48:21
QKhearn

2023-02-09 17:59:41
MianShi...

2022-11-30 21:18:25
牛客11896...

2022-10-19 20:21:09
亲切的香菇不愿...

2022-10-07 17:49:23

括号匹配深度

输入描述:

输出描述:

输入

输出

python解法

问题信息

热门推荐

通过挑战的用户

相关试题