题目描述

阔浩序列是这样定义的:

1. 空串是合法的序列,且代价=1
2. 如果 s 是合法的阔浩序列,那么( s )也是合法的,且( s )的代价为 s+1
3. 如果s,t都是合法的,那么它们拼接起来的 st 也是合法,且总的代价为s的代价*t 的代价。

例如,(()())()是合法的，其代价为(2*2+1)*2=10

输入
一行仅包含“("和“)"的合法序列。(不含引号)
100%的数据保证,阔浩序列长度 len 满足1<= len <=200,000
输出
输出一个数，阔浩序列的代价。由于答案可能过大,所以输出取模，设代价为 ans ,输出 ans % P ( P =1,000,000,007)

例如()()()(())=222*3=24

思路题解

类似于力扣856. 括号的分数这个题，其中计算方式可能发生了变化但是基本思想差不多，可以使用栈的思想来记录当前字符状态下的代价。
对于本题，即分为以下三种情况：

1.s[i]为'('时，压入0，代表一个新的括号的开始
2.s[i]为')'时，判断s[i-1]是否为'('2.1 s[i-1]为'(':  因'()'的代价为2，因此直接压入22.2 s[i-1]为')':  当stack.pop()不为0时，一直相乘stack里面的数存到tmp里，象征A*B当stack.pop()为0时，代表一个部分的结束，返回tmp+1，象征着A+1

ps：因为默认输入为合法的，因此可以放心的使用s[i-1]
最后AC

s=input()
stack=[]
if len(s)==1:print(0)
else:for i in range(len(s)):if s[i]=="(":stack.append(0)else:if s[i-1]=="(":stack.pop()stack.append(2)else:tmp = 1while stack:v=stack.pop()if v==0:stack.append(tmp+1)breakelse:tmp*=vprint(stack)ans=1p=1000000007while stack:v=stack.pop()if v!=0:ans=ans*v%pprint(ans%p)
#((())())