HDU 1022 Train Problem I - 棧模擬進出棧序列驗證

問題描述

有 n 輛火車 (n≤9)，給定進棧序列和出棧序列，判斷出棧序列是否合法。合法則輸出操作序列（in/out），否則輸出 No。

棧模擬算法

用棧模擬進出過程：

1. 遍歷進棧序列，依次 push 並記錄 "in"。
2. 每次 push 後，若棧頂等於出棧序列當前位置，則 pop 並記錄 "out"，推進出棧指針，重複直到不匹配或棧空。
3. 最終若出棧序列全匹配且棧空，則合法。

代碼實現（C++）

#include 
#include 
#include 
using namespace std;

int main() {
    int n;
    char in[10], out[10];
    while (cin >> n >> in >> out) {
        stack s;
        int j = 0, k = 0;
        char ops[20]; // 記錄操作
        for (int i = 0; i < n; i++) {
            s.push(in[i]);
            ops[k++] = 'i'; // in
            while (!s.empty() && j < n && s.top() == out[j]) {
                s.pop();
                ops[k++] = 'o'; // out
                j++;
            }
        }
        if (s.empty()) {
            cout << "Yes." << endl;
            for (int i = 0; i < k; i++) cout << (ops[i]=='i' ? "in" : "out") << endl;
            cout << "FINISH" << endl;
        } else {
            cout << "No." << endl << "FINISH" << endl;
        }
    }
    return 0;
}

關鍵點

• 操作記錄數組大小至少 2n。
• 輸出格式嚴格：每行一個操作，最後 FINISH。
• 多組測試，輸入直到 EOF。