输入包括一行,一个合法的括号序列s,序列长度length.
输出一个整数,表示方案数
(((())))
24
()()()
1
import java.util.Scanner;
import java.util.Stack;
/**
* 京东2018秋招Android
* 括号匹配方案
* 合法的括号匹配序列被定义为:
* 1. 空串""是合法的括号序列
* 2. 如果"X"和"Y"是合法的序列,那么"XY"也是一个合法的括号序列
* 3. 如果"X"是一个合法的序列,那么"(X)"也是一个合法的括号序列
* 4. 每个合法的括号序列都可以由上面的规则生成
* 例如"", "()", "()()()", "(()())", "(((())))"都是合法的。 东东现在有一个合法的括号序列s,
* 一次移除操作分为两步:
* 1. 移除序列s中第一个左括号
* 2. 移除序列s中任意一个右括号.保证操作之后s还是一个合法的括号序列
* 东东现在想知道使用上述的移除操作有多少种方案可以把序列s变为空
* 如果两个方案中有一次移除操作移除的是不同的右括号就认为是不同的方案。
* 例如: s = "()()()()()",输出1, 因为每次都只能选择被移除的左括号所相邻的右括号.
* s = "(((())))",输出24, 第一次有4种情况, 第二次有3种情况, ... ,依次类推, 4 * 3 * 2 * 1 = 24
* 输入描述:
* 输入包括一行,一个合法的括号序列s,序列长度length(2 ≤ length ≤ 20).
* 输出描述:
* 输出一个整数,表示方案数
* 输入例子1:
* (((())))
* 输出例子1:
* 24
*
* 思路：遍历字符串，每次把左括号都压入栈，每次遇到右括号，先统计栈中有几个左括号，统计数与上次统计数相乘
* 接着弹出栈中的一个左括号
* 直到遍历结束，结果即为方案数
*/
public class BracketMatch {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.next();
Stack<Character> stack = new Stack<>();
int result = 1;
char c;
for (int i = 0; i < s.length(); i++) {
c = s.charAt(i);
if (c == '(') {
stack.push(c);
}
if (c == ')') {
int size = stack.size();
result *= size;
stack.pop();
}
}
System.out.println(result);
}
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String S = scanner.next();
int index = 0;
int result = 1;
for (int i = 0; i < S.length(); i++) {
if(S.charAt(i) == '('){
index ++;
}else{
result *= index;
index--;
}
}
System.out.println(result);
}
}
//碰到'('则入栈，碰到')'统计栈中'('个数size，res*=size，然后出栈一个'('
//因为要选不同的')'删去，而')'都在序列中，删除操作不好执行（或是说复杂度较高）
//且可删除的')'若有多个，那么删除不同的')'可能使得剩下的序列不同，这会使问题复杂
//因此逆向思考，既然'('可以匹配多个')'，同理，')'也可以匹配多个'('
//这样处理也有一个极大的好处，当')'定了，去掉前面哪个'('后剩下的序列都相同，这样可以使用乘法定理
#include <stdio.h>
#include <string.h>
const int N = 21;
int main() {
char str[N], signStack[N];
while(~scanf("%s",str)){
int len = strlen(str);
int res = 1, top = 0;
for(int i=0;i<len;i++){
if(str[i]=='(') signStack[top++] = '(';
else{
res*=top;
top--;
}
}
printf("%d\n",res);
}
return 0;
}
#include <stdio.h>
#include <string.h>
int len;
char s[25];
int dfs(int step);
int main()
{
int i;
gets(s);
len = strlen(s);
//'('->1
//')'->2
for(i=0;i<len;i++)
if(s[i]=='(')
s[i] = 1;
else
s[i] = 2;
printf("%d\n",dfs(0));
return 0;
}
int dfs(int step)
{
if(step==len)
return 1;
if(s[step]!=1)
return dfs(step+1);
int i,flag=1,sum=0;
for(i=step+1;i<len && flag;i++)
{
if(s[i]==2)
{
flag--;
s[i] = 0;
sum += dfs(step+1);
s[i] = 2;
}
else if(s[i])
flag++;
}
return sum;
} //题目描述
//合法的括号匹配序列被定义为 :
//1. 空串""是合法的括号序列
//2. 如果"X"和"Y"是合法的序列, 那么"XY"也是一个合法的括号序列
//3. 如果"X"是一个合法的序列, 那么"(X)"也是一个合法的括号序列
//4. 每个合法的括号序列都可以由上面的规则生成
//例如"", "()", "()()()", "(()())", "(((())))"都是合法的。 东东现在有一个合法的括号序列s, 一次移除操作分为两步 :
// 1. 移除序列s中第一个左括号
// 2. 移除序列s中任意一个右括号.保证操作之后s还是一个合法的括号序列
// 东东现在想知道使用上述的移除操作有多少种方案可以把序列s变为空
// 如果两个方案中有一次移除操作移除的是不同的右括号就认为是不同的方案。
// 例如 : s = "()()()()()", 输出1, 因为每次都只能选择被移除的左括号所相邻的右括号.
// s = "(((())))", 输出24, 第一次有4种情况, 第二次有3种情况, ..., 依次类推, 4 * 3 * 2 * 1 = 24
// 输入描述 :
// 输入包括一行, 一个合法的括号序列s, 序列长度length(2 ≤ length ≤ 20).
// 输出描述 :
// 输出一个整数, 表示方案数
//输入：(((())))
//输出：24
//输入：((()))(()(()))((()))
//输出：432
#include<iostream>
#include<string>
using namespace std;
int main() {
string str;
getline(cin, str); int num = 1, count = 1;
for (int i = 0; i < str.size(); i++)
(str[i] == '(')?num *= (++count-1):count--;
cout << num;
return 0;
}
// 每当遇到（ 就进栈，遇到 ） 就结构乘以栈的大小，并将 （ 出栈。
// 一般括号之类的题目基本上都运用栈解决
#include <iostream>
#include <stack>
#include <string>
using namespace std;
int main()
{
string str;
cin >> str;
int size = str.size();
stack<char> st;
st.push(str[0]);
int result = 1;
for(int i = 1; i < size; i++)
{
if(str[i] == ')')
{
result *= st.size();
st.pop();
}
else if(str[i] == '(')
st.push(str[i]);
}
cout << result;
return 0;
}
#include <bits/stdc++.h>
#define LL long long
#define ULL unsigned long long
#define lowbit(x) ((x)&(-x))
#define INF 0x3f3f3f3f
using namespace std;
/*
* 京东 括号匹配方案
* 由于长度最长也就20，再加上这个时间限制……是否可以暴力搜索？
* 但是搜着搜着发现，其实这道题可以稍微优化一下，变成记忆化搜索，也就是动态规划。
*
* dp[s]代表s变成空的方案数
* 初始状态是()，可以通过一次变化变成空(dp["()"] = 1)
* 如果本身就是空，就不能通过变换得到空(dp[""] = 0) （不过这个貌似是多余的，到了()就会返回
*
* 用(()())这个序列做个例子
* (()())
* / | \
* (()) ()() ()()
* / \ | \
* () () () ()
*
* 一共有4种方案，其中()()重复出现，所以可以做一个记忆化搜索
* 时间复杂度比讨论中其他的要大吧……第一反应其实不是这个做法，但是错了几次，就放弃了。
* 拼着贴近时间限制的想法尝试一下搜索，没想到过了。
*/
int ans = 1;
unordered_map<string, int> dp;
bool isLegal(string &s) {
// 利用计数模拟入栈出栈
int cnt = 0;
for(int i = 0; i < s.size(); ++i) {
if(s[i] == '(') {
++cnt;
}
if(s[i] == ')') {
if(cnt == 0) {
return false;
}
else {
--cnt;
}
}
}
return cnt == 0;
}
int dfs(string &s) {
if(dp.count(s)) {
return dp[s];
}
dp[s] = 0;
for(int i = 0; i < s.size(); ++i) {
if(s[i] == '(') {
for(int j = i + 1; j < s.size(); ++j) {
if(s[j] == ')') {
string tmp;
for(int k = i + 1; k < s.size(); ++k) {
if(k != j) tmp.push_back(s[k]);
}
if(isLegal(tmp)) {
dp[s] += dfs(tmp);
}
}
}
break;
}
}
return dp[s];
}
int main()
{
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
cin.tie(nullptr);
ios::sync_with_stdio(false);
dp[""] = 0;
dp["()"] = 1;
string s;
cin >> s;
ans = dfs(s);
cout << ans << endl;
return 0;
}
#include <string>
#include <iostream>
using namespace std;
int main(){
string s;
while(getline(cin, s)){
int result = 1;
int nums = 0;
for(size_t i = 0; i < s.size();++i){
if(s[i] == '('){
++nums;
}
else{
result *= nums;
--nums;
}
}
cout << result << endl;
}
} 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
/**
* @author wylu
*/
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
char[] s = br.readLine().toCharArray();
int res = 1, count = 0;
for (char ch : s) {
if (ch == '(') count++;
else res *= count--;
}
System.out.println(res);
}
}
扫描二维码，关注牛客网
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
京公网安备
11010502036488号
