【c++】NOIP 2013普及组 第二题:表达式求值

【c++】NOIP 2013普及组 第二题:表达式求值,第1张

【c++】NOIP 2013普及组 第二题:表达式求值

题目描述

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

输入

一行,一个表达式,表达式中只包含数字、加法运算符“+”和乘法运算符“*”,且没有括号,所有参与运算的数字均为 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
using namespace std;

int main()
{

	long long ans=0,temp,num;char op;
	cin>>temp;
	while(cin>>op>>num){
		if(op=='+'){
			ans=(ans+temp)%10000;
			temp=num;
		}
		else{
			temp=(temp*num)%10000;
		}
	}
	ans=(ans+temp)%10000;
	cout<

欢迎分享,转载请注明来源:内存溢出

原文地址: http://outofmemory.cn/zaji/3970217.html

(0)
打赏 微信扫一扫 微信扫一扫 支付宝扫一扫 支付宝扫一扫
上一篇 2022-10-21
下一篇 2022-10-21

发表评论

登录后才能评论

评论列表(0条)

保存