【题解】表达式的值

题目描述

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

　　

　　运算的优先级是：

　　1.先计算括号内的，再计算括号外的。

　　2.“×”运算优先于“⊕”运算，即计算表达式时，先计算×运算，再计算⊕运算。

　　例如：计算表达式A⊕B×C时，先计算B×C，其结果再与A做⊕运算。

　　现给定一个未完成的表达式，例如_ (_×_)，请你在横线处填入数字0或者1，请问有多少种填法可以使得表达式的值为0。

?

输入格式

　　共2行：

　　第一行为一个整数 L，表示给定的表达式中除去横线外的运算符和括号的个数。

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

?

输出格式

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

?

输入样例

4

(*)

?

输出样例

3

?

数据规模

　　对于20%的数据，0≤L≤10。

　　对于50%的数据，0≤L≤1000。

　　对于70%的数据，0≤L≤10000。

　　对于100%的数据，0≤L≤100000。

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

?

题解

　　题目中给出的是中缀表达式，我们可以先转后缀表达式，然后补上数字的位，在模拟运算一遍这个表达式即可。

#include <iostream>#include <cstdio>#include <stack>#define MAX_LEN (100000   5)using namespace std;const int mod = 10007;int len;char s[MAX_LEN];stack <char> st;char ns[MAX_LEN   MAX_LEN];int nlen;stack <int> n0, n1;int main(){    scanf("%d%s", &len, s   2);    len  = 2;    s[1] = '(';    s[len] = ')';    ns[  nlen] = '_';    for(register int i = 1; i <= len;   i)    {        if(s[i] == '(')        {            st.push(s[i]);        }        else if(s[i] == ')')        {            while(st.top() != '(')            {                ns[  nlen] = st.top();                st.pop();            }            st.pop();        }        else if(s[i] == ' ')        {            while(st.top() != '(')            {                ns[  nlen] = st.top();                st.pop();            }            st.push(s[i]);            ns[  nlen] = '_';        }        else        {            while(st.top() == '*')            {                ns[  nlen] = st.top();                st.pop();            }            st.push(s[i]);            ns[  nlen] = '_';        }    }    int u0, u1, v0, v1;    for(register int i = 1; i <= nlen;   i)    {        if(ns[i] == '_')        {            n0.push(1);            n1.push(1);            continue;        }        u0 = n0.top();        n0.pop();        v0 = n0.top();        n0.pop();        u1 = n1.top();        n1.pop();        v1 = n1.top();        n1.pop();        if(ns[i] == ' ')        {            n0.push((u0 * v0) % mod);            n1.push((u0 * v1   u1 * v0   u1 * v1) % mod);        }        else        {            n0.push((u0 * v0   u0 * v1   u1 * v0) % mod);            n1.push((u1 * v1) % mod);        }    }    printf("%d", n0.top());    return 0;}

参考程序

?

来源：https://www.icode9.com/content-4-329801.html