(LeetCode 面试经典 150 题) 20. 有效的括号 (栈)

思路：栈，时间复杂度0(n)。

C++版本：

class Solution {
public:bool isValid(string s) {stack<char> st;// 哨兵，解决越界问题st.push('#');bool flag=true;for(auto x:s){if(x=='('|| x=='{'|| x=='['){st.push(x);}else{if(x==')'){if(st.top()!='('){flag=false;break;}}else if(x=='}'){if(st.top()!='{'){flag=false;break;}}else{if(st.top()!='['){flag=false;break;}}st.pop();}}if(flag&&st.size()==1) return true;return false;}
};

JAVA版本：

class Solution {public boolean isValid(String s) {Deque<Character> st=new ArrayDeque<>();st.add('#');boolean flag=true;for(var x:s.toCharArray()){if(x=='('|| x=='{'|| x=='['){st.push(x);}else{if(x==')'){if(st.peek()!='('){flag=false;break;}}else if(x=='}'){if(st.peek()!='{'){flag=false;break;}}else{if(st.peek()!='['){flag=false;break;}}st.pop();}}System.out.println(st.size());if(flag==true&&st.size()==1) return true;return false;}
}

GO版本：

func isValid(s string) bool {st:=[]rune{}st=append(st,'#')flag:=truefor _,x:=range s {if x=='(' || x=='[' || x=='{' {st=append(st,x)}else{if x==')' {if st[len(st)-1]!='(' {flag=false;break}}else if x==']' {if st[len(st)-1]!='[' {flag=false;break}}else{if st[len(st)-1]!='{' {flag=false;break}}st=st[:len(st)-1]}}if flag==true && len(st)==1 {return true}return false
}