Saturday, November 23, 2013

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:
  1. Each open bracket must have a corresponding close bracket of the same kind to the right. Thus getValue() is balanced, but getValue(} is not.
  2. 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.
Write a program that will prompt the user for an input line and determine if it's brackets of various kinds are balanced. Support the following bracket types:
(), [], {}, <>
Test your program on the following expressions:
{a[1], b[2], c[3]}
void alloc() { x = new ArrayList<>(b[3]); }
<<<< ((( [[ { x } ]] ))) >>>>

A[1) = 34;
(((( b )))
:) (:
Hint: Use a stack data structure.

CS1 Deadline: 12/6/2013
Use: handin cs1113 extra6


  1. Dr. Cline the following expression would count as balanced or unbalanced?

    "<(expression>)" ?? There is a balanced number of each closing brackets type but not in the same order. Is it considered balanced or unbalanced?

  2. That's considered unbalanced. Also )( is considered unbalanced, whereas () is balanced.