NOIP2013年普及组T2 表达式求值

【题目描述】

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

【输入描述】

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

【输出描述】

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

【输入样例1】

1+1*3+4

【输出样例1】

8

【输入样例2】

1+1234567890*1

【输出样例2】

7891

【输入样例3】

1+1000000003*1

【输出样例3】

4

【样例说明】

样例 1 计算的结果为 8，直接输出 8。

样例 2 计算的结果为 123456789，输出后 4位，即 7891。

样例 3 计算的结果为 1000000004，输出后 4 位，即 4。

【数据范围】

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

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

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

【分析】

1.题目中已经告知，输入的数据只包含0~9，“+”和“*”这几个字符，也就是不用考虑其他特殊字符了。而且表达式中没有括号，减少了不少难度。

2.加号和乘号有优先级问题，加号在前乘号在后

3.比较麻烦的一点是当答案长度多于 4 位时，请只输出最后 4 位，前导 0 不输出。这个操作直接 模10000即可。

4. 本题所有参与数据的数字都在0~$2^{31}-1$范围内，int的范围$2^{31}$,10位数，遇到乘法和加法会超范围，如果要做运算的话建议用long long

5.题目要求输出表达式的值，换句话说，题目的输入数据应该是保证有解的，不会出现 “1++1024”这样的表达式。

【解题思路1】

由于题目描述的过程是一个比较规律的过程，一个数字一个符号，直到最后读不到为止，那么实际上这个过程只有加法和乘法，我们可以每次遇到“+”的符号就把前面的累计求和，遇到“*”的符号就先乘再求和，加法用来加每次的乘积。这样功能就比较好划分了。

【参考代码1】

#include<cstdio>
#include<iostream>
using namespace std;

int sum=0,num,tmp;  //定义和，要操作的数，临时数 
int main()
{
	char op;  //定义操作符 
	scanf("%d",&num);  //首先读入一个数字，之后就是一个符号和一个数字的格式
	while(scanf("%c",&op) && op !='\n')   //没有遇到回车符就继续读入
	{
		scanf("%d",&tmp);  //读入第二个数，根据上面的符号进行下面的操作
		if(op == '+')
		{
			sum=(sum+num)%10000; //遇到加号就加上上一段的值， 
			num=tmp;  //将每次读入的数 赋值给num 
		}
		else //除了加号就是乘号 
		{
			num=(num*tmp)%10000;  //遇到乘号先把两个数乘起来 
		}
	} 
	sum=(sum+num)%10000; //因为我们每次都是先读取符号再操作上一步的值，所以要加上最后一步操作的值。 
	printf("%d",sum);
	
	return 0; 
}

---

返回目录：NOIP/CSP信息学奥赛复赛

---