1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Quick question about stacks

  1. Feb 22, 2013 #1

    Zondrina

    User Avatar
    Homework Helper

    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
        public StackADT(int capacity){
            isBoundedCapacity = true;
            boundedCapacity = Math.abs(capacity);
            Operators = new ArrayList<T>(boundedCapacity);
        }
       
        //Used to create an UNBOUNDED capacity stack
        public StackADT(){
            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++;
            Operators.add(item);
        }
    Matching brackets code ( Located in another class ):

    Code (Text):
        public void validateMatchingBrackets() throws MissmatchedBracketsException  {
            StackADT<Character> operationStack = new StackADT<Character>();  //Empty unbounded stack

            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. jcsd
  3. Feb 22, 2013 #2

    mfb

    User Avatar
    2016 Award

    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 ")".
     
  4. Feb 22, 2013 #3

    Zondrina

    User Avatar
    Homework Helper

    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 {
           
            StackADT<Character> operationStack = new StackADT<Character>();  //Empty unbounded stack

            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?
     
  5. Feb 22, 2013 #4

    mfb

    User Avatar
    2016 Award

    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.
     
  6. Feb 22, 2013 #5

    Zondrina

    User Avatar
    Homework Helper

    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 {
           
            StackADT<Character> operationStack = new StackADT<Character>();  //Empty unbounded stack

            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 :)
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Quick question about stacks
Loading...