logo AlgoBeat OnlineJudge
登录 注册

#102981. [BZOJ 2981] [Poi2002]括号

内存限制:128 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: 匿名

题目描述

减法不满足结合率,例如 ,但 ,因此 。这意味着表达式 依赖减法操作的顺序。如果没有括号,假定表达式计算从左到右,即 等于 。我们给出表达式的形式如下:

表示 (加)  (减), 表示计算变量。对下面的表达式 我们想插入 对括号得到和表达式相同的结果。例如,我们想得到和下面表达式相等值的表达式 可以对下面的表达式插入括号 得到

注意: 我们只对完整而正确的表达式有兴趣,一个完整正确的表达式必须符合

  1. 它可能是单个变量,
  2. 可能形如 ,而且 都是完整而正确的表达式。

通常来说,我们对如下空括号形式不感兴趣:。而表达式 不是完整的,因为它缺少最外层的括号。

输入格式

第一行有一个整数 ,表示表达式变量的个数。在下面的 行有一个字符 。第 行出现的字符给出了 之间的操作。

输出格式

对表达式 添加 对括号,使得它与给出的表达式等价,表示插入空格的不同方案数,答案不超过

样例输入

7
-
-
+
+
-
+

样例输出

3

数据范围与提示

对于 的数据,