# Homework Help: Quick question about stacks

1. Feb 22, 2013

### Zondrina

1. The problem statement, all variables and given/known data

I'm trying to create a program which evaluates boolean expressions consisting of ()[]{}XYZ'!| 01TF. Right now I'm working on a bracket matching algorithm that will determine if the brackets match in a given expression.

The problem I'm getting is it's telling me I'm not throwing the proper exceptions for some reason even though I'm pretty sure I am inside my matching brackets code.

Here's my code which concerns this from my StackADT<T> class which I manually wrote. I used an ArrayList as my store. Just the bracket code, constructors, top, pop and push methods are below :

Constructors :

Code (Text):
//Used to create a BOUNDED capacity stack
isBoundedCapacity = true;
boundedCapacity = Math.abs(capacity);
Operators = new ArrayList<T>(boundedCapacity);
}

//Used to create an UNBOUNDED capacity stack
isBoundedCapacity = false;
boundedCapacity = StackProtocol.INITIAL_CAPACITY;
Operators = new ArrayList<T>(boundedCapacity);
}
Top, pop and push :

Code (Text):
@Override
public T top() throws StackUnderflowException{
if(isEmpty())
throw new StackUnderflowException();
return Operators.get(topOfStack);
}

@Override
public T pop() throws StackUnderflowException {
if(isEmpty())
throw new StackUnderflowException();
return Operators.remove(topOfStack--);
}

@Override
public void push(T item) throws BoundedCapacityOverFlowException {
if(size() == boundedCapacity) {
if(isBoundedCapacity())
throw new BoundedCapacityOverFlowException();
else {
boundedCapacity *= 2;
Operators.ensureCapacity(boundedCapacity); //Automatically increases the stack bound
}
}
topOfStack++;
}
Matching brackets code ( Located in another class ):

Code (Text):
public void validateMatchingBrackets() throws MissmatchedBracketsException  {

for(int i=0; i<booleanExpression.length(); i++) { //Loop over the expression
Character c = booleanExpression.charAt(i);

if((c == '(' || c == '{' || c == '[')) //If c is an open bracket
operationStack.push(c); //Push it onto the stack

else if(c == ')' || c == '}' || c == ']') { //Else if c is a close bracket
if(operationStack.isEmpty()) //First check if the stack is empty which means we have no match
throw new MissmatchedBracketsException(); //Throw the exception

if( (c == ')' && operationStack.top() == '(') //If the stack wasn't empty, find the match and pop
|| (c == ']' && operationStack.top() == '[')
|| (c == '}' && operationStack.top() == '{') )
operationStack.pop();
}
}

if(!operationStack.isEmpty())  //After the loop, if the stack is not empty, then throw an exception
throw new MissmatchedBracketsException();
}
If anyone could help me pinpoint what's wrong with my bracket code it would be very helpful :).

2. Feb 22, 2013

### Staff: Mentor

Who/what is telling you that in which way?

I think your bracket matching algorithm gets problems with strings like "{)}" - it just ignores the ")".

3. Feb 22, 2013

### Zondrina

No my code will not have problems with "{)}" I just tested it in my GUI.

Also, I switched my code up a bit :

Code (Text):
public void validateMatchingBrackets() throws MissmatchedBracketsException,
BoundedCapacityOverFlowException,
StackUnderflowException {

for(int i=0; i<booleanExpression.length(); i++) { //Loop over the expression
Character c = booleanExpression.charAt(i);

if((c == '(' || c == '{' || c == '['))
operationStack.push(c);

else if(c == ')' || c == '}' || c == ']') { //Else if c is a close bracket
if(operationStack.isEmpty()) //First check if the stack is empty which means we have no match
throw new MissmatchedBracketsException(); //Throw the exception

if((c == ')' && operationStack.top() == '(') //If the stack wasn't empty, find the match and pop
|| (c == ']' && operationStack.top() == '[')
|| (c == '}' && operationStack.top() == '{'))
operationStack.pop();
}
}

if(!operationStack.isEmpty())  //After the loop, if the stack is not empty, then throw an exception
throw new MissmatchedBracketsException();
}
Now my method will throw any over and underflows back to the method caller. My method caller is a method called evaluateExpression() :

Code (Text):
public void evaluateExpression() {
//Perform necessary validation
try{
validateVariablesAndOperators();
validateMatchingBrackets();
}
catch (BoundedCapacityOverFlowException e) {
e.getMessage();
}
catch (StackUnderflowException e) {
e.getMessage();
}
catch(InvalidVariableOrOperatorException e){
booleanExpression = e.toString();
results = new boolean[] {
false, false, false, false,
false, false, false, false
};
if(gui != null)
gui.updateGUI();
return;
}
catch(MissmatchedBracketsException e){
booleanExpression = e.toString();
results = new boolean[] {
false, false, false, false,
false, false, false, false
};

if(gui != null)
gui.updateGUI();
return;
}
Now for some reason, I get an error :

unreported exception assignment2_2402.BoundedCapacityOverFlowException; must be caught or declared to be thrown
t.validateMatchingBrackets();

Which makes no sense since I'm throwing these exceptions and dealing with them?

4. Feb 22, 2013

### Staff: Mentor

I don't see how this gives an error (as it should).
The first "{" is recognized and put on the stack. For ")", the program enters the else if case, but does not do anything there, as the stack is not empty and stack.top gives "{" and c is ")".

You should not get those error messages at all, unless you use a stack of fixed size and nest brackets too deep. Do you get them for all expressions? Did you check the state of the program just before it runs into errors? If you do not have a method to add breakpoints in your code to debug it, a lot of debug outputs should work as well.

5. Feb 22, 2013

### Zondrina

Here's a snip :

Code (Text):
for(int i=0; i<booleanExpression.length(); i++) { //Loop over the expression
Character c = booleanExpression.charAt(i);
if((c == '(' || c == '{' || c == '[')) {
try{operationStack.push(c);}
catch(BoundedCapacityOverFlowException e) {
booleanExpression = e.toString();
results = new boolean[] {
false, false, false, false,
false, false, false, false
};

if(gui != null)
gui.updateGUI();
return;
}
}
else if(c == ')' || c == '}' || c == ']') { //Else if c is a close bracket
try {
if(operationStack.isEmpty()) //First check if the stack is empty which means we have no match
throw new MissmatchedBracketsException(); //Throw the exception

if( ((c == ')') && (operationStack.top() == '(' )) //If the stack wasn't empty, find the match and pop
||  ((c == ']') && (operationStack.top() == '['))
||  ((c == '}') && (operationStack.top() == '{')) )
operationStack.pop();
}
I thought that for "{)}" :

i = 0 implies '{' is put into stack entry 0 by the if statement.

i = 1 implies we skip the if and go to the else if.

So in the else if, first we check if the stack is empty because if we found a close bracket before we found an open bracket ( aka the stack is empty ) then we just want to throw the exception right away.

The stack isn't empty, so it skips over to the next if which result in :

if( ((c == ')') && (operationStack.top() == '(' )) getting executed, but top returns '{' in this case. So nothing happens. Nothing will continue to happen as all the other ifs don''t happen.

So now... i = 2 implies ... oooh so the stack is going to wind up being cleared as we did nothing with the ')'. So to fix this ... I need to change my logic around. I see why I was wrong now. Instead of '==' I should really be saying '!=' and throw the exception if that does happen to occur.

Here's the completed code that wound up working according to the test server :

Code (Text):
public void validateVariablesAndOperators() throws InvalidVariableOrOperatorException {
String validTokens = "XYZ&|'()[]{} 01TF";
for(int i=0; i<booleanExpression.length(); i++){
char c = booleanExpression.charAt(i);

if(!validTokens.contains(""+c))
throw new InvalidVariableOrOperatorException();
}
}
public void validateMatchingBrackets() throws MissmatchedBracketsException {

for(int i=0; i<booleanExpression.length(); i++) { //Loop over the expression
Character c = booleanExpression.charAt(i);
if((c == '(' || c == '{' || c == '[')) {
try{operationStack.push(c);}
catch(BoundedCapacityOverFlowException e) {
booleanExpression = e.toString();
results = new boolean[] {
false, false, false, false,
false, false, false, false
};

if(gui != null)
gui.updateGUI();
return;
}
}
else if(c == ')' || c == '}' || c == ']') { //Else if c is a close bracket
try {
if(operationStack.isEmpty()) //First check if the stack is empty which means we have no match
throw new MissmatchedBracketsException(); //Throw the exception
Character tempPop = operationStack.pop();
if( ((c == ')') && (tempPop != '(' )) //If the stack wasn't empty, find the match and pop
||  ((c == ']') && (tempPop != '['))
||  ((c == '}') && (tempPop != '{')) )
throw new MissmatchedBracketsException();
}
catch(StackUnderflowException e){
booleanExpression = e.toString();
results = new boolean[] {
false, false, false, false,
false, false, false, false
};

if(gui != null)
gui.updateGUI();
return;
}
}
}
if(!operationStack.isEmpty())  //After the loop, if the stack is not empty, then throw an exception
throw new MissmatchedBracketsException();
}
Thanks a lot for your help :)