游客 Signup | Login
中文 | En

2676 - 表达式的值

【问题描述】

对于 1 位二进制变量定义两种运算：


<tbody>
    <tr>
        <td>运算符</td>
        <td>运算规则</td>
    </tr>
    <tr>
        <td>&oplus;</td>
        <td>0&oplus;0=0<br />
        0&oplus;1=1<br />
        1&oplus;0=1<br />
        1&oplus;1=1</td>
    </tr>
    <tr>
        <td>&times;</td>
        <td>0&times;0=0<br />
        0&times;1=0<br />
        1&times;0=0<br />
        1&times;1=1</td>
    </tr>
</tbody>

运算的优先级是：
1.  先计算括号内的，再计算括号外的。
2.  “×”运算优先于“⊕”运算，即计算表达式时，先计算×运算，再计算⊕运算。
例如：计算表达式 A⊕B×C 时，先计算 B×C，其结果再与A做⊕运算。
现给定一个未完成的表达式，例如 +(*_)，请你在横线处填入数字0或者1，请问有多少种填法可以使得表达式的值为0。 
 

Input

输入文件共2 行。

第1 行为一个整数 L，表示给定的表达式中除去横线外的运算符和括号的个数。
第2 行为一个字符串包含 L 个字符，其中只包含’(’、’)’、’+’、’’这4 种字符，其中(’、’)’是左右括号，’+’、’’分别表示前面定义的运算符“⊕”和“×”。这行字符按顺序给出了给定表达式中除去变量外的运算符和括号。

Output

输出共1 行。包含一个整数，即所有的方案数。注意：这个数可能会很大，请输出方案数对 10007取模后的结果。

Examples

Input

4
+(*)

Output

3

Hint



输入输出样例说明：  给定的表达式包括横线字符之后为： +(_*_) 在横线位置填入(0、0、0)、(0、1、0)、(0、0、1)时，表达式的值均为 0，所以共有 3种填法。
数据范围：

对于 20%的数据有 0<=L<=10。 

对于 50%的数据有 0<=L<=1,000。 

对于 70%的数据有 0<=L<=10,000。 

对于 100%的数据有 0<=L<=100,000。 

对于 50%的数据输入表达式中不含括号。


NOIP2011 普及组 exp

Solution C++

#include<iostream>
#include<stack>

#define yxj_equal sc.top()=='('&&text[i]==')'
#define yxj_low (sc.top()=='('&&text[i]!=')')||(sc.top()=='*'&&text[i]=='(')||(sc.top()=='+'&&(text[i]=='('||text[i]=='*'))
using namespace std;
 
const int MOD = 10007;
char text[100010];
int len;
stack<int> s0, s1;
stack<int> sc;
 
void init()
{
     cin >> len;
     cin >> text;
     while (!s0.empty()) s0.pop();
     while (!s1.empty()) s1.pop();
     while (!sc.empty()) sc.pop();
     text[len++] = ')';
     text[len] = '\0';
     sc.push('('); s0.push(1); s1.push(1);
}
 
int main()
{
    init();
    int i = 0;
    while (i < len)
    {
          if (yxj_equal)
          {
              sc.pop();
              i++;
          }
          else
          {
              if (yxj_low)
              {
                  sc.push(text[i]);
                  if (text[i] != '(')
                  {
                      s0.push(1);
                      s1.push(1);
                  }
                  i++;
              }
              else
              {
                  if (!yxj_low)
                  {
                      int a0 = s0.top(), a1 = s1.top(), rec0, rec1;
                      s0.pop(); s1.pop();
                      int b0 = s0.top(), b1 = s1.top();
                      s0.pop(); s1.pop();
                      char ch = sc.top();
                      sc.pop();
                      if (ch == '+')
                      {
                          rec0 = a0*b0%MOD;
                          rec1 = (a1*b0%MOD+a0*b1%MOD+a1*b1%MOD)%MOD;
                      }
                      else
                      {
                          rec1 = a1*b1%MOD;
                          rec0 = (a1*b0%MOD+a0*b1%MOD+a0*b0%MOD)%MOD;
                      }
                      s0.push(rec0);
                      s1.push(rec1);
                  }
              }
          }
    }
    cout << s0.top() << endl;
    return 0;
}

Hint

输入输出样例说明：  给定的表达式包括横线字符之后为： +(_*_) 在横线位置填入(0、0、0)、(0、1、0)、(0、0、1)时，表达式的值均为 0，所以共有 3种填法。

数据范围：
对于 20%的数据有 0<=L<=10。
对于 50%的数据有 0<=L<=1,000。
对于 70%的数据有 0<=L<=10,000。
对于 100%的数据有 0<=L<=100,000。
对于 50%的数据输入表达式中不含括号。

NOIP2011 普及组 exp

Time Limit 1 second
Memory Limit 128 MB
Discuss Stats
上一题 下一题