数据结构和算法——栈的面试算法

判断括号字符串是否合法？

我们的表达式中常常有一些括号包裹，编程语言语法检查的时候会判断括号是否匹配正确，常用的就是用栈结构。

"[[()]]" //合法
"{[)}" //不合法

算法思路：

1.遍历字符串，如果是左括号，就压入栈中，如果是右括号，就判断
2.判断的方法，首先看栈是否为空，如果为空，则说明字符串非法。再看看Pop()出来的元素是否与之配对，不配对就是非法，如果配对就进行下一循环。
3.字符串遍历完后，如果栈还是不为空，则说明字符串非法

func main(){
    str := "[[]"
    res := checkStr(str)
    fmt.Println(res)
}
func checkStr(str string) bool{
    stack := util.NewStack()
    charMap := map[string]string{")":"(", "]":"[", "}":"{"} //先定义配对的map,右括号为键
    str2 := []rune(str)
    for i:=0; i< len(str2); i++{
        char := string(str2[i])
        if value,ok := charMap[char]; !ok{ //如果是左括号，压入栈
            stack.Push(char)
        }else if stack.Len == 0 || (stack.Pop() != value){ //如果是右括号，判断弹出的字符是否与之匹配
            return false
        }
    }
    if stack.Len == 0 {
        return true
    }else{
        return false
    }
}

go使用切片来实现简单stack

//使用切片来实现栈
type Stack struct{
    Len int
    s []interface{}
}
func NewStack() *Stack{
    return &Stack{0,make([]interface{},0)}
}
func (stack *Stack)Pop() interface{}{
    if stack.Len == 0{
        return nil
    }else{
        res := stack.s[stack.Len-1] //获取栈顶元素
        stack.s = stack.s[:stack.Len-1] //删除栈顶元素
        stack.Len--
        return res
    }
}
func (stack *Stack)Push(data interface{}){
    defer func() {
        stack.Len++
    }()
    stack.s = append(stack.s, data)
}
func (stack *Stack)Print(){
    fmt.Println(stack.s)
}

本作品采用《CC 协议》，转载必须注明作者和本文链接