題目描述
有一個只由一些括號字元組成的字串,若要稱其為「平衡的」字串,必須符合以下條件:
1. 為空字串
2. 若A和B是平衡的,則AB也是平衡的。
3. 若A是平衡的,則(A)、{A}、[A]也是平衡的。
2. 若A和B是平衡的,則AB也是平衡的。
3. 若A是平衡的,則(A)、{A}、[A]也是平衡的。
「平衡的」字串,舉例:「{}()」、「[{()}]」、「({()})」。
「不平衡的」字串,舉例:「{}(」、「({)}」、「[[」、「}{」。
給定一個字串,判斷其是否「平衡」。
原題網址
輸入格式
將會從檔案輸入一行或是多行的資料,您必須讀取檔案資料至檔案結尾(EOF)。
輸出格式
判斷每一行輸入的字串資料,字串是「平衡的」,輸出「true」,否則輸出「false」。
範例輸入
{}()
({()})
{}(
[]
({()})
{}(
[]
範例輸出
true
true
false
true
true
false
true
解題概念
利用堆疊結構,並將字元區分為左括號和右括號。從字串最前端開始,若讀取到左括號,將左括號放入堆疊中,若讀取到右括號,則從堆疊中拿出上次放入的左括號,若拿出的左括號不是右括號對應的左括號,表示此字串「不平衡」。直到讀取到字串結尾,若堆疊中沒有任何剩餘的左括號,表示此字串「平衡」。
參考答案
import java.util.Scanner;
import java.util.Stack;
public class Solution {
public static void main(final String[] args) {
final Scanner sc = new Scanner(System.in);
while (sc.hasNext()) {
final String input = sc.nextLine();
System.out.println(isBalanced(input));
}
}
private static boolean isBalanced(final String s) {
final char[] tokens = s.toCharArray();
final Stack<Character> stack = new Stack<>();
for (final char token : tokens) {
switch (token) {
case '(':
case '[':
case '{':
stack.push(token);
break;
case ')':
case ']':
case '}':
if(stack.isEmpty()){
return false;
}
final char c = stack.pop();
switch (c) {
case '(':
if (token != ')') {
return false;
}
break;
case '[':
if (token != ']') {
return false;
}
break;
case '{':
if (token != '}') {
return false;
}
break;
default:
return false;
}
}
}
return stack.empty();
}
}