主要是對(duì)于表達(dá)式處理算法的概念比較模糊，類比應(yīng)用起來(lái)不是很順，一開(kāi)始把想把數(shù)值棧給省略只用O（1）的空間儲(chǔ)存結(jié)果，結(jié)果發(fā)現(xiàn)有問(wèn)題，遲遲沒(méi)有下手。
這兩天復(fù)習(xí)了一下表達(dá)式處理算法，逃了一天晚自習(xí)回家輕松的AC了此題。
在導(dǎo)刊上看到SHUXK牛的題解，是基于分治算法，利用手工棧解決的。一方面我們可以肯定他作為初三同學(xué)的高超水平。
另一方面，我們可以思考，對(duì)于在考場(chǎng)上果斷分治90分是很好的，但進(jìn)而用手工棧來(lái)AC的話，還不如使用正解的算法。
思路不想說(shuō)了，表達(dá)式處理的基本算法和簡(jiǎn)單的統(tǒng)計(jì)知識(shí)。
AC代碼
#include<cstdio>
#include<cstring>
const int mod=10007;
char exp[100005];
int n;
int stacka[100005],stackb[100005];
char stackc[100005];
int stab=0,stc=0;
void dorp();
int main(){
freopen("exp.in","r",stdin);
freopen("exp.out","w",stdout);
scanf("%d ",&n);
for(int i=1;i<=n;i++)
scanf("%c ",&exp[i]);
stab++;
stacka[stab]=stackb[stab]=1;
for(int i=1;i<=n;i++){
if(exp[i]=='+'){
while(stc&&stackc[stc]=='*')
dorp();
stc++;
stackc[stc]='+';
stab++;
stacka[stab]=stackb[stab]=1;
}
if(exp[i]=='*'){
stc++;
stackc[stc]='*';
stab++;
stacka[stab]=stackb[stab]=1;
}
if(exp[i]=='('){
stc++;
stackc[stc]='(';
stab++;
stacka[stab]=stackb[stab]=1;
}
if(exp[i]==')'){
while(stc&&stackc[stc]!='(')
dorp();
dorp();
}
}
while(stc)
dorp();
printf("%d ",stacka[1]);
fclose(stdin);
fclose(stdout);
return 0;
}
void dorp(){
int a,b;
if(stackc[stc]=='+'){
a=stacka[stab]*stacka[stab-1];
b=stackb[stab]*stackb[stab-1]+stacka[stab]*stackb[stab-1]+stackb[stab]*stacka[stab-1];
}
if(stackc[stc]=='*'){
a=stacka[stab]*stacka[stab-1]+stacka[stab]*stackb[stab-1]+stackb[stab]*stacka[stab-1];
b=stackb[stab]*stackb[stab-1];
}
a%=mod;
b%=mod;
stacka[stab-1]=a;
stackb[stab-1]=b;
stc--;
stab--;
}