表达式求值_牛客博客

表达式求值

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 131072K，其他语言262144K

64bit IO Format: %lld

题目描述

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

输入描述:

输入仅有一行，为需要你计算的表达式，表达式中只包含数字、加法运算符“+”和乘法运算符“”，且没有括号。所有参与运算的数字均为 0 到
231-1 之间的整数。输入数据保证这一行只有0~9、+、这12种字符。输出描述:
输出只有一行，包含一个整数，表示这个表达式的值。注意：当答案长度多于4位时，请只输出最后4位，前导0不输出。

示例1
输入

1+1*3+4

输出

说明
计算的结果为8，直接输出8。
示例2
输入

1+1234567890*1

输出

说明
计算的结果为1234567891，输出后4位，即7891。
示例3
输入
复制
1+1000000003*1
输出
复制
4
说明
计算的结果为1000000004，输出后4位，即4。

思路：
题意不难，其实就是模拟加乘
我一开始想到用string，但打到一半才意识到，string每个都是一个字符，如果有两位以上的数就需要乘10加一块构成一个完整的数，太麻烦了，还不如直接读入整个数
我们发现奇数位是数字，偶数位是运算符
不如：1+2 * 3
奇数位1,3，5分别对应1,2，3
偶数位2,4分别对应 + *
首先stack w，需要一个栈
这样当读到奇数位时我们就读入a，a为int型，然后将a存入w
当为偶数位时我们读入b，b为char型，判断是+，就跳过继续
如果是乘号，我们就用乘号的前一位数字（即w.top() ）乘以后一位数字（读入一个a），得到的乘积存入w中
你会发现w中存的其实都是等待相加的数，因为我们把要乘的数都是处理后存入
最后将w的后四位加在一起，输出即可

代码：

#include<bits/stdc++.h>
using namespace std;

typedef  long long ll;

template<class T>inline void read(T &res)
{
char c;T flag=1;
while((c=getchar())<'0'||c>'9')if(c=='-')flag=-1;res=c-'0';
while((c=getchar())>='0'&&c<='9')res=res*10+c-'0';res*=flag;
}
#define mod 10000  
stack<int>w;
int a,b;
int sum=0;
int main()
{
    int a;
    char b;
    for(int i=1;;i++)
    {
        if(i&1)
        {
            cin>>a;
            w.push(a%mod);
        }
        else 
        {
            b=getchar();
            if(b!='+'&&b!='*')break;
                if(b=='*')
            {
                cin>>a;
                int q=w.top();
                w.pop();
                w.push((a%mod)*q%mod);
                i++;

            }
        }

    }
    while(!w.empty())
    {
        sum=(sum+w.top())%mod;
        w.pop();
    } 
    cout<<sum;
    return 0;

}