Ta sẽ xử lí từng toán tử:

• Gọi ~ans~ là kết quả cho đến trước toán tử này
• Gọi ~num~ là biến để lưu giá trị tích lũy của một chuỗi phép nhân (ban đầu ~num = 1~)
• Gọi ~last~ là giá trị của toán hạng trước đó (giữa toán tử đang xử lí và toán tử phía trước)
• Gọi ~sign~ là dấu của toán tử + hoặc - trước đó

Chia thành 2 trường hợp là toán tử cộng trừ hoặc toán tử nhân:

• Nếu toán tử đang xét là cộng hoặc trừ thì cộng/trừ ~ans~ cho ~num \times x~ với ~x~ là toán hạng trước đó, đặt lại ~num = 1~ lưu lại dấu này để biết ta sẽ cộng hay trừ toán hạng kế tiếp.
• Nếu toán tử đang xét là nhân thì đặt ~num = num \times x~ với ~x~ là toán hạng trước đó.

Code mẫu

#include <bits/stdc++.h>

using namespace std;
#define DB(X) { cout << #X << " = " << (X) << '\n'; }
#define DB1(A, _) { cout << #A << "[" << _ << "] = " << (A[_]) << '\n'; }
#define DB2(A, _, __) { cout << #A << "[" << _ << "][" << __ << "] = " << (A[_][__]) << '\n'; }
#define DB3(A, _, __, ___) { cout << #A << "[" << _ << "][" << __ << "][" << ___ << "] = " << (A[_][__][___]) << '\n'; }
#define PR(A, l, r) { cout << '\n'; for (int _ = l; _ <= r; ++_) DB1(A, _); cout << '\n';}
#define sz(x) ((int) (x).size())
#define all(v) (v).begin(), (v).end()
#define fi first
#define se second

using ll = long long;
using ld = long double;
using ii = pair<int, int>;
const int mod = 123456789;
int32_t main() {
#ifdef HynDuf
    freopen("A.inp", "r", stdin);
    freopen("A.out", "w", stdout);
#else
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
#endif
    int T;
    cin >> T;
    while (T--) {
        string s;
        cin >> s;
        int ans = 0;
        int ptr = 0;
        int lst = -1;
        int sign = 1;
        if (s[ptr] == '-') {
            ptr++;
            sign = -1;
        } else if (s[ptr] == '+') {
            ptr++;
        }
        while (ptr < sz(s)) {
            int num = 0;
            while (ptr < sz(s) && s[ptr] != '+' && s[ptr] != '-' && s[ptr] != '*') {
                num = (num * 10LL + (s[ptr] - '0')) % mod;
                ptr++;
            }
            if (lst != -1) {
                num = lst * 1LL * num % mod;
            }
            if (ptr == sz(s)) {
                ans = (1LL * ans + sign * 1LL * num + 1LL * mod) % mod;
            } else {
                if (s[ptr] == '*') {
                    lst = num;
                } else {
                    ans = (1LL * ans + sign * 1LL * num + 1LL * mod) % mod;
                    sign = (s[ptr] == '+' ? 1 : -1);
                    lst = -1;
                }
                ptr++;
            }

        }
        cout << ans << '\n';
    }
    return 0;
}
/* stuff you should look for
 * int overflow, array bounds
 * special cases (n=1?)
 * do smth instead of nothing and stay organized
 * WRITE STUFF DOWN
 * DON'T GET STUCK ON ONE APPROACH
 */