一个合法的括号匹配序列有以下定义:
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。牛牛现在给你一个合法的括号序列,需要你计算出其深度。
[编程题]括号匹配深度
import java.util.*;
public class Main {
public static void main(String args[]) {
Scanner in = new Scanner(System.in);
String s = in.nextLine().trim();
char[] chs = s.toCharArray();
int res = 1;
int cur = 0;
for(int i = 0; i < chs.length - 1; i++) {
if(chs[i] == '(') ++cur;
else --cur;
res = Math.max(res,cur);
}
System.out.println(res);
}
}
发表于 2021-05-26 18:44:34
回复(0)
//简单的模拟题
//深度即当前未匹配的左括号‘（’的个数
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int main()
{
string s;
cin>>s;
int depth=0; //储存最大深度
int tot=0; //储存当前深度
for(int i=0;i<s.length();i++)
{
if(s[i]=='(') tot++; //左括号则当前深度+1
else tot--; //右括号则减一
depth=max(depth,tot); //取深度最大值
}
cout<<depth;
return 0;
}
发表于 2018-09-11 17:30:15
回复(0)
import java.util.*;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String str = in.nextLine();
char[] arr = str.toCharArray();
int max = 0;
int temp = 0;
for ( int i = 0; i < arr.length ; i ++) {
if ( '(' == arr[i]) {
temp ++;
} else if ( ')' == arr[i]) {
if ( temp > max) {
max = temp ;
}
temp --;
}
}
System.out.print(max);
}
}
发表于 2022-09-27 14:46:31
回复(0)
用的栈，很麻烦，和前几排的大佬们学习
#include <iostream>
#include <string>
using namespace std;
template<class T>
struct Node {
Node<T>* next;
T data;
Node():next(NULL){}
Node(T t):next(NULL),data(t){}
};
template <typename T>
class SqLink {
private:
Node<T>* head;
int len;
public:
SqLink(){
head = new Node<T>;
len = 0;
}
bool empty() {
return head->next == NULL;
}
bool push(T t) {
Node<T>* r = new Node<T>(t);
r->next = head->next;
head->next = r;
++len;
return true;
}
bool pop(T& t) {
if (empty())
return false;
Node<T>* r = head->next;
t = r->data;
head->next = r->next;
delete r;
--len;
return true;
}
bool getpop(T& t) {
if (empty())
return false;
Node<T>* r = head->next;
t = r->data;
return true;
}
int mymax(int& n, int& m) {
return (n > m ? n : m);
}
void mycout(string num) {
char k = NULL;
int r = 0, s = 0;
for (int i = 0; i < num.length(); ++i) {
if (num[i] == '(') {
push(num[i]);
++r;
}
else {
pop(k);
--r;
}
s = mymax(r, s);
}
cout << s << endl;
}
};
int main() {
string num;
SqLink<char> pmc;
cin >> num;
pmc.mycout(num);
return 0;
}
发表于 2022-09-24 23:03:55
回复(0)
利用栈进行求解
import java.util.*;
public class Main {
public static void main(String[] args){
Scanner in = new Scanner(System.in);
String cur = in.next();
Deque<Character> stack = new ArrayDeque<>();
int res = 0;
for(int i = 0;i < cur.length();i++){
if(cur.charAt(i) == '('){
stack.add(')');
}else{
stack.pop();
}
res = Math.max(res,stack.size());
}
System.out.println(res);
}
}
发表于 2022-07-31 17:56:44
回复(0)
#include<iostream>
using namespace std;
int main(){
string input;
int count = 0;
int res = 0;
cin >> input;
for(char &a : input){
if(a == '('){
count++;
res = count > res ? count : res;
}
else
count--;
}
cout << res;
return 0;
}
发表于 2022-04-08 23:54:25
回复(0)
list_1,list_2 = [],[]
str_1 = input()
for i in str_1:
if i == ")":
list_1.append(i)
if len(list_1)>len(list_2):
list_2 = list_1
else:
list_1 = []
str_2 = "".join(str_1)
str_3 = "".join(list_2)
int_1 = str_2.index(str_3) + len(str_3)
print(len(str_3) + str_2[int_1:].count(")") - str_2[int_1:].count("("))
python新手，有大佬看看写的对不对
发表于 2022-03-31 21:29:44
回复(0)
import java.util.*;
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
int max = 0;
int count = 0 ;
LinkedList<String> list = new LinkedList();
for(int i = 0;i< str.length(); i++){
String current = str.substring(i,i+1);
String last = list.size()!=0?list.getLast():null;
if(last!=null && current.equals(")")){
count = list.size();
list.pop();
if(list.size()>max){
max = count;
}
}else{
list.push(current);
}
}
System.out.println(max);
}
}
public class Main{
public static void main(String[] args){
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
int max = 0;
int count = 0 ;
LinkedList<String> list = new LinkedList();
for(int i = 0;i< str.length(); i++){
String current = str.substring(i,i+1);
String last = list.size()!=0?list.getLast():null;
if(last!=null && current.equals(")")){
count = list.size();
list.pop();
if(list.size()>max){
max = count;
}
}else{
list.push(current);
}
}
System.out.println(max);
}
}
发表于 2021-12-28 19:43:32
回复(0)
rec = []
depth = 0
string = input()
for i in string:
if i == '(':
depth += 1
elif i == ')':
rec.append(depth)
depth -= 1
if depth == 0:
print(max(rec))
这个方法比较慢，不用确认输入是否正确应该可以有简洁方法
发表于 2021-12-01 01:43:38
回复(0)
def deepth():
s = input()
res = 1
for i in range(len(s)):
if s[i] == '(':
if s[i] == s[i+1]:
res += 1
print(res)
if __name__ == '__main__':
deepth()
s = input()
res = 1
for i in range(len(s)):
if s[i] == '(':
if s[i] == s[i+1]:
res += 1
print(res)
if __name__ == '__main__':
deepth()
发表于 2021-09-14 17:38:03
回复(1)
def func():
str_input = input()
cnt = 0
max_len = 0
for idx,item in enumerate(str_input):
if item == '(':
cnt+=1
else:
cnt-=1
max_len= max(max_len,cnt)
print(max_len)
if __name__ == '__main__':
func()
发表于 2021-07-14 12:07:54
回复(0)
#include <iostream>
#include <stack>
#include <algorithm>
using namespace std;
int main()
{
string input;
cin>>input;
stack<char> stack_1;
int deepth = 0;
for(int i = 0; i < input.size();i++)
{
if(input[i] == '(')
stack_1.push(input[i]);
else{
stack_1.pop();
}
deepth = stack_1.size() > deepth ? stack_1.size() : deepth;
}
cout<<deepth;
}
#include <stack>
#include <algorithm>
using namespace std;
int main()
{
string input;
cin>>input;
stack<char> stack_1;
int deepth = 0;
for(int i = 0; i < input.size();i++)
{
if(input[i] == '(')
stack_1.push(input[i]);
else{
stack_1.pop();
}
deepth = stack_1.size() > deepth ? stack_1.size() : deepth;
}
cout<<deepth;
}
发表于 2021-07-07 21:16:58
回复(0)
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(stringWidth(s));
}
public static int stringWidth(String s) {
char[] ch = s.toCharArray();
int count = 0;
int depth = 0;
for (int i = 0; i < ch.length; i++) {
if (ch[i] == '(') {
count++;
} else
count--;
depth = Math.max(depth, count);
}
return depth;
}
}
发表于 2019-08-09 15:48:55
回复(0)
问题信息
通过挑战的用户
-
2023-02-13 16:40:13 -
2023-02-03 10:00:32 -
2022-12-02 16:08:20
-
2022-09-30 09:04:03 -
2022-09-15 23:53:15
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
