算法1

栈+取模

C++ 代码

#include<cstdio>
#include<iostream>
#include<stack>
#include<string>
#include<cstring>

using namespace std;

typedef long long LL;

const int N = 1000010;

stack<LL> stk;

int k;

string s;

LL get()
{
    LL res = 0;
    while(s[k] >= '0' && s[k] <= '9') res *= 10, res += s[k] - '0', ++ k;
    return res;
}

int main()
{
    cin >> s;   
    while(k < s.size())
    {
        if(s[k] >= '0' && s[k] <= '9')
        {
            stk.push(get());
        }
        else if(s[k] == '+')
        {
            ++ k;
            stk.push(get());
        }
        else if(s[k] == '*')
        {
            ++ k;
            LL num = get();
            num = num * stk.top() % 10000ll;
            stk.pop();
            stk.push(num);
        }
    }
    LL res = 0;
    while(stk.size())
    {
        LL num = stk.top();
        res = (res + num) % 10000ll;
        stk.pop();
    }
    printf("%lld", res);
    return 0;
}