2981. [Poi2002]括号
#2981. [Poi2002]括号
题目描述
减法不满足结合率, 例如 (5-2)-1=2, 但 5-(2-1)=4, 因此 (5-2)-1<>5-(2-1). 这意味着表达式5-2-1 依赖减法操作的顺序. 如果没有扩号，假定表达式计算从左到右, 即5-2-1 等于 (5-2)-1.我们给出表达式的形式如下：
x 1 +/- x 2 +/- ... +/- x n,
+/- 表示+ (加) - (减), x 1, x 2,..., x n 表示计算变量. 对下面的表达式
x 1- x 2-...- x n
我们想插入 n -1对括号得到和表达式相同的结果.例如，我们想得到和下面表达式相等值的表达式
x 1- x 2- x 3+ x 4+ x 5- x 6+ x 7
可以对下面的表达式插入括号
x 1- x 2- x 3- x 4- x 5- x 6- x 7
得到
((( x 1- x 2)-(( x 3- x 4)- x 5))-( x 6- x 7)).
注意: 我们只对完整而正确的表达式有兴趣，一个完整正确的表达式必须符合
- 它可能是单个变量,
- 可能形如( w 1- w 2), 而且 w 1 和 w 2 都是完成而正确的表达式.
通常来说，我们对如下空括号形式不感兴趣: (), ( x i), ((...)). 而表达式 x 1-( x 2- x 3) 不是完整的，因为它缺少最外层的括号.
输入格式
第一行有一个整数 n , 2<= n <=1 000 000. 表示表达式变量的个数.在下面的 n -1 行有一个字符+ 或 -. 第
i 行 出现的字符给出了 x i-1 和 x i 之间的操作.
输出格式
对表达式 x 1- x 2-...- _x n_添加n-1对括号，使得它与给出的表达式等价。在naw.out
中写入一个整数，表示插入空格的不同方案数，答案不超过1 000 000 000。
样例
样例输入
7
-
-
+
+
-
+
样例输出
3