數據結構——使用Java棧實現【括號匹配】

給定一個只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判斷字符串是否有效。java

有效字符串需知足：spa

1. 左括號必須用相同類型的右括號閉合。
2. 左括號必須以正確的順序閉合。

注意空字符串可被認爲是有效字符串。code

參考leetcode.com或leetcode-cn.com   第20題  有效的括號ip

地址：https://leetcode-cn.com/problems/valid-parentheses/description/leetcode

實現思路：字符串

{  [  (  )  ]  }get

一、依次遍歷字符串，只要是{  [  (  都把它壓入棧中it

二、若是是  )   ]    }    則前後判斷棧頂元素是否爲(  ，若是是則匹配成功，棧頂中  (  出棧，不是則返回false，不匹配io

三、判斷棧頂元素是否爲 ] ，若是是則匹配成功，棧頂中  [  出棧class

四、判斷棧頂元素是否爲 } ，若是是則匹配成功，棧頂中  {  出棧

五、判斷棧中是否還存在元素，若是不存在則表示以前已經所有匹配出棧，若是還存在則表示部分未匹配，判斷依據，stack.isEmpty()。

即 棧頂元素反映了在嵌套的層次關係中，最近的須要匹配的元素。

具體代碼實現：

package cn.itcats.stack;

import java.util.Stack;

public class Solution {
    public boolean isValid(String s) {
        //一、申明一個stack
        Stack<Character> stack = new Stack<Character>();
        //遍歷s String本質上是char[]
        for(int i = 0 ; i < s.length() ; i++){
            char c = s.charAt(i);
            if(c == '{' || c == '[' || c=='('){
                //若是是{ [ (   壓入棧中
                stack.push(c);
            }else{
                //  }  ]  )   進行比對
                if(stack.isEmpty()){
                    return false;
                }
                char topChar = stack.pop();
                if(c == ']' && topChar != '['){
                    return false;
                }
                if(c == '}' && topChar != '{'){
                    return false;
                }
                if(c == ')' && topChar != '('){
                    return false;
                }
            }
        }
        //若是循環結束,棧中沒有元素則表示所有匹配成功
        return stack.isEmpty();
    }
}