本题字符串中符号最大达到100000，那么只用递归的方式去求解表达式的话就需要100000层的递归（会超时）。那么可以回到后缀表达式的思路。
使用op栈保存符号，num栈保存数字。在计算过程中遇到*就进行计算后把计算的结果压栈。重复这个过程就可以了。
要注意：题目要求当答案长度大于4位时，输出后四位。而且题目中给的数据范围是2^31-1，在计算过程中也会超过数据类型范围。采用取余的性质在计算过程中取余。 
#include <bits/stdc++.h>

typedef long long ll;

using namespace std;

string s;
// ll string_to_num(int l, int r) {
//     ll ans = 0;
//     for (int i=l;i<=r;i++) {
//         ans = ans*10 + (s[i]-'0');
//     }
//     return ans;
// }

// ll calc(int l, int r) {
//     if (l>r) return 0;
//     int pos1 = -1, pos2 = -1;
//     for (int i=l;i<=r;i++) {
//         if (s[i]=='+') pos1 = i;
//         if (s[i]=='*') pos2 = i;
//     }
//     if (pos1==-1&&pos2==-1) {
//         return string_to_num(l, r);
//     }
//     if (pos1!=-1) return (calc(l, pos1-1)%10000+calc(pos1+1, r)%10000)%10000;
//     if (pos2!=-1) return (calc(l, pos2-1)%10000*calc(pos2+1, r)%10000)%10000;
//     return 0;
// }
const int p = 10000;
stack<int> num;
stack<char> op;
ll calc(int l, int r) {
    for (int i=l;i<=r;) {
        if (s[i]=='+'||s[i]=='*') {
            op.push(s[i]);
            i++;
        }
        else {
            int number = 0;
            int j = i;
            while (j<=r&&!(s[j]=='+'||s[j]=='*')) {
                number = number*10 + (s[j]-'0');
                j++;
                i++;
            }
            num.push(number);
            if (!op.empty() && op.top()=='*') {
                int ans = num.top();
                num.pop();
                ans = (ans%p * num.top()%p)%p;
                num.pop();
                num.push(ans);
                op.pop();
            }
        }
    }
    while (!op.empty()) {
        int ans = num.top();
        num.pop();
        ans = (ans%p + num.top()%p)%p;
        num.pop();
        num.push(ans);
        op.pop();
    }
    return num.top();
}

int main() {
    cin>>s;
    cout<<calc(0, s.size()-1)%10000;
    
    return 0;
}