leetcode 20 有效的括号

思路：

一个符号数组，["{", "[", "(", "}", "]", ")"]一个栈。

• 如果遇到左边的符号 0<= index < 3，则push栈
• 如果遇到右边的符号 index > 2
  1. 首先先判断栈空不空。如果是空，则return false;
  2. 拿栈顶元素比较，如果匹配则继续进行。如果不匹配则return false.
  3. 当字符串都判断完毕，则判断栈是否为空。如果不空，则return false.
  4. return true

实现：

swift 没有栈，需要用数组实现一个：

struct Stack<T> {
    // 对数组进行初始化
    fileprivate var array = [T]()
    
    public var isEmpty: Bool {
        return array.isEmpty
    }
    
    public var count: Int {
        return array.count
    }
    
    public mutating func push(_ element: T) {
        array.append(element)
    }
    
    public mutating func pop() -> T? {
        // 数组不为空时，返回并移除最后一个元素；空时，返回nil
        return array.popLast()
    }
    
    public var top: T? {
        //数组不为空时，返回最后一个元素；空时，返回nil
        return array.last
    }
}

// 判断符号是否成对匹配
func isValid(_ s: String) -> Bool {
    let charArray = Array(s)
    let symbelArray : [Character] = ["{", "[", "(", "}", "]", ")"]
    var stackStr = Stack<Character>()
    
    for item in charArray {
        if let index = symbelArray.index(of: item) {
            if index < 3 {
                // 如果是左括号，则进栈
                stackStr.push(item)
            }
            else {
                // 右括号
                if stackStr.isEmpty {
                    // 栈中没有元素，则不可能匹配
                    return false
                }
               
                // 如果栈中有元素，则拿栈顶元素匹配
                if let top = stackStr.top as? Character {
                    if symbelArray[index - 3] != top {
                        // 栈顶元素不匹配
                        return false
                    }
                    
                    // 栈顶元素匹配成功，则继续进行。
                    stackStr.pop()
                }
            }
        }
    }
    
    // 所有右边的括号都匹配了，如果栈还有元素，说明还有左括号没有匹配成功。
    return stackStr.isEmpty
}