Balanced Brackets and Parentheses.
Difficulty (2/5).Many languages enclose expressions using brackets or parentheses of various kinds. For example, in Java, you might see expressions like the following:
s = new ArrayList<>(); A[(i*2)+1] = ((x+2)*(y-2)); public int getValue() { return val; }Notice how in all of these cases there is a "balancing principle" that gives the brackets a hierarchical structure. The rules for this balancing are as follows:
- Each open bracket must have a corresponding close bracket of the same kind to the right. Thus getValue() is balanced, but getValue(} is not.
- A closing bracket must be the same kind as the nearest unclosed open bracket to the left. Thus, A[(i*2)+1] is balanced, but A[(i*2]) is not.
(), [], {}, <>Test your program on the following expressions:
BALANCED: (a+3)*(b+2) {a[1], b[2], c[3]} void alloc() { x = new ArrayList<>(b[3]); } <<<< ((( [[ { x } ]] ))) >>>> NOT BALANCED: A[1) = 34; (((( b ))) :) (:Hint: Use a stack data structure.
CS1 Deadline: 12/6/2013
Use: handin cs1113 extra6 BalancedBrackets.java