栈的应用（一）

栈的应用二  括号匹配的校验算法

算法思路

1.循环遍历字符串，读取每一个字符串，如果是左括号，则入栈

2.如果是右括号，则

   （1）如果栈空，说明右括号多余，false

   （2）如果栈非空，当前指针指向的字符和栈顶比较，如果不同，false；如果匹配，则出栈一次

   （3）如果循环结束后栈空，则返回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>();	        // 循环遍历字符串	        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;	                	}	                }	            }	        }	        // 循环结束后，栈空表示匹配完了，不空表示多余左括号	        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;	        }	    }}