找尋某整數位於哪個區間之內

最近在開發的專案，有用到JDT AST Parser，
實作時碰到了一個問題，
這個問題可以獨立出來成為一個有趣的題目。

[問題描述]

假設有一段程式碼如下，
而我們想要知道某行位在哪個(最內層的)class裡面。 (假設所有的class名稱都不重複)
例如第7行在class C裡面，第11行在class A裡面。
(雖然第7行也同時位在class B與class A裡，但我們要找的是最內層的。)

// ......
class A {

    class B {

        class C {

        }

    }

}


class D {

}

這個問題等同於把每個class擺在一條正整數X軸上，
每個class的區間有起始與結束的值。
給一個正整數N，我們想找出N位在哪個區間裡。

A   B   C   C   B   A   D   D
2   4   6   8   10  12  15  17

在看參考答案之前，
大家可以先自己想一下這個問題應該怎麼解決。


[正式題目I/O]

(前情提要如上所述)
<input>
line 1: 有N個class
line 2~N+1: 每行包括class的名稱、起始位置與結束位置
line N+2~eof: 每行包括要測試的行數X

<output>
X位在哪個區間之內，
若不位於任何區間則沒有任何輸出。
(每一行輸出之後都需要換行)

<範例input>

4
A 2 12
B 4 10
C 6 8
D 15 17
3
7
9
13
16

<範例output>

A
C
B

D

這邊我提供一個想法，
compiler在處理chain of function calls時，
是怎麼知道目前到第幾層了呢?
Ans: 「stack」

雖然stack是個很大的關鍵提示，
不過要實作起來並不會很簡單哦 XD
因為還是有一些case要考慮。

大概的想法是，
由上而下visit每個class，
每visit到一個class的開頭，就把他push到stack裡，
visit到class的結尾時，就把他pop掉。
由此一來，我們就可以保證stack頂端的class就是答案。

例如，visit到第3行時，此時stack頂端是A，
代表第3行就位在class A的範圍裡面。
visit到第7行時，此時stack頂端是C；
visit到第8行結束時，C被pop掉，
因此visit到第9行時，此時stack頂端是B，
代表第9行位於class B裡面。

以下是我用C++寫的參考解答。

#include <iostream>
#include <string>
#include <vector>
#include <stack>
using namespace std;

class Block {
public:
    string name;
    int start;
    int end;
    Block(string blockName, int start, int end) {
        this->name = blockName;
        this->start = start;
        this->end = end;
    }
};

class ScopeFinder {
private:
    vector<Block> blockList;
public:
    // 初始化blockList
    void init() {
        int numOfBlocks;
        string blockName;
        int start, end;
        cin >> numOfBlocks;
        while (numOfBlocks-- > 0) {
            cin >> blockName >> start >> end;
            blockList.push_back( Block(blockName,start,end) );
        }
    }
    // 輸入一個整數，找出該整數位在哪個區間之內
    string getBlockName(int num) {
        stack<Block> blockStack;
        // Iterate through blockList
        for (vector<Block>::iterator it=blockList.begin(); it!=blockList.end(); it++) {
            Block block = *it;
            // 忽略所有num之前的blocks (不重要，反正就算留著之後還是會被pop掉)
            if (num > block.end)
                continue;
            // num在某個block之前，可能有兩種case:
            // case1: "A*B B A" 或 "A*A B B" (*是num)
            // case2: "A A*B B" 或 "*A A" (case2的stack會是空的)
            if (num < block.start)
                return blockStack.empty() ? "" : blockStack.top().name;
            // 把目前iteration的block push進stack
            blockStack.push(block);
        }
        // iteration結束後，分成兩種case:
        // case1: "A*A" 或 "A B*B A" 或 "A A B*B" (意思其實都一樣，num位在最後一個block之間)
        // case2: "A A*" (case2的stack會是空的)
        return blockStack.empty() ? "" : blockStack.top().name;
    }
};

int main(int argc, char **argv) {
    ScopeFinder scopeFinder;
    scopeFinder.init();
    int num;
    while (cin >> num)
        cout << scopeFinder.getBlockName(num) << endl;
    return 0;
}

接著，來提一個進階版：

若X不位於任何class的scope之內，
則回傳最接近的class。
例如: X=13時回傳A，X=14時回傳D。

這邊我就不貼實作程式碼了，
大家可以自己想想看。

我這邊提供一個參考解法，
每次的iteration去記錄「在X之前、最靠近X且最外層的class」。
上面我貼的程式碼中，
有stack可能是空的情況，代表X不在任何class的scope之內。
在這些情況下，若還在iteration中，
就去比較X與記錄的class名稱以及目前iteration的class之間的距離；
若iteration已經結束了，就代表X位在所有class之下，
就直接回傳剛剛記錄的那個class即可。