题目

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例

输入：s = “()”
输出：true

输入：s = “()[]{}”
输出：true

输入：s = “(]”
输出：false

输入：s = “([)]”
输出：false

输入：s = “{[]}”
输出：true

解题思路

  • 首先，若想要给的字符串中的括号都是有效的，字符串 s 的长度必须为偶数，若为奇数一定不会匹配，返回false。
  • 遍历字符串 s，每当遇到左括号时，就将其对应的右括号压栈。当遇到右括号时，将其与栈顶元素进行比较(因为，若想一个括号能够匹配，其左括号一定是在右括号的左边才有可能匹配，而当遇见第一个右括号时，只有距离它最近的一个未匹配过的左括号才可能与它匹配(也就是比较它和最后一个入栈的右括号是否相同))。
  • 当遇见右括号且栈顶元素不同时，返回false。
  • 当遇到右括号时，栈是空的()，返回false。
  • 字符串 s 全部遍历完成后，若栈中还有剩余的元素，则说明未完全匹配，返回false。

代码

  1. import java.util.Scanner;
  2. import java.util.Stack;
  4. public class Valid_Parentheses_20 {
  5.     public static  boolean isValid(String s) {
  6.         Stack<Character> sk = new Stack<Character>();
  7.         int n = s.length();
  8.         if(n % 2 != 0){
  9.             return false;
  10.         }
  11.         for(int i=0;i<n;i++){
  12.             if(s.charAt(i)=='('){
  13.                 sk.push(')');
  14.             }else if(s.charAt(i) == '['){
  15.                 sk.push(']');
  16.             }else if(s.charAt(i)=='{'){
  17.                 sk.push('}');
  18.             }else if(sk.isEmpty() || sk.pop()!=s.charAt(i)) {
  19.                 return false;
  20.             }
  21.         }
  22.         //当全部匹配结束后，栈中仍有元素则返回false
  23.         if(!sk.isEmpty()){
  24.             return false;
  25.         }
  26.         return true;
  27.     }
  29.     public static void main(String[] argu){
  30.         Scanner scan = new Scanner(System.in);
  31.         String s = scan.next();
  32.         if (isValid(s)) {
  33.             System.out.println("true");
  34.         } else {
  35.             System.out.println("false");
  36.         }
  37.     }
  38. }