java.util包中提供了stack這個類,可以利用堆棧解決很多問題,比如經典的括號匹配問題
先看看stack這個類
方法
例題:
描述 現在,有一行括號序列,請你檢查這行括號是否配對。 輸入 第一行輸入一個數N(N 0-100),表示有N組測試數據。後面的N行輸入多組輸入數據,每組輸入數據都是一個字符串S(S的長度小於10000,且S不是空串),測試數據組數少於5組。數據保證S中只含有"[","]","(",")"四種字符 輸出 每組輸入數據的輸出占一行,如果該字符串中所含的括號是配對的,則輸出Yes,如果不配對則輸出No 樣例輸入 3 [(]) (]) ([[]()]) 樣例輸出 No No Yes
思路:
當匹配到左括號則壓棧
匹配到右括號,則和棧頂元素比較,匹配一對則出棧,否則返回No,結束判斷
棧空還沒匹配完,也返回No,結束判斷
package com.day1;
import java.util.Scanner;
import java.util.Stack;
public class Main {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int n = input.nextInt();
String[] arr = new String[n];
for (int i = 0; i < arr.length; i++) {
arr[i] = input.next();
}
for (String string : arr) {
System.out.println(isMatch(string));
}
}
private static String isMatch(String str){
Stack stack = new Stack<>();//建立棧
/**
* 對字符串逐個掃描
* 遇到左括號入棧,遇到右括號則判斷
*/
for (int i = 0; i < str.length(); i++) {
if (str.charAt(i)!=')' && str.charAt(i)!=']') {
stack.push(str.charAt(i));
}else {
///棧空或者不匹配,則返回No
if (stack.empty() || !isBracketMatch(stack.peek(), str.charAt(i))) {
return "No";
}else {
stack.pop();
}
}
}
return "Yes";
}
/**
* 判斷兩個括號是否匹配
* @param c1
* @param c2
* @return
*/
private static boolean isBracketMatch(Character c1,Character c2){
if (c1 == '(' && c2 == ')') {
return true;
}
if (c1 =='[' && c2 ==']') {
return true;
}
return false;
}
}