链接

表达式求值

时间限制: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,直接输出8。
示例2
输入

1+1234567890*1

输出

7891

说明
计算的结果为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;

}