表达式求值【NOIP2013普及组】

给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。

输入输出格式

输入格式：

输入仅有一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“+”和乘法运算符“*”，且没有括号，所有参与运算的数字均为 0 到 2^31-1 之间的整数。输入数据保证这一行只有 0~ 9、+、*这 12 种字符。

输出格式：

输出只有一行，包含一个整数，表示这个表达式的值。注意：当答案长度多于 4 位时，
请只输出最后 4 位，前导 0 不输出。

输入输出样例

输入样例：

【输入样例 1】

$1+1\ast 3+4$

【输入样例 2】

$1+1234567890\ast 1$

【输入样例 3】

$1+1000000003\ast 1$

输出样例：

【输出样例 1】

$8$

【输出样例 2】

$7891$

【输出样例 3】

$4$

提示信息

【输入输出样例说明】

• 样例 1 计算的结果为 8，直接输出 8。
• 样例 2 计算的结果为 1234567891，输出后 4 位，即 7891。
• 样例 3 计算的结果为 1000000004，输出后 4 位，即 4。

【数据范围】

• 对于 30%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100；
• 对于 80%的数据，0≤表达式中加法运算符和乘法运算符的总数≤1000；
• 对于 100%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100000。

想法：

我的思路非常简单，用的方法就很简单，先输入一个字符串，然后逐个将字符存入两个数组$shuzi$和$fuhao$总，分别表示数字和符号。
然后枚举每一位数和符号，先算乘法，将算过的数标记一下，在算加法就行了~~

代码：

代码可简单了~

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;
long long l,t,S,F,fuhao[200000],shuzi[200000];
string a;
int main()
{//freopen ("expr.in","r",stdin);//freopen ("expr.out","w",stdout);cin >>a; l=a.size();for (int i=0;i<l;i++){if (!t){shuzi[++S]=shuzi[S]*10+a[i]-48;t=1;}else{if (a[i]>='0' && a[i]<='9')shuzi[S]=shuzi[S]*10+a[i]-48;else{shuzi[S]%=10000;if (a[i]=='+')fuhao[++F]=1;elsefuhao[++F]=2;t=0; }}}for (int i=1;i<=F;i++){if (fuhao[i]==2){fuhao[i]=-1;shuzi[i+1]*=shuzi[i];shuzi[i+1]%=10000;shuzi[i]=-1;}}int i=1,t1=1,t2=2;while (i<=F){while (shuzi[t1]==-1) t1++;while (shuzi[t2]==-1 || t2<=t1) t2++;while (fuhao[i]==-1) i++;if (fuhao[i]==1){shuzi[t2]+=shuzi[t1];shuzi[t2]%=10000;shuzi[t1]=-1;fuhao[i]=-1;}}cout <<shuzi[S];
//	fclose(stdin);
//	fclose(stdout);return 0;
}

只有60多行，是不是很“短”呀？
但是你如果直接抄代码，你会发现，此代码在比较新的编译器下会全部错误答案，但在比较旧的编译器下可以AC！！
为什么呢？
这就涉及到编译器的问题了：
我们看第17行，$shuzi[++S]=shuzi[S]\ast 10+a[i]-48;$
这一句在不同的编译器中会用不同的机器语言呈现：
1、旧版编译器：首先S增加1，然后计算后面的一串东西，然后再将这一串的结果存入数组中。
2、新版编译器：首先计算后面的一串东西，然后S增加1，然后将这一串的结果存入数组中。
这就导致计算的时候S还是旧的值，并没有+1，因此会得出错误的答案。
怎么改呢？
很简单，只要将第17行的

$shuzi[++S]=shuzi[S]\ast 10+a[i]-48;$

改为两行：

$S++;$
$shuzi[++S]=shuzi[S]\ast 10+a[i]-48;$

就可以了~
下面给出完整代码：

#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
using namespace std;
long long l,t,S,F,fuhao[200000],shuzi[200000];
string a;
int main()
{//freopen ("expr.in","r",stdin);//freopen ("expr.out","w",stdout);cin >>a; l=a.size();for (int i=0;i<l;i++){if (!t){S++; shuzi[S]=shuzi[S]*10+a[i]-48;t=1;}else{if (a[i]>='0' && a[i]<='9')shuzi[S]=shuzi[S]*10+a[i]-48;else{shuzi[S]%=10000;if (a[i]=='+')fuhao[++F]=1;elsefuhao[++F]=2;t=0; }}}for (int i=1;i<=F;i++){if (fuhao[i]==2){fuhao[i]=-1;shuzi[i+1]*=shuzi[i];shuzi[i+1]%=10000;shuzi[i]=-1;}}int i=1,t1=1,t2=2;while (i<=F){while (shuzi[t1]==-1) t1++;while (shuzi[t2]==-1 || t2<=t1) t2++;while (fuhao[i]==-1) i++;if (fuhao[i]==1){shuzi[t2]+=shuzi[t1];shuzi[t2]%=10000;shuzi[t1]=-1;fuhao[i]=-1;}}cout <<shuzi[S];
//	fclose(stdin);
//	fclose(stdout);return 0;
}

看我这么细心，给我一个三连吧~~