借用arraystack的包完成

import "github.com/emirpasic/gods/stacks/arraystack"func isValid(s string) bool {stack := arraystack.New()for _, c := range s {if c == '(' {stack.Push(')')} else if c == '[' {stack.Push(']')} else if c == '{' {stack.Push('}')} else {if stack.Empty() {return false}tempC, _ := stack.Pop()if tempC != c {return false}}}return stack.Empty() }

接下來分析一下arraystack的實現(xiàn)

arraystack

用法

A stack based on a array list.

ArrayStack A stack based on a array list.Implements Stack, IteratorWithIndex, JSONSerializer and JSONDeserializer interfaces.package mainimport "github.com/emirpasic/gods/stacks/arraystack"func main() {stack := arraystack.New() // emptystack.Push(1) // 1stack.Push(2) // 1, 2stack.Values() // 2, 1 (LIFO order)_, _ = stack.Peek() // 2,true_, _ = stack.Pop() // 2, true_, _ = stack.Pop() // 1, true_, _ = stack.Pop() // nil, false (nothing to pop)stack.Push(1) // 1stack.Clear() // emptystack.Empty() // truestack.Size() // 0 }

stack的new，push和pop

// Push adds a value onto the top of the stack func (stack *Stack) Push(value interface{}) {stack.list.Add(value) }// Pop removes top element on stack and returns it, or nil if stack is empty. // Second return parameter is true, unless the stack was empty and there was nothing to pop. func (stack *Stack) Pop() (value interface{}, ok bool) {value, ok = stack.list.Get(stack.list.Size() - 1)stack.list.Remove(stack.list.Size() - 1)return }// String returns a string representation of container func (stack *Stack) String() string {str := "ArrayStack\n"values := []string{}for _, value := range stack.list.Values() {values = append(values, fmt.Sprintf("%v", value))}str += strings.Join(values, ", ")return str }

A stack based on a array list。

// Add appends a value at the end of the list func (list *List) Add(values ...interface{}) {list.growBy(len(values))for _, value := range values {list.elements[list.size] = valuelist.size++} }// Get returns the element at index. // Second return parameter is true if index is within bounds of the array and array is not empty, otherwise false. func (list *List) Get(index int) (interface{}, bool) {if !list.withinRange(index) {return nil, false}return list.elements[index], true }// Remove removes the element at the given index from the list. func (list *List) Remove(index int) {if !list.withinRange(index) {return}list.elements[index] = nil // cleanup referencecopy(list.elements[index:], list.elements[index+1:list.size]) // shift to the left by one (slow operation, need ways to optimize this)list.size--list.shrink() }

list

// Check that the index is within bounds of the list func (list *List) withinRange(index int) bool {return index >= 0 && index < list.size }func (list *List) resize(cap int) {newElements := make([]interface{}, cap, cap)copy(newElements, list.elements)list.elements = newElements }// Expand the array if necessary, i.e. capacity will be reached if we add n elements func (list *List) growBy(n int) {// When capacity is reached, grow by a factor of growthFactor and add number of elementscurrentCapacity := cap(list.elements)if list.size+n >= currentCapacity {newCapacity := int(growthFactor * float32(currentCapacity+n))list.resize(newCapacity)} }

總結(jié)

以上是生活随笔為你收集整理的20. 有效的括号 golang 堆栈的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。