实现
package stack
import "log"
type ArrayStack struct {
items []string // 存储栈元素的数组
n int // 栈的大小
count int // 栈中元素的个数
}
func NewArrayStack(n int) ArrayStack {
return ArrayStack{items: make([]string, n, n), n: n, count: 0}
}
// push 入栈
func (arrayStack *ArrayStack) push(item string) {
if arrayStack.count == arrayStack.n {
log.Println("ArrayStack is full")
return
}
arrayStack.items[arrayStack.count] = item
arrayStack.count++
}
// 出栈
func (arrayStack *ArrayStack) pop() string {
if arrayStack.count == 0 {
log.Println("ArrayStack if empty")
return ""
}
result := arrayStack.items[arrayStack.count-1]
arrayStack.count--
return result
}
// 查看栈顶元素
func (arrayStack *ArrayStack) getStackTop() string {
if arrayStack.count == 0 {
log.Println("ArrayStack if empty")
return ""
}
result := arrayStack.items[arrayStack.count-1]
return result
}
应用
栈的应用有很多,比如函数调用栈、表达式计算和括号匹配等等。
括号匹配
基本思路是准备一个栈用于存储左括号,我们遍历要判断是否满足括号匹配的字符串,中途如果遇到了左括号就将其入栈,如果遇到了右括号则将其与栈顶弹出元素相匹配,如果栈为空或者不匹配则表示这个字符串不满足括号匹配的原则。
show my code:
注意这里面用到栈正是上文中的顺序栈。
package stack
import (
"unicode/utf8"
)
type bracketItem struct {
side string
matchBracket string
}
var left = "left"
var right = "right"
var bracketMap = map[string]bracketItem{
"(": {side: left, matchBracket: ")"},
")": {side: right, matchBracket: "("},
"[": {side: left, matchBracket: "]"},
"]": {side: right, matchBracket: "["},
"{": {side: left, matchBracket: "}"},
"}": {side: right, matchBracket: "{"},
}
func BracketMatch(str string) bool {
stack := NewArrayStack(utf8.RuneCountInString(str))
for _, s := range str {
s2 := string(s)
// 不是括号则直接跳过
v, ok := bracketMap[s2]
if !ok {
continue
}
// 如果是括号则进一步判断是左括号还是右括号
if v.side == left {
stack.push(s2)
continue
}
// 栈顶元素与当前括号相匹配
if stack.getStackTop() != "" && stack.getStackTop() == v.matchBracket {
_ = stack.pop()
} else {
return false
}
}
if stack.count != 0 {
return false
}
return true
}
测试代码:
package stack
import (
"fmt"
"testing"
)
var bracketList = []string{
"{",
"aa{",
"{d{f",
"{}",
"{)",
"{()}",
"{asdfdas([{asdfdfad}])aaaaaaaa[]{([)}()}",
"{asdfdas([{asdfdfad}])aaaaaaaa[]{([{}])}()}",
}
func TestBracketMatch(t *testing.T) {
for _, bracketStr := range bracketList {
fmt.Println(BracketMatch(bracketStr))
}
}