表达式求值【NOIP2013普及组】
给定一个只包含加法和乘法的算术表达式，请你编程计算表达式的值。
输入输出格式
输入格式：
输入仅有一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“+”和乘法运算符“*”，且没有括号，所有参与运算的数字均为 0 到 2^31-1 之间的整数。输入数据保证这一行只有 0~ 9、+、*这 12 种字符。
输出格式：
输出只有一行，包含一个整数，表示这个表达式的值。注意：当答案长度多于 4 位时，
请只输出最后 4 位，前导 0 不输出。
输入输出样例
输入样例：
【输入样例 1】
1 + 1 ∗ 3 + 4 1+1*3+4 1+1∗3+4
【输入样例 2】
1 + 1234567890 ∗ 1 1+1234567890*1 1+1234567890∗1
【输入样例 3】
1 + 1000000003 ∗ 1 1+1000000003*1 1+1000000003∗1
输出样例：
【输出样例 1】
8 8 8
【输出样例 2】
7891 7891 7891
【输出样例 3】
4 4 4
提示信息
【输入输出样例说明】
- 样例 1 计算的结果为 8，直接输出 8。
- 样例 2 计算的结果为 1234567891，输出后 4 位，即 7891。
- 样例 3 计算的结果为 1000000004，输出后 4 位，即 4。
【数据范围】
- 对于 30%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100；
- 对于 80%的数据，0≤表达式中加法运算符和乘法运算符的总数≤1000；
- 对于 100%的数据，0≤表达式中加法运算符和乘法运算符的总数≤100000。
想法：
我的思路非常简单，用的方法就很简单，先输入一个字符串，然后逐个将字符存入两个数组 s h u z i shuzi shuzi和 f u h a o fuhao 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;
else
fuhao[++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行， s h u z i [ + + S ] = s h u z i [ S ] ∗ 10 + a [ i ] − 48 ; shuzi[++S]=shuzi[S]*10+a[i]-48; shuzi[++S]=shuzi[S]∗10+a[i]−48;
这一句在不同的编译器中会用不同的机器语言呈现：
1、旧版编译器：首先S增加1，然后计算后面的一串东西，然后再将这一串的结果存入数组中。
2、新版编译器：首先计算后面的一串东西，然后S增加1，然后将这一串的结果存入数组中。
这就导致计算的时候S还是旧的值，并没有+1，因此会得出错误的答案。
怎么改呢？
很简单，只要将第17行的
s h u z i [ + + S ] = s h u z i [ S ] ∗ 10 + a [ i ] − 48 ; shuzi[++S]=shuzi[S]*10+a[i]-48; shuzi[++S]=shuzi[S]∗10+a[i]−48;
改为两行：
S + + ; S++; S++;
s h u z i [ + + S ] = s h u z i [ S ] ∗ 10 + a [ i ] − 48 ; shuzi[++S]=shuzi[S]*10+a[i]-48; shuzi[++S]=shuzi[S]∗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;
else
fuhao[++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;
}
看我这么细心，给我一个三连吧~~
转载：https://blog.csdn.net/DUXS11/article/details/128709861