题目描述
给定一个只包含加法和乘法的算术表达式,请你编程计算表达式的值。保证表达式合法。
输入
一行,一个表达式,表达式中只包含数字、加法运算符“+”和乘法运算符“*”,且没有括号,所有参与运算的数字均为 0到 2^31-1 之间的整数。输入数据保证这一行只有0~ 9、+、*这12种字符。
一个整数,表示这个表达式的值。注意:当答案长度多于4位时,请只输出最后4位,前导0不输出。
输入样例1
样例输入
1+1*3+4
样例输出
8
提示
(NOIP2013junior-2)
输入样例2
1+1234567890*1
输出样例2
7891
输入样例3
1+1000000003*1
输出样例3
4
样例说明
样例1计算的结果为8,直接输出8。
样例2计算的结果为 1234567891,输出后4 位,即7891。
样例3计算的结果为 1000000004,输出后4 位,即4。
数据范围
对于30%的数据,0≤表达式中加法运算符和乘法运算符的总数≤100;
对于80%的数据,0≤表达式中加法运算符和乘法运算符的总数≤1000;
对于100%的数据,0≤表达式中加法运算符和乘法运算符的总数≤100000。
这题它说保留后四位数字这个好办可以用%10000来解决,但是如果我们用平常写的时候是可以来判断一下,但是还是解决不了,所以可用栈
代码:
#include#include #include #include //c++自带栈在STL模板库里调用 using namespace std; string x; stack s; //算符栈 stack n; //数字栈 long long ans; int len; int main() { int i=0; getline(cin,x); len=x.length(); while (i<=len-1) { int t=0; bool f=false; while (x[i]>='0'&&x[i]<='9') //进数字的操作 { t=t*10+(x[i]-48); f=true; i++; } if (f) { n.push(t%10000); if (s.size()>=1&&s.top()=='*') //处理乘号 { int k=n.top(); s.pop(); n.pop(); //先把top的数出栈,再让top-1的数成为top,让他们相乘,再让top出栈,让乘积进栈 k*=n.top(); //这几行码核心内容就是n[--top]=n[top]*n[top+1]; n.pop(); n.push(k%10000); } } if (x[i]=='+'||x[i]=='*') { s.push(x[i]); i++; } } int size=n.size(); for (i=1;i<=size;i++) //计算和 { ans+=n.top(); n.pop(); ans%=10000; } printf("%lld",ans%10000); return 0; }
这样我们的代码都写好了,但是是不是有点复杂。我们换一个思路,我们最开始先读入一个数,将他作为累加和,后面因为运算优先级的问题,所以我们可以遇到一个乘号就分个段,然后我们就可以来看看怎样去算了。
_____ * _____ * _____ |_____| |_____| |_____|=ans 段1 段2 段3 现在需要求这个 |段|
现在需要的变量:
long long ans=0,temp,num; //ans是计算结果,temp用来累加每个段的值,num为每个计算数 char op; // *** 作符号
接下来输入初始temp段
cin>>temp;
不知道有多少个 *** 作数,所以用while输入
while(cin>>op>>num)
接下来我们就进行分段的 *** 作,然而在这个过程中进行计算。
if(op=='+'){ ans=(ans+temp)%10000; temp=num; } else{ temp=(temp*num)%10000; }
最后一段我们的ans无法将其累加进去,temp为最后一段,所以在最后需要加一下temp
ans=(ans+temp)%10000;
接下来ans就是答案。
代码:
#include#include #include #include #include #include #include #include #include
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)