棧的應(yīng)用二  括號匹配的校驗(yàn)算法

算法思路

1.循環(huán)遍歷字符串，讀取每一個字符串，如果是左括號，則入棧

2.如果是右括號，則

   （1）如果棧空，說明右括號多余，false

   （2）如果棧非空，當(dāng)前指針指向的字符和棧頂比較，如果不同，false；如果匹配，則出棧一次

   （3）如果循環(huán)結(jié)束后棧空，則返回true，反之返回false

import java.util.LinkedList;
public class BracketMatch {	    public static void main(String[] args) {	    	System.out.PRintln(match("{[]([])}"));	    }	    public static boolean match(String inputStr) {	        int len = inputStr.length();	        LinkedList<Character> stack = new LinkedList<Character>();	        // 循環(huán)遍歷字符串	        for (int i = 0; i < len; i++) {	            // 如果是左括號則入棧	            if (isLeftBracket(inputStr.charAt(i))) {	                stack.push(inputStr.charAt(i));	                // 如果是右括號	            } else if (isRightBracket(inputStr.charAt(i))) {	                // 棧空，則右括號沒有匹配的左括號，則返回false	                if (stack.isEmpty()) {	                    return false;	                    // 棧不空，則和棧頂比較	                } else {	                	if("{".equals(stack.peek().toString())&&"}".equals(String.valueOf(inputStr.charAt(i)))){	                			stack.pop();	                			continue;	                	}	                	if(stack.peek().toString().equals("[")&&"]".equals(String.valueOf(inputStr.charAt(i)))){	                			stack.pop();	                			continue;	                	}	                	if(stack.peek().toString().equals("(")&&")".equals(String.valueOf(inputStr.charAt(i)))){	                			stack.pop();	                			continue;	                	}	                }	            }	        }	        // 循環(huán)結(jié)束后，棧空表示匹配完了，不空表示多余左括號	        if (stack.isEmpty()) {	            return true;	        } else {	            return false;	        }	    }	    /**	     * 判斷字符是不是左括號	     * 	     * @param dc	     * @return	     */	    public static boolean isLeftBracket(char ch) {	        if (ch == '(' || ch == '[' || ch == '{') {	            return true;	        } else {	            return false;	        }	    }	    /**	     * 判斷字符是不是右括號	     * 	     * @param dc	     * @return	     */	    public static boolean isRightBracket(char ch) {	        if (ch == ')' || ch == ']' || ch == '}') {	            return true;	        } else {	            return false;	        }	    }}