算法Sedgewick第四版-第1章基础-010一检查括号是否成对出现

 1 /******************************************************************************
 2  *  Compilation:  javac Parentheses.java
 3  *  Execution:    java Parentheses
 4  *  Dependencies: In.java Stack.java
 5  *
 6  *  Reads in a text file and checks to see if the parentheses are balanced.
 7  *
 8  *  %  java Parentheses
 9  *  [()]{}{[()()]()}
10  *  true
11  *
12  *  % java Parentheses
13  *  [(]) 
14  *  false
15  *
16  ******************************************************************************/
17 
18 public class Parentheses {
19     private static final char LEFT_PAREN     = '(';
20     private static final char RIGHT_PAREN    = ')';
21     private static final char LEFT_BRACE     = '{';
22     private static final char RIGHT_BRACE    = '}';
23     private static final char LEFT_BRACKET   = '[';
24     private static final char RIGHT_BRACKET  = ']';
25 
26     public static boolean isBalanced(String s) {
27         Stack<Character> stack = new Stack<Character>();
28         for (int i = 0; i < s.length(); i++) {
29             if (s.charAt(i) == LEFT_PAREN)   stack.push(LEFT_PAREN);
30             if (s.charAt(i) == LEFT_BRACE)   stack.push(LEFT_BRACE);
31             if (s.charAt(i) == LEFT_BRACKET) stack.push(LEFT_BRACKET);
32 
33             if (s.charAt(i) == RIGHT_PAREN) {
34                 if (stack.isEmpty())           return false;
35                 if (stack.pop() != LEFT_PAREN) return false;
36             }
37 
38             else if (s.charAt(i) == RIGHT_BRACE) {
39                 if (stack.isEmpty())           return false;
40                 if (stack.pop() != LEFT_BRACE) return false;
41             }
42 
43             else if (s.charAt(i) == RIGHT_BRACKET) {
44                 if (stack.isEmpty())             return false;
45                 if (stack.pop() != LEFT_BRACKET) return false;
46             }
47         }
48         return stack.isEmpty();
49     }
50 
51 
52     public static void main(String[] args) {
53         In in = new In();
54         String s = in.readAll().trim();
55         StdOut.println(isBalanced(s));
56     }
57 }

 1 /*************************************************************************
 2  * 
 3  * % java Ex_1_3_04
 4  * [()]{}{[()()]()}
 5  * true
 6  * 
 7  * % java Ex_1_3_04
 8  * [(])
 9  * false
10  * 
11  *************************************************************************/
12 
13 public class Ex_1_3_04
14 {
15     public static boolean isBalanced(String s)
16     {
17         Stack<Character> open = new Stack<Character>();
18         int n = s.length();
19         
20         for (int i = 0; i < n; i++)
21         {
22             char c = s.charAt(i);
23             
24             if (c == '(' || c == '[' || c == '{')
25                 open.push(c);
26             else if ((c == ')' && (open.isEmpty() || open.pop() != '(')) ||
27                      (c == ']' && (open.isEmpty() || open.pop() != '[')) ||
28                      (c == '}' && (open.isEmpty() || open.pop() != '{')))
29                 return false;
30         }
31         
32         return open.isEmpty();
33     }
34     
35     public static void main(String[] args)
36     {
37         String s = StdIn.readAll().trim();
38         
39         StdOut.println(isBalanced(s));
40     }
41 }