大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺
这道题一看就跟正常表达式求值差不多,我们需要一步一步保存前一部分的得0和得1的方案数,然后再与后面的进行运算,求出下个状态的方法总数,看到这里,很多朋友肯定想到了动态规划,然而如何保存运算顺序呢,那就要用到中缀表达式转后缀表达式,再按照运算顺序进行计算,下面是代码:
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<iostream>
#include<algorithm>
const int maxn=100000;
const int mod=10007;
using namespace std;
char ss[maxn+100],s[maxn+100];
int l,top,a[maxn+100],b[maxn+100];
void add()
{
int k,k0,k1;
k=a[0];
k0=a[k-1]*a[k];
k1=a[k-1]*b[k]+b[k-1]*a[k]+b[k-1]*b[k];
a[--a[0]]=k0%mod,b[a[0]]=k1%mod;
}
void multiply()
{
int k,k0,k1;
k=a[0];
k0=a[k-1]*a[k]+a[k-1]*b[k]+b[k-1]*a[k];
k1=b[k-1]*b[k];
a[--a[0]]=k0%mod,b[a[0]]=k1%mod;
}
int main()
{
int i,j,k;
char tmp;
scanf("%d%s\n",&l,ss);
a[0]=b[0]=top=0;
for(i=0; i<l; i++) {
tmp=ss[i];
switch(tmp){
case '(':
s[++top]=tmp;
break;
case '+':{
if(i==0 || (i>0 && ss[i-1]!=')'))
a[++a[0]]=1,b[a[0]]=1;
while(top>0 && s[top]!='('){
if(s[top]=='+')add();
else multiply();
top--;
}
s[++top]=tmp;
break;
}
case '*':{
if((i>0 && ss[i-1]!=')') || i==0)
a[++a[0]]=1,b[a[0]]=1;
while(top>0 && s[top]=='*')
multiply(),top--;
s[++top]=tmp;
break;
}
default:{
if(ss[i-1]!=')')
a[++a[0]]=1,b[a[0]]=1;
while(s[top]!='('){
if(s[top]=='+')add();
else multiply();
top--;
}
top--;
break;
}
}
}
if(top>0 && ss[l-1]!=')')
a[++a[0]]=1,b[a[0]]=1;
while(top>0){
if(s[top]=='+')add();
else multiply();
top--;
}
if(l==0)printf("%d\n",1);
else printf("%d\n",a[a[0]]);
return 0;
}
这里可以看到,处理时遇到(
时直接入栈,+
号时要将所有的之前入栈的*
出栈,遇到)
再将(
出栈,然后按照这种方法运算就行了
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/193684.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...