20. 有效的括号-E

20. 有效的括号-E

给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true
示例 2:

输入: "()[]{}"
输出: true
示例 3:

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

输入: "{[]}"
输出: true

• 分析

  leetcode上go不能导入外部的stack包，而go也没有内部的stack包  
  只能自己再实现一次;
  算法很简单，跟数据结构中的公式的语法分析一样
  

• code

package main

import (
	"fmt"
)
func main(){
	fmt.Println(ValidParentheses("()"))
	fmt.Println(ValidParentheses("()[]{}"))
	fmt.Println(ValidParentheses("(]"))
	fmt.Println(ValidParentheses("([)]"))
	fmt.Println(ValidParentheses("{[]}"))
}

type stack struct{
	v []interface{}
	len int
}
func (sk*stack)Pop(){
	if sk.len>0{
		sk.v=sk.v[:sk.len-1]
		sk.len-=1
	}
}
func (sk*stack)Push(in interface{}){
	sk.v=append(sk.v,in)
	sk.len+=1
}
func (sk*stack)Peek()interface{}{
	if sk.len==0{
		return nil
	}else{
		return sk.v[sk.len-1]
	}
}
func (sk*stack)Len()int{
	return sk.len
}


func ValidParentheses(in string)bool{
	if len(in)==0{
		return true
	}
	sk:=new(stack)
	for i:=len(in)-1;i>=0;i--{
		switch in[i] {
		case '(':
			check(sk,'(',')')
		case '{':
			check(sk,'{','}')
		case '[':
			check(sk,'[',']')
		default:
			sk.Push(in[i])
		}
	}
	if sk.Len()==0{
		return true
	}else{
		return false
	}
}
func check(sk *stack,a,b byte){
	if sk.Peek()==b{
		sk.Pop()
	}else{
		sk.Push(a)
	}
}
//---------stack--------------------------------------------------------------
type Stack struct{
	v []interface{}
	len int
}
func (sk*Stack)Pop(){
	if sk.len>0{
		sk.v=sk.v[:sk.len-1]
		sk.len-=1
	}
}
func (sk*Stack)Push(in interface{}){
	sk.v=append(sk.v,in)
	sk.len+=1
}
func (sk*Stack)Peek()interface{}{
	if sk.len==0{
		return nil
	}else{
		return sk.v[sk.len-1]
	}
}
func (sk*Stack)Len()int{
	return sk.len
}
func New()*Stack{
	return new(Stack)
}