今天所做的習題是LeetCode20，Valid Parentheses，有很大的收獲。

第一個想到的就是利用棧先從左到右遍歷字符串，找到所有的左部放到棧中，再從右到左遍歷字符串，找到所有的右部放到棧中，之后開始進行匹配發現不匹配立刻返回FALSE到一方空了之后如果另一方也空了就返回TRUE否則返回FALSE后來發現這種思路是不對的，因為：([[]()])這個原本是對的，但采用此方法會判斷為FALSE應該從左到右遍歷字符串如果是左部則放進棧中，如果是右部則判斷與棧頂元素相配，如果相配則棧頂元素被彈出棧，否則直接返回 FALSE遍歷全部字符之后，如果棧為非空也返回FALSE最后返回TRUE

代碼如下：

public boolean isValid(String s) {		Stack<Character> stack=new Stack<Character>();		for(int i=0;i<s.length();i++){			char ch=s.charAt(i);			switch (ch) {			case '(':			case '[':			case '{':				stack.push(ch);				break;			case ')':				if((stack.isEmpty())||stack.peek()!='(')					return false;				else					stack.pop();				break;			case ']':				if((stack.isEmpty())||stack.peek()!='[')					return false;				else					stack.pop();				break;			case '}':				if((stack.isEmpty())||stack.peek()!='}')					return false;				else					stack.pop();				break;			default:				break;			}		}		if(!stack.isEmpty())			return false;		return true;	}這是一種最基本的思路，也很容易理解。在編寫的時候需要注意兩個問題，一個是在遇到右部的時候需要判斷棧是否已經為空了，另一個是在結束的時候需要判斷棧是否仍然為非空（即其中仍然有左部）
查閱后發現這道題有好幾個很巧妙的方法
1.
/**	 * 這個方法超棒	 * 棧中放的只有當前需要出現的右部	 * 當出現一個左部的時候，就將應該出現的右部放入棧中	 * 當出現右部時和棧頂元素比較，如果不相同則返回FALSE	 * 最后棧為非空時也會返回FALSE	 * 都沒有問題的時候會返回TRUE**/	public boolean isValid(String s) {		Stack<Character> stack = new Stack<Character>();		for (char c : s.toCharArray()) {			if (c == '(')				stack.push(')');			else if (c == '{')				stack.push('}');			else if (c == '[')				stack.push(']');			else if (stack.isEmpty() || stack.pop() != c)				return false;		}		return stack.isEmpty();	}這個思路在調試完才看明白。它采取的思路就是不再當遇見右部的時候分3個情況判斷棧頂，而是直接把應該出現元素放在棧頂。出現右部的時候比較這個右部和pop出的棧頂元素是否相同。
這一個增加棧頂元素的動作減少了3個case判斷塊
2.
	public boolean isValid(String s) {        Stack<Integer> p = new Stack<>();        for(int i = 0; i < s.length(); i++) {            //第i個字符是左部還是右部，如果是左部則q % 2 == 0，否則q % 2 == 1            int q = "(){}[]".indexOf(s.substring(i, i + 1));            if(q % 2 == 1) {                if(p.isEmpty() || p.pop() != q - 1) return false;            } else p.push(q);        }        return p.isEmpty();    }這種方法不是很容易理解。
思路是這樣的：用substring來獲取每一個字符變為單字符的字符串，找到這個單字符串在"(){}[]"中的位置，如果在0,2,4，即q%2==0時說明為左部，直接進棧，否則說明為右部。
當為右部的時候首先判斷棧是否為空
之后再判斷棧頂元素是否為左部，根據q來判斷，即符號出現的位置。如果是對應的左部的話則正好應該為前一個位置，最后完成判斷。
總結：這兩種方法，一種是直接給出應該出現的右部。另一種是在出現右部的時候判斷是否為對應的左部。分別直接從符號本身出發和從符號的位置序號出發。
都明顯要比我用的方法更聰明。