CompetitiveProgramming/codeforces/100920/D.cpp at master · phonglnDEV/CompetitiveProgramming · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <bits/stdc++.h>
#define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; ++i)
#define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; --i)
#define REP(i,a) for(int i=0,_a=(a); i < _a; ++i)

#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define PR(A,n)  { cout << #A << " = "; FOR(_,1,n) cout << A[_] << ' '; cout << endl; }
#define PR0(A,n) { cout << #A << " = "; REP(_,n) cout << A[_] << ' '; cout << endl; }

#define sqr(x) ((x) * (x))
#define ll long long
#define SZ(x) ((int) (x).size())
using namespace std;

const int MN = 1000111;
char s[MN];
bool good[MN];
int match[MN], len;

int ATOM = 0;
int MUL = 1;
int ADD = 2;

int parse(int l, int r) {
    if (s[l] == '(' && match[l] == r) {
        int typ = parse(l+1, r-1);

        if (typ == ATOM) {
            good[l] = good[r] = true;
        }
        else if (typ == MUL) {
            if (l > 0 && s[l-1] == '/') {
                // cannot :(
            }
            else {
                good[l] = good[r] = true;
            }
        }
        else { // typ == ADD
            if (l > 0 && (s[l-1] == '*' || s[l-1] == '/' || s[l-1] == '-')) {
            }
            else if (r < len-1 && (s[r+1] == '*' || s[r+1] == '/')) {
            }
            else {
                good[l] = good[r] = true;
            }
        }

        if (good[l]) return typ;
        else return ATOM;
    }

    int i = l;
    int typ = ATOM;
    while (i <= r) {
        if (s[i] == 'x') {
            ++i;
        }
        else {
            assert(s[i] == '(');
            int t = parse(i, match[i]);
            typ = max(typ, t);
            i = match[i] + 1;
        }
        if (i > r) break;

        if (s[i] == '*' || s[i] == '/') typ = max(typ, MUL);
        if (s[i] == '+' || s[i] == '-') typ = max(typ, ADD);
        ++i;
    }

    return typ;
}

int main() {
    int ntest; scanf("%d\n", &ntest);
    while (ntest--) {
        scanf("%s\n", &s[0]);
        len = strlen(s);
        REP(i,len) good[i] = 0;

        stack<int> st;
        REP(i,len) {
            if (s[i] == '(') st.push(i);
            else if (s[i] == ')') {
                int j = st.top(); st.pop();
                match[i] = j;
                match[j] = i;
            }
        }
        parse(0, len-1);

        REP(i,len) if (!good[i]) putchar(s[i]); puts("");
    }
}