九章演算法 | Facebook面試題 : 迷你解析器

撰文 | JZ

專欄 | 九章演算法

題目描述

有一個以字元串形式給出的嵌套數組，編寫一個解析器使其反序列化。

數組的元素為整數或相同形式的數組。

注意：你可以認為這個字元串遵從如下規則：

• 字元串不為空
• 字元串不包含空格
• 字元串僅包含數字0-9，[，-，]，和逗號「,」。

樣例

樣例一

給定字元串s = 「234」，返回一個只包含一個整數234的NestedInteger對象。

樣例二

給定字元串s = 「[123,[456,[789]]]」，返回一個包含兩個元素的NestedInteger對象：

1. 一個整數123
2. 一個NestedInteger的List，其中包含兩個元素：
1. 一個整數456
2. 一個NestedInteger的List，其中包含一個元素：
3. 一個整數789

解題思路分析

這屬於一道中等難度的字元串處理問題，主要難點在於對於層次的邏輯思考，每一種情況都不能漏。

簡單分析一下，此題需要一層一層進行剖析，到達最內層後結束。對於這種層次題目很明顯適合兩種解法，一種是用Stack，一種是遞歸。；兩種解法只是代碼寫法上的區別，其實本質思想上並沒有差別（Stack可以認為就是模擬遞歸），所以參考程序只給出了一種用Stack的解法，遞歸類似。

深入分析：

1. 在字元串中如果遇到「[」符號，便需要新開一層（即需要壓棧）
2. 在字元串中如果遇到「]」符號，表示此層結束（即需要彈棧）。但是在一層結束時，因為上一層要包含彈出的這一層，所以需要將其加入到其上一層（彈棧後的棧頂）
3. 在字元串中如果遇到「,」時，只需要處理前面是數字的情況（因為前面是數組的情況在遇到「]」時便處理過了），即把數字加入到當前層（即棧頂層）即可。
4. 注意一個特殊情況：只包含一個數字（如樣例一）的情況，需要額外處理（因為其沒有任何符號）。

參考代碼

面試官角度分析

這道題不難於演算法，能做到不遺漏情況，各層邏輯清晰，即可得到hire。

LintCode相關練習題

Flatten-nested-list-iterator

推薦閱讀：