UVa

UVa11234 POJ3367 HDU1805 Expressions

題目連結 UVa
題目連結 POJ
題目連結 HDU

  • 題意：給定一個用後綴表達式 $S$，請轉換成一個用隊列做出來會是一樣的表達式 $R$。
  • 題解：先用 dfs 建樹，再 bfs 並把過程記錄，最後依 bfs 反序輸出。
    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
    #pragma GCC optimize(2)
    #include <algorithm>
    #include <cmath>
    #include <cstring>
    #include <iostream>
    #include <stack>
    #include <queue>
    #include <map>
    #include <string>
    #include <vector>
    using namespace std;
    typedef pair<int, int> PII;
    typedef unsigned long long ULL;
    const int INF = 1e9;
    const int MXN = 1e5 + 5;
    const int MXV = 3e5 + 5;
    const ULL MOD = 10009;
    const ULL seed = 31;
    #define MP make_pair
    #define PB push_back
    #define F first
    #define S second
    #define FOR(i, L, R) for (int i = L; i != (int)R; ++i)
    #define FORD(i, L, R) for (int i = L; i != (int)R; --i)
    #define IOS                                                                    \
        cin.tie(NULL);                                                             \
        cout.tie(NULL);                                                            \
        ios_base::sync_with_stdio(false);
    string s;
    int si;
    vector<PII> child;

    int dfs()
    {
        stack<int> st;
        FOR(i,0,s.size())
        {
            if(islower(s[i]))
            {
                child[i].F = child[i].S = -1;
            }
            else
            {
                child[i].S = st.top();
                st.pop();
                child[i].F = st.top();
                st.pop();

            }
            st.push(i);
        }
        return st.top();
    }

    vector<int> q;
    void bfs(int x)
    {
        q.clear();
        q.push_back(x);
        FOR(i,0,q.size())
        {
            if(child[q[i]].F!=-1)
            {
                q.push_back(child[q[i]].F);
            }
            if(child[q[i]].S!=-1)
            {
                q.push_back(child[q[i]].S);
            }
        }
        FORD(i, q.size() - 1, 0 - 1) { cout << s[q[i]]; }
        cout << '\n';
    }

    int main()
    {
        int t;
        cin >> t;
        while (t--)
        {
            cin >> s;
            child.resize(s.size());
            si = 0;
            bfs(dfs());
        }
    }

如果你覺得這篇文章很棒，請你不吝點讚 (ﾟ∀ﾟ)

Recommended Posts