題目描述

有一個只由一些括號字元組成的字串,若要稱其為「平衡的」字串,必須符合以下條件:



1. 為空字串
2. 若A和B是平衡的,則AB也是平衡的。
3. 若A是平衡的,則(A)、{A}、[A]也是平衡的。

「平衡的」字串,舉例:「{}()」、「[{()}]」、「({()})」。

「不平衡的」字串,舉例:「{}(」、「({)}」、「[[」、「}{」。

給定一個字串,判斷其是否「平衡」。

原題網址

https://www.hackerrank.com/challenges/java-stack

輸入格式

將會從檔案輸入一行或是多行的資料,您必須讀取檔案資料至檔案結尾(EOF)。

輸出格式

判斷每一行輸入的字串資料,字串是「平衡的」,輸出「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();
    }
}