public class BalanceChecker
1: import java.util.ArrayDeque;
2: import java.util.Deque;
3: import java.util.Scanner;
5: /**
6: * A class that checks whether the parentheses, brackets, and braces
7: * in a string occur in left/right pairs.
8: *
9: * @author Frank M. Carrano
10: * @author Timothy M. Henry
11: * @author Mark Young
12: * @version 4.1
13: */
14: public class BalanceChecker {
16: private static final Scanner KBD = new Scanner(System.in);
18: /**
19: * Decides whether the parentheses, brackets, and braces in a string occur
20: * in left/right pairs. Prints a running commentary on what it's doing.
22: * @param expression A string to be checked.
23: * @return True if the delimiters are paired correctly.
24: */
25: public static boolean checkBalance(String expression) {
26: // create the container
27: Deque<Character> openDelimiterStack
28: = new ArrayDeque<>();
30: // initialize some variables
31: int characterCount = expression.length();
32: boolean isBalanced = true;
33: int index = 0;
34: char nextCharacter;
36: // report what you're doing
37: System.out.println();
38: System.out.println("Checking balance on " + expression);
40: // run thru expression character by character
41: while (isBalanced && (index < characterCount)) {
42: // process one character
43: nextCharacter = expression.charAt(index);
44: switch (nextCharacter) {
45: case '(':
46: case '[':
47: case '{':
48: // opening bracket
49: System.out.println("... pushing " + nextCharacter);
50: openDelimiterStack.push(nextCharacter);
51: break;
52: case ')':
53: case ']':
54: case '}':
55: // closing bracket
56: System.out.println("... matching " + nextCharacter);
57: if (openDelimiterStack.isEmpty()) {
58: System.out.println("... EMPTY STACK!");
59: isBalanced = false;
60: } else {
61: char openDelimiter = openDelimiterStack.pop();
62: System.out.println("... popping " + openDelimiter);
63: isBalanced = isPaired(openDelimiter, nextCharacter);
64: } // end if
65: break;
67: default:
68: // non-bracket characters
69: break;
70: } // end switch
71: index++;
72: } // end while
74: // report result
75: if (!openDelimiterStack.isEmpty()) {
76: // show remaining (unmatched) brackets
77: System.out.print("... stack still contains ");
78: while (!openDelimiterStack.isEmpty()) {
79: System.out.print(openDelimiterStack.pop());
80: }
81: System.out.println();
82: isBalanced = false;
83: }
85: return isBalanced;
86: } // end checkBalance
88: /**
89: * Check whether the given characters, open and close, form a pair of
90: * parentheses, brackets, or braces.
91: *
92: * @param open what should be the opening bracket
93: * @param close what should be the closing bracket
94: * @return true if open and close form a matching open-close pair of
95: * brackets.
96: */
97: private static boolean isPaired(char open, char close) {
98: return (open == '(' && close == ')') ||
99: (open == '[' && close == ']') ||
100: (open == '{' && close == '}');
101: } // end isPaired
103: /**
104: * A driver that demonstrates the class BalanceChecker.
105: *
106: * @author Frank M. Carrano
107: * @author Timothy M. Henry
108: * @version 4.1
109: * @param args ignored
110: */
111: public static void main(String[] args) {
112: // test the balance of various expressions
113: testBalance("a {b [c (d + e)/2 - f] + 1}");
114: testBalance("[a {b / (c - d) + e/(f + g)} - h]");
115: testBalance("{a [b + (c + 2)/d ] + e) + f }");
116: testBalance("[a {b + [c (d+e) - f ] + g}");
117: testBalance("(a + b) - c * d + (a / d))");
119: System.out.println("\n\nDone.");
120: } // end main
122: /**
123: * Test the balance of an expression.
124: *
125: * @param expression the expression to check.
126: */
127: public static void testBalance(String expression) {
128: boolean isBalanced = BalanceChecker.checkBalance(expression);
129: if (isBalanced)
130: System.out.println(expression + " is balanced");
131: else
132: System.out.println(expression + " is not balanced");
133: pause();
134: } // end testBalance
136: /**
137: * Prompt user and wait for them to press enter key.
138: */
139: private static void pause() {
140: System.out.println();
141: System.out.print("...press enter...");
142: KBD.nextLine();
143: System.out.println();
144: }
146: } // end BalanceChecker
148: /*
150: Checking balance on a {b [c (d + e)/2 - f] + 1}
151: ... pushing {
152: ... pushing [
153: ... pushing (
154: ... matching )
155: ... popping (
156: ... matching ]
157: ... popping [
158: ... matching }
159: ... popping {
160: a {b [c (d + e)/2 - f] + 1} is balanced
162: ...press enter...
165: Checking balance on [a {b / (c - d) + e/(f + g)} - h]
166: ... pushing [
167: ... pushing {
168: ... pushing (
169: ... matching )
170: ... popping (
171: ... pushing (
172: ... matching )
173: ... popping (
174: ... matching }
175: ... popping {
176: ... matching ]
177: ... popping [
178: [a {b / (c - d) + e/(f + g)} - h] is balanced
180: ...press enter...
183: Checking balance on {a [b + (c + 2)/d ] + e) + f }
184: ... pushing {
185: ... pushing [
186: ... pushing (
187: ... matching )
188: ... popping (
189: ... matching ]
190: ... popping [
191: ... matching )
192: ... popping {
193: {a [b + (c + 2)/d ] + e) + f } is not balanced
195: ...press enter...
198: Checking balance on [a {b + [c (d+e) - f ] + g}
199: ... pushing [
200: ... pushing {
201: ... pushing [
202: ... pushing (
203: ... matching )
204: ... popping (
205: ... matching ]
206: ... popping [
207: ... matching }
208: ... popping {
209: ... stack still contains [
210: [a {b + [c (d+e) - f ] + g} is not balanced
212: ...press enter...
215: Checking balance on (a + b) - c * d + (a / d))
216: ... pushing (
217: ... matching )
218: ... popping (
219: ... pushing (
220: ... matching )
221: ... popping (
222: ... matching )
223: ... EMPTY STACK!
224: (a + b) - c * d + (a / d)) is not balanced
226: ...press enter...
230: Done.
231: */