ZOJ 3826 Hierarchical Notation EON 解析器實現

ZOJ 3826 Hierarchical Notation 字符串模擬解析

模擬 Python 字典的 EON 格式解析：鍵值對用逗號分隔，大括號包裹，值可以是字符串或嵌套 EON。查詢用點號分隔層級。輸入冒號數 ≤ 10000，查詢 ≤ 1000。離線處理：先讀所有查詢鍵，解析 EON 時只記錄被查詢鍵的值位置。

核心解析邏輯

維護當前路徑緩衝區 buf，掃描 EON 字符串：
- {：進入嵌套，路徑加 .
- }：退出嵌套，路徑減兩層
- :：鍵結束，若當前路徑在查詢集中，記錄值起始位置
- ,：同層下一鍵，路徑減一層
- 其他字符：追加到路徑

關鍵代碼片段

void analyse(const char *s) {
    int j = 0;
    for (int i = 0; s[i]; i++) {
        if (s[i] == '{') {
            while (j > 0 && buf[j-1] != '|') buf[j--] = 0;
            if (j > 0 && buf[j-1] == '|') j--;
            buf[j] = 0;
            buf[j++] = '.';
            buf[j] = 0;
        } else if (s[i] == '}') {
            while (j > 0 && buf[j-1] != '.') buf[j--] = 0;
            buf[j--] = 0;
            while (j > 0 && buf[j-1] != '.') buf[j--] = 0;
            buf[j] = 0;
        } else if (s[i] == ':') {
            buf[j] = 0;
            if (MAP.count(string(buf))) 
                for (int k = 0; k < MAP[string(buf)].size(); k++)
                    ans[MAP[string(buf)][k]] = i + 1;
            buf[j++] = '|';
            buf[j] = 0;
        } else if (s[i] == ',') {
            while (buf[j-1] != '.') buf[j--] = 0;
        } else {
            buf[j++] = s[i];
            buf[j] = 0;
        }
    }
}

void print(int pos) {
    int rest = 0;
    while ((buff[pos] != ',' && buff[pos] != '}' || rest > 0) && buff[pos]) {
        if (buff[pos] == '{') rest++;
        if (buff[pos] == '}') rest--;
        putchar(buff[pos++]);
    }
    putchar('\n');
}

輸出處理

記錄值在原始字符串中的起始位置，輸出時從該位置打印到對應的 , 或 } (需處理嵌套大括號平衡)。未查到的鍵輸出 "Error!"。

複雜度與優化

• 時間：O(|EON| + Q × L)，L 為平均查詢鍵長度
• 空間：O(|EON| + Q × L) 存儲查詢映射
• 離線優化：只處理被查詢的鍵，避免構建完整 AST
• 內存限制緊張時採用字符數組而非 string 存儲