[HackerRank]Java的堆疊(Java Stack)

題目描述

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

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

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

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

原題網址

輸入格式

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

輸出格式

判斷每一行輸入的字串資料，字串是「平衡的」，輸出「true」，否則輸出「false」。

範例輸入

範例輸出

解題概念

利用堆疊結構，並將字元區分為左括號和右括號。從字串最前端開始，若讀取到左括號，將左括號放入堆疊中，若讀取到右括號，則從堆疊中拿出上次放入的左括號，若拿出的左括號不是右括號對應的左括號，表示此字串「不平衡」。直到讀取到字串結尾，若堆疊中沒有任何剩餘的左括號，表示此字串「平衡」。

參考答案

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();
    }
}