問(wèn)題：給定一個(gè)字符串所表示的括號(hào)序列，包含以下字符： '(', ')', '{', '}', '[' and ']'墓塌， 判定是否是有效的括號(hào)序列
如括號(hào)必須依照 "()" 順序表示， "()[]{}" 是有效的括號(hào)旨枯，但 "([)]"則是無(wú)效的括號(hào)漏麦。
思路： 括號(hào)最重要的是匹配游添，只要出現(xiàn)()[]{}，就可以抵消掉秉馏，否則就false耙旦，而且對(duì)于stack的第一個(gè)元素 不能是}])，其他的就可以push入棧萝究。
這里免都，我們用數(shù)組來(lái)模擬stack，string作為輸入源帆竹。
注意匹配的順序绕娘，不能是“)(”。
Python3
class Solution:
# @param {string} s A string
# @return {boolean} whether the string is a valid parentheses
def isValidParentheses(self, s):
# Write your code here
stack = []
for index in s:
if index == "(" or index == "{" or index == "[":
stack.append(index)
continue
length = len(stack)
if stack:
if index == ")" and stack[length - 1] == "(":
stack.pop()
continue
if index == "}" and stack[length - 1] == "{":
stack.pop()
continue
if index == "]" and stack[length - 1] == "[":
stack.pop()
continue
else:
return False
else:
if index == "}" or index == "]" or index == ")":
return False
if stack:
return False
else:
return True
這里栽连，我有遇到一個(gè)問(wèn)題险领，如何判斷一個(gè)數(shù)組為空。
stack == None 是行不通的秒紧。
親測(cè)以下均可：
a = []
if not bool(a):
if not a:
if len(a) == 0:
if a == []:
也就是說(shuō)绢陌，一個(gè)空的列表 == 0 == False
java
public class Solution {
/**
* @param s A string
* @return whether the string is a valid parentheses
*/
public boolean isValidParentheses(String s) {
// Write your code here
Stack<Character> stack = new Stack<Character>();
for (char bracket: s.toCharArray())
{
if (bracket == '(')
{
stack.push(')');
}
else if (bracket == '{')
{
stack.push('}');
}
else if (bracket == '[')
{
stack.push (']');
}
else if (stack.isEmpty() || bracket != stack.pop())
{
return false;
}
}
return stack.isEmpty();
}
}
在用java做的時(shí)候，我發(fā)現(xiàn)了一個(gè)好方法噩茄，就是如上思路下面，簡(jiǎn)潔可行。
也發(fā)現(xiàn)了幾個(gè)問(wèn)題：
- java中 “{” 和 ‘{’ 是不一樣的類(lèi)型：第一個(gè)是string 第二個(gè)是 char绩聘。
- java中有現(xiàn)成的stack沥割，c++也有耗啦，反而就是python沒(méi)有。但是他們建立順序棧的方式都差不多机杜，均用了數(shù)組帜讲。
下面就是相關(guān)的信息：
Java 數(shù)據(jù)結(jié)構(gòu)包括： 枚舉（Enumeration）位集合（BitSet）向量（Vector）棧（Stack）字典（Dictionary）哈希表（Hashtable）屬性（Properties）
Python3數(shù)據(jù)結(jié)構(gòu)包括：列表（棧，隊(duì)列）集合椒拗，字典似将，元組
