首页 > 试题广场 >

括号匹配深度

[编程题]括号匹配深度

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

输入

(())

输出

算法知识视频讲解

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)

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)

小谷围做题家

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)

只会写java的程序猿

import java.util.Scanner;
public class Main{
    public static void main(String[] args){
        Scanner sc=new Scanner(System.in);
        String s=sc.nextLine();
        int count=0,res=0;
        for(int i=0;i<s.length();i++){
            if(s.charAt(i)=='('){
                count++;
            }else{
                count--;
            }
            res=Math.max(res,count);
        }
        sc.close();
        System.out.println(res);
    }
}

发表于 2021-07-12 21:21:51 回复(0)

Java

薛猫201811222034408

import java.util.Scanner;

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

    public static int getDeep(String s) {
        char[] chs = s.toCharArray();
        int res = Integer.MIN_VALUE;
        int cnt = 0;
        for (int i = 0; i < chs.length; i++) {
            if (chs[i] == '(') {
                cnt++;
            } else {
                cnt--;
            }
            if (cnt < 0) {
                cnt = 0;
            }
            res = Math.max(res, cnt);
        }
        return res;
    }
}

发表于 2021-04-14 16:23:43 回复(0)

Java

牛客196305255号

 public static void solve(String str) {
	int count=0;
	while(!str.isEmpty()) {
	    str=str.replace("()", "");
	    count++;
	}
	System.out.println(count);
}

发表于 2021-01-12 20:02:30 回复(0)

Java

何止hz

import java.util.Scanner;
import java.util.Stack;

/**
 * @Author: coderjjp
 * @Date: 2020-05-15 7:32
 * @Description: 括号匹配深度
 * @version: 1.0
 */
public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        int ans = 0;
        Stack<Character> stack = new Stack<>();
        int i = 0;
        while (i < s.length()){
            if (s.charAt(i) == '('){
                stack.push('(');
                i++;
            }
            else {
                ans = Math.max(ans, stack.size());
                while (i < s.length() && s.charAt(i) == ')'){
                    stack.pop();
                    i++;
                }
            }
        }
        System.out.println(ans);
    }
}

发表于 2020-05-15 08:45:46 回复(0)

Shelven丶

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

int main()
{
	string s;
	cin >> s;
	int _max = 0;
	stack<char> sc;
	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == '(')
		{
			sc.push(s[i]);
			if (sc.size() > _max)_max = sc.size();
		}
		else sc.pop();
	}
	cout << _max;
}

发表于 2020-04-30 21:39:18 回复(0)

提交观点

问题信息

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

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

上传者：小小

难度：

57条回答 58收藏 13154浏览

通过挑战的用户

查看代码

在做核酸的布莱...

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解法

问题信息

热门推荐

通过挑战的用户

相关试题