Stack中怎么判斷字符串是否合法

判斷字符串是否合法是這樣的：有一個(gè)字符串，它只包含大中小括號(hào)，那么符號(hào) ([)] 這樣是不合法的，合法的應(yīng)該是這樣: ([]) ，同樣 ([]){ 這樣的符號(hào)也是不合法的 基于以上的共識(shí)，咱們先考慮使用數(shù)組的方式，來分析一下。

1. 定義一個(gè)初始值，如果剛開始輸入的就是 ( 或者 { 或者 [ ，那么我們不能立刻判斷到它就是不合法的，因?yàn)樗枰却ヅ?，如果到最后還是沒有匹配上，那就是不合法的;如果剛開始輸入的是 ) 或者 } 或者 ] ，我們立刻就能知道這是不合法的。

2. 如果此時(shí)輸入了 ( 和 [ ，初始值應(yīng)該 ++ ，接下來輸入的是右邊的符號(hào)的話應(yīng)該是 ] 而不是 ) ，此時(shí)需要進(jìn)行判斷第三個(gè)輸入的字符是否匹配第二個(gè)，只有第二個(gè)也匹配之后才需要進(jìn)行匹配第一個(gè)字符。

3. 如果匹配成功，則初始值應(yīng)該 - - ，所有字符串匹配完畢之后，需要看初始值是否為最初賦予的值，如果是則說明所有符號(hào)都是合法的，否則說明還有符號(hào)沒有匹配上，則不合法 經(jīng)過這樣的分析之后，寫代碼應(yīng)該就比較好寫了，比如我們可以這樣實(shí)現(xiàn):

/**
 * 判斷字符串是否合法
 *      比如: "([)]" 不合法, "[()]" 合法
 */
public class IsValidString {
    public static void main(String[] args) {
        // 定義字符串的內(nèi)容
        String symbol="([]){";
        // 調(diào)用判斷方法
        boolean result=isValid(symbol);
        System.out.print(result);
    }
    public static  boolean isValid(String s){
        // 用來接收傳入的值
        char[] arr = s.toCharArray();
        // 定義一個(gè)數(shù)組,用來存放傳入的字符串,長(zhǎng)度為傳入的字符串的值
        char[] stack = new char[s.length()];
        // 定義 stackEnd 為 -1 是為了讓第一個(gè)元素能夠進(jìn)入數(shù)組,即 stackEnd++ 值為 0
        int stackEnd=-1,length=s.length();
        for(int i=0;i<length;i++){
            // 如果剛開始是左括號(hào),左中括號(hào)等符號(hào),則不能直接判斷為該符號(hào)不合法,而是放入數(shù)組,等待匹配
            if(arr[i]=='(' || arr[i]=='[' || arr[i]=='{'){
                stackEnd++;
                stack[stackEnd]=arr[i];
            }
            // 如果剛開始就是右括號(hào),右中括號(hào)等符號(hào),則不合法,直接返回 false
            else if((arr[i]==']' || arr[i]==')' || arr[i]=='}') && stackEnd==-1){
                return false;
            }
            else {
                // 分情況來進(jìn)行匹配
                if(arr[i]==')' && stack[stackEnd]=='('){
                    stackEnd--;
                }
                else if(arr[i]==']' && stack[stackEnd]=='['){
                    stackEnd--;
                }
                else if(arr[i]=='}' && stack[stackEnd]=='{'){
                    stackEnd--;
                }
                else{
                    // 如果都匹配不到,說明該符號(hào)不合法,則直接返回 false
                    return false;
                }
            }
        }
        if(stackEnd!=-1){
            // 如果最后結(jié)果不等于 -1 ,說明 stackEnd 中還有符號(hào)沒有被匹配到,則也是不合法
            return false;
        }
        else
            return true;
    }
}

可以明顯看到，使用數(shù)組的話，會(huì)有很多 if ， else ， else if ，阿粉怎么聞到了壞代碼的味道。

有沒有更巧妙的方法呢？看下面：

/**
 * 判斷字符串是否合法
 *      比如: "([)]" 不合法, "[()]" 合法
 */
public class IsValidString {
    public static void main(String[] args) {
        // 定義字符串的內(nèi)容
        String symbol="([]){";
        // 調(diào)用判斷方法
        boolean result=isValid(symbol);
        System.out.print(result);
    }
    public static boolean isValid(String s){
        // 定義一個(gè)空棧
        Stack<Character> stack=new Stack<>();
        // 定義 map ,用來存放匹配的符號(hào)
        Map<Character,Character> map=new HashMap<>();
        char[] arr=s.toCharArray();
        map.put(')','(');
        map.put(']','[');
        map.put('}','{');
        for (int i=0;i<arr.length;i++){
            // 如果 map 中不包含進(jìn)入的符號(hào),說明是左邊的符號(hào),直接入棧即可
            if (!map.containsKey(arr[i])){
                stack.push(arr[i]);
            }else {
                // 如果進(jìn)入的符號(hào)和棧頂?shù)脑夭黄ヅ?則說明符號(hào)不合法
                if (map.get(arr[i])!=stack.pop()){
                    return false;
                }
            }
        }
        // 最后判斷棧是否為空,如果為空,說明所有符號(hào)都已匹配完畢,全都合法
        // 如果棧不為空,說明還有符號(hào)沒有匹配到,則不合法
        if (stack.empty()){
            return true;
        }else {
            return false;
        }

    }
}