LeetCode

385. Mini Parser

2017-01-10  本文已影响15人  小万叔叔
/**
 Given a nested list of integers represented as a string, implement a parser to deserialize it.
 
 Each element is either an integer, or a list -- whose elements may also be integers or other lists.
 
 Note: You may assume that the string is well-formed:
 
 String is non-empty.
 String does not contain white spaces.
 String contains only digits 0-9, [, - ,, ].
 Example 1:
 
 Given s = "324",
 
 You should return a NestedInteger object which contains a single integer 324.
 Example 2:
 
 Given s = "[123,[456,[789]]]",
 
 Return a NestedInteger object containing a nested list with 2 elements:
 
 1. An integer containing value 123.
 2. A nested list containing two elements:
 i.  An integer containing value 456.
 ii. A nested list with one element:
 a. An integer containing value 789.
*/

/**
 * // This is the interface that allows for creating nested lists.
 * // You should not implement it, or speculate about its implementation
 * class NestedInteger {
 *     // Return true if this NestedInteger holds a single integer, rather than a nested list.
 *     public func isInteger() -> Bool
 *
 *     // Return the single integer that this NestedInteger holds, if it holds a single integer
 *     // The result is undefined if this NestedInteger holds a nested list
 *     public func getInteger() -> Int
 *
 *     // Set this NestedInteger to hold a single integer.
 *     public func setInteger(value: Int)
 *
 *     // Set this NestedInteger to hold a nested list and adds a nested integer to it.
 *     public func add(elem: NestedInteger)
 *
 *     // Return the nested list that this NestedInteger holds, if it holds a nested list
 *     // The result is undefined if this NestedInteger holds a single integer
 *     public func getList() -> [NestedInteger]
 * }
 */

/*
Discuss: 
 1. 按照对[]显然要使用到栈的形式,读到 "[" 的时候创建数组, 读到 "]" 的时候返回上一级
 2. 读到 "," 的时候把元素插入进去.
 [123, [456, [78, 910], 123]]
 Array
    |   123 add 
    |   Array Push
          |   456 add 
          |   Array push
                |  78 add
                |  910 add
                |  <- pop
          |   123 add
          | <- pop
    |  <- pop
  Return
 
 需要一个栈结构来支持,新入栈的数组已经添加到上一个层级元素里面,新增加的栈元素依然是栈顶元素的一个element,所以不会有空间浪费。
*/

class NestedInteger {
    var currentValue: Int = Int.max
    var currentArray: [NestedInteger] = []
    
    public func isInteger() -> Bool {
        return currentArray.isEmpty
    }
    
    public func getInteger() -> Int {
        return currentValue
    }
    
    public func setInteger(_ value: Int) {
        currentValue = value
    }
    
    public func add(_ elem: NestedInteger) {
        currentArray.append(elem)
    }
    
    public func getList() -> [NestedInteger] {
        return currentArray
    } 
}
class Solution {
    //由于栈会被弹空,所以用一个值记录栈顶元素
    var stackTopCell: NestedInteger = NestedInteger()
    //用数组来模拟栈结构
    var stackArray: [NestedInteger] = []
    
    func stackNestedPush(element: NestedInteger) {
        if let peek = stackPeek() {
            peek.add(element)
        }
        else {
            stackTopCell = element
            
        }
        stackArray.append(element)
    }
    //
    func stackNestedPop() {
        //droplast 返回的是一个新的序列
        //removeLast 返回的是remove的值,修改的是当前序列
        stackTopCell = stackArray.removeLast()
    }
    
    func stackPeek() -> NestedInteger? {
        return stackArray.last
    }
    
    func deserialize(_ s: String) -> NestedInteger {
        
        var savedStr: String = ""  //记录数字字符串
        //string 存在两种操作
        //清理之前需要把保存的内容当如当前栈顶元素中去
        func clearStatus() {
            if (!savedStr.isEmpty){
                //内容不为空的情况,创建成员,保存到当前的栈顶元素当中
                let nestedCell = NestedInteger()
                nestedCell.setInteger(Int(savedStr)!)
                stackPeek()?.add(nestedCell)
                savedStr = ""
            }
        }
        
        func insertStatus(char: Character) {
            savedStr.append(char)
        }
        
        for char in s.characters {
            //如果为当前的内容是[, 则需要入栈,
            if char == "[" {
                let nestedCell = NestedInteger()
                stackNestedPush(element: nestedCell)
            }
            else if char == "," {
                clearStatus()
            }
            else if char == "]" {
                clearStatus()
                stackNestedPop()
            }
            else {
                if (Int(String(char)) != nil) || char == "-" {
                    insertStatus(char: char)
                }
            }
        }
        
        //如果最后一位不是出栈操作,则必定是一个纯数字
        if (!savedStr.isEmpty) {
            stackTopCell.setInteger(Int(savedStr)!)
        }
        return stackTopCell
    }
}

let sov = Solution()
sov.deserialize("[13, [12,[23,45]]]")
上一篇 下一篇

猜你喜欢

热点阅读