Utilizing Stacks

[waxen flame]

// TODO Choose the most appropriate data structure for the task and import it
import java.util.Stack;
// import java.util.Queue;

public class BalancedParenthesesChecker {

    public static boolean isBalanced(String expression) {

        boolean b = true; 

        Stack<Character> stack = new Stack<Character>(); 
        char top; 

      char[] expr =  expression.toCharArray(); 
        for(char c: expr){
            stack.push(c); 
            top = stack.peek(); 
            if(c == '}' || c == ']'|| c == ')'){
                stack.pop(); 
            }
            if(top == '{' || top == '[' || top == '('){
               return true; 
            }
        }
        return false; 
    }

    public static void main(String[] args) {
        // TODO Test your implementation
        String expression = "{(([a + b]) * c) - d}";
        System.out.println("Is the expression balanced? " + isBalanced(expression));
        expression = "([(a + b) * c)} - d";
        System.out.println("Is the expression balanced? " + isBalanced(expression));
    }
}

for referene here is my code. Right now, I am trying to do the balanced parentheses checker problem. I just learned stacks this week. I am unsure of how to get the logic correct for this problem entirely. The first one outputs that it is balanced, which is correct but also marks the second one as balanced which is incorrect. What should I keep in mind about the structure of stacks while writing this code to make the logic work?

[idle elbow]

⌛ This post has been reserved for your question.

Hey @waxen flame! Please use /close or the Close Post button above when your problem is solved. Please remember to follow the help guidelines. This post will be automatically closed after 300 minutes of inactivity.

TIP: Narrow down your issue to simple and precise questions to maximize the chance that others will reply in here.

[rancid gull]

Right now you are returning true as soon as an opening parenthesis is encountered. I will give you some pseudocode how this method should work.

boolean isBalanced(expression):
  char[] chars = expression.toCharArray();
  Stack<Character> myStack = new Stack<Character>();  //You might want to look into ArrayDeque. Stack is a legacy class. 
  for every character (c)  in chars: 
      if c is an opening parethesis: 
          push c onto the stack
      if c is a closing parenthesis: 
          if c does not match the opening parenthesis at the top of the stack:
              return false
          else
            pop the opening parenthesis from the stack
  if the stack is not empty after all characters have been processed return false, else return true. 

[waxen flame]

@rancid gull thank you for your response! here is my updated code on how i'm attempting the problem now

[idle elbow]

If you are finished with your post, please close it.
If you are not, please ignore this message.
Note that you will not be able to send further messages here after this post have been closed but you will be able to create new posts.

[waxen flame]

// TODO Choose the most appropriate data structure for the task and import it
import java.util.Stack;
// import java.util.Queue;

public class BalancedParenthesesChecker {


    public static boolean isBalanced(String expression) {

        Stack<Character> stack = new Stack<Character>(); 
        char top; 
        
        char[] arr = expression.toCharArray(); 
        for(char c : arr){
            if(c == '{' || c == '}' || c == '(' ||  c == ')' || c == '[' || c == ']'){
                stack.push(); 
                top = stack.peek(); 

                switch(c){
                    case '{' :
                    if(top == '}'){
                        stack.pop(); 
                    }
                    else{
                        continue; 
                    }
                    break; 
                    case '[' :
                    if(top == ']'){
                        stack.pop(); 
                    }
                    else{
                        continue; 
                    }
                    break;
                    case '(' :
                    if(top == ')'){
                        stack.pop(); 
                    }
                    else{
                        continue; 
                    }
                    break; 
                }

            }
        }
        return stack.isEmpty(); 
    }

    public static void main(String[] args) {
        // TODO Test your implementation
        String expression = "{(([a + b]) * c) - d}";
        System.out.println("Is the expression balanced? " + isBalanced(expression));
        expression = "([(a + b) * c)} - d";
        System.out.println("Is the expression balanced? " + isBalanced(expression));
    }
}

i figure using a switch might be better

now it return false for both

[austere panther]

gah ...... if all ur doing is counting openning and closing parenthesis, the proper data structure is an int!

.... u dont need more than that

[waxen flame]

my method is trying to check if the stack is empty

i want it to pop the parentheses once it finds a match

[rancid gull]

keep both cases separate. Only if its an opening parenthesis push it onto the stack. Currently you have all under the same if.

[austere panther]

move this into a helper method

            if(c == '{' || c == '}' || c == '(' ||  c == ')' || c == '[' || c == ']')

[waxen flame]

heres my current iteration

        Stack<Character> stack = new Stack<Character>(); 
        char top; 
        
        char[] arr = expression.toCharArray(); 
        for(char c : arr){
            if(c == '{' ||  c == '(' || c == '[' ){
                stack.push(c); 
                top = stack.peek(); 
            switch(c){
                case '}' :
                if(top == '(' || top == '['){
                    return false; 
                }
                else{
                    pop(); 
                }
                break; 
                case ')' :
                if(top == '[' || top == '{'){
                    return false; 
                }
                else{
                    pop(); 
                }
                break; 
                case ']' :
                if(top == '(' || top == '{'){
                    return false; 
                }
                else{
                    pop(); 
                }
            }
                 
        }
        return stack.isEmpty(); 
    }
    }```

[rancid gull]

You should have two separate conditions in your for loop:

 for(char c : arr){
    if(c == '{' || c == '(' ||  c == '[') {
      //Do something
    }
    if(c == '}' || c == ')' || c == ']') {
        //Do something
     }
}

[waxen flame]

i see

[rancid gull]

what should happen in both of these cases is explained in here

[waxen flame]

i get what you're saying but it's mostly that i'm trying to figure out how to properly use the stack

maybe i am overcomplicating it though

[rancid gull]

try one more time with the template I just gave you and then we'll see what confuses you.

[waxen flame]

sure sounds good

i will start from scratch

[austere panther]

dont teach ppl to use magic numbers!

 for(char c : arr){
    if(isOpeningParenthesis(c)) {
      //Do something
    }
    if(isClosingParenthesis(c) {
        //Do something
     }
}

[rancid gull]

right ... "magic numbers"

[waxen flame]

what is meant by this

[austere panther]

yes, do u know what magic numbers refers to?

[waxen flame]

no i do not

i am just learning data structures now as of last week

so i'm pretty green at this

[rancid gull]

"magic numbers" refers to values which intend is not clear from looking at them. For example this would be an opening bracket but it is not clear from looking at the code:
char c = (char) 40 //Would mean (

[austere panther]

its not ur fault but u should have been taight a lot of things before datastructures that u clearly havent

the problem isnt that u dont know
but that @rancid gull encourages u to not fix it

[waxen flame]

can you elaborate a bit more?

[austere panther]

magic numbers refers to using ANY litteral whose context is not immediately clear

if the method was named isCorrectlyNestedParenthesis for example, the reason why ur using those symbols is clear

but is balanced, tells u nothing so anybody who reads the code will go "why are these symbols here" "what do they represent"

[rancid gull]

you do realise that this is an exercise right.

[waxen flame]

idk i'm a first year bachelor's student

so i am not like super great at convention yet

[rancid gull]

you are good. Do you have your new iteration ?

[austere panther]

besides, u should never smash all code into a single method

[waxen flame]

i'm working on the second part of it

[rancid gull]

yeah and he will be taught that once he starts writing larger projects

[waxen flame]

haha i'm a girl

but yes

i hope so

[rancid gull]

sorry

[austere panther]

after its alrdy a habbit and becomes a big deal to unlearn, instead of when its easy and convenient?

[rancid gull]

there is nothing to unlearn here. The task is to implement this method. We are working on that.

[waxen flame]

        for(char c : arr){
            if(c == '{' || c == '[' || c == '('){
                stack.push(c); 
                top = stack.peek(); 
            }
            if(c == '}' || c == ')' || c == ']'){
                if(c == '}' && top == '{'){
                    
                }
            }
        }```

[rancid gull]

the only thing you have brought to the conversation so far is that the approach and structure of the exercise is flawed

[waxen flame]

here is the updated for loop i am working on

i think here it might be okay to use a switch case? So i am sure to only pop off the stack once i have a match

but i am unsure

actually

i moved my peek

[rancid gull]

1. You don't need a top variable that is updated every time you push something onto the stack. That's what peek is for.
2. Yea a switch is sensible in this context.

[waxen flame]

i moved peek to be in the second if statement

so i can see what is in the stack

[rancid gull]

you actually don't need the top variable at all. Use a switch to check what the corresponding opening parenthesis for the closing one would be. That you could store in a variable

[waxen flame]

fair

here is the code so far

i will think about how to implement the change you recommended

so far in this iteration it still return false both times :/

    public static boolean isBalanced(String expression) {

        Stack<Character> stack = new Stack<Character>(); 
        char top; 

        char[] arr = expression.toCharArray(); 

        for(char c : arr){
            if(c == '{' || c == '[' || c == '('){
                stack.push(c); 
            }
            if(c == '}' || c == ')' || c == ']'){
               top = stack.peek(); 
               switch(c){
                case '}' :
                  if(top == '[' || top == '('){
                    return false; 
                  }
                  else{
                    stack.pop(); 
                  }
                  break; 
                  case ')' :
                  if(top == '[' || top == '{'){
                    return false; 
                  }
                  else{
                    stack.pop(); 
                  }
                  break; 
                  case '[' :
                  if(top == '{' || top == '('){
                    return false; 
                  }
                  else{
                    stack.pop(); 
                  }
               }
                
            }
        }
        
        return stack.isEmpty(); ```

[waxen flame]

i will implement this

in the meantime

why might i still be getting false

for both

[rancid gull]

case '[' : That should probably be a closing bracket

[waxen flame]

ah you're right

ah! it works now

that was the only error i guess

[rancid gull]

yeah and now that it works. We can work on cleaning the code up

[waxen flame]

yeah.

i'd love to know how to make it a bit neater

[rancid gull]

you could start by using a switch to find the corresponding opening parenthesis

[waxen flame]

good idea

idk why but i thought that approach wouldve been too long

maybe i could write it like

[austere panther]

    public static boolean isBalanced(String expression) {
        if (expression == null || expression.isEmpty()) 
          return false;

        Stack<Character> stack = new Stack<Character>(); 
        for(char c : expression.toCharArray()){

            if(isOpenParenthesis(c)){
                stack.push(c); 

            } else if(isClosingParenthisis(c)){
                if ( isMatchingClosingParenthisis(c, stack.peek()) {
                  stack.pop();

                } else {
                  return false;
                }
            }
        }
        return stack.isEmpty();
    }

helper methods are ur friend

[waxen flame]

isOpenParenthesis? is this a method you created for this

i have taken an objects class

but i am

rusty

i think

[rancid gull]

It won't work you are not poping from the stack

[austere panther]

yes, same code u have, but placed in a differant method
looks neater, is easier to follow
AND it allows the code to CLEARLY say what its doing

[waxen flame]

so you made two different method, one for if it's open and one for if it's closed?

[austere panther]

good catch, corrected

[waxen flame]

as in the parentheses

[rancid gull]

and if you introduce helper methods without properly introducing side effects and so on. You will end up with worse code that is harder to follow

[waxen flame]

so let me see if i can follow what borgrel did

they made two different methods corresponding to it being open or closed

and then they called those methods

to check if it corresponds to that

[austere panther]

instead of this:

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

u have this:

public static boolean isOpeningParenthisis(char c) {
  return (c == '{' || c == '[' || c == '(');
}

it is neater, clearer and makes the code reusable

[waxen flame]

i get it

you are trying to encapsulate it

that makes sense

i can try to do something like this

[austere panther]

exactly the same code, but named and described so that ppl dont have to sit with a pen and paper for an hr to work out what the boolean algebra in the if statement means

it also allows u to TEST the boolean expression all on its own
to make sure its correct, instead of having 'some problem' somewhere' in 200 lines of code

there are HUGE benefits

[rancid gull]

and huge drawbacks when done incorrectly

[waxen flame]

my encapsulation skills could use some work

[waxen flame]

yeah i've heard of this too

i think this is something i struggled with in my objects class a bit

[austere panther]

long as u stick to single responsibility there are no drawbacks

[waxen flame]

i will try to do something like this

but i will try to post my implementation here

to see if i can get some pointers

no harm in trying to improve my skills at encapsulation

    public static boolean isBalanced(String expression) {

        Stack<Character> stack = new Stack<Character>(); 
        char top; 

        char[] arr = expression.toCharArray(); 

        for(char c : arr){
            if(isOpen(c)){
                stack.push(c); 
            }
            if(isClosed(c)){
               top = stack.peek(); 
               switch(c){
                case '}' :
                  if(top != '{'){
                    return false; 
                  }
                  else{
                    stack.pop(); 
                  }
                  break; 
                  case ')' :
                  if(top != '('){
                    return false; 
                  }
                  else{
                    stack.pop(); 
                  }
                  break; 
                  case ']' :
                  if(top != '['){
                    return false; 
                  }
                  else{
                    stack.pop(); 
                  }
               }
                
            }
        }
        
        return stack.isEmpty(); 
    }
    public static boolean isOpen(char c){
        return (c == '{' || c == '[' || c == '('); 
    }
    public static boolean isClosed(char c){
        return (c == '}' ||  c == ']' || c == ')'); 
    }```

here was my attempt at this without looking at borgels

code still works

which is a good thing

but i dont think its as neat as it could be

[rancid gull]

yeah the switch needs to be condensed. Use the switch to get the corresponding opening bracket for a given closing one.

don't mutate the stack inside the switch

[austere panther]

i think u misunderstand encapsulation

encapsulation is hiding/protecting implementation details and controlling modification

by making more methods ur actually exposing more implementation details

[waxen flame]

didn't you make helper methods as well?

or am i misunderstanding

sorry not encapsulation. not the term i'm looking for

but the word is not coming to me right now

[waxen flame]

how come?

[austere panther]

it comes down to 'dont duplicate code'

if u do the same thing, in many differant places and one of those places has an error, u end up with inconsistent behaviour
also how do u find the problem when ur actions are in 6 differant places

[rancid gull]

I should have phrased that differently. Try to extract mutating of the stack out of the switch

[waxen flame]

that makes sense

i guess i should now rethink the structure of my switch statement then

[austere panther]

this is a good use for a switch expression instead of a switch statement

[waxen flame]

what do you mean

[austere panther]

as of java ?17? i think? there is a new kind of switch u can write, its called a switch expression and it doesnt need any break statements

and its primary use is when ur trying to retrieve/modify a single value in differant ways

[rancid gull]

java 13. And there is the enhanced switch

switch(c) {
  case 'A' -> //Code
  case 'B' -> //Code
}

and the switch expression:

var result = switch(c) {
  case 'A' -> //Code
  //And so on
}

[waxen flame]

oh

i've never seen it written like this

[rancid gull]

that's why I would have liked to keep that out of this conversation

its syntax sugar

you can read about it here: https://www.baeldung.com/java-switch

[waxen flame]

syntax sugar?

ive heard that phrase once

in a lecture i think

but can you remind me what it means

[austere panther]

public boolean isMatchingParenthesis(char opening, char closing) {
  return switch (opening) {
    case '{' -> closing == '}';
    case '(' -> clasing == ')';
    case '[' -> clasing == ']';
}

not syntax suger, it actually works differantly because it expects a value coming out

[rancid gull]

syntax sugar is a feature of a language that let's you do something more easily,/ with less typing involved

the switch expression, yes. The enhanced switch , no

[waxen flame]

i will make a helper method to check if my parentheses are matching then

so that i dont have to modify the stack within the switch

@rancid gull this was the idea you had right?

[rancid gull]

yep.

[waxen flame]

so i made the helper method

but now it returns false for both again

so i may need to check the logic in my method

public static boolean isMatching(char open, char close){
        switch(open){
            case '{' :
             if(close == '}'){
                return true; 
             }
             break; 
            case '(' :
             if(close == ')'){
                return true; 
             }
             break; 
            case '[' :
             if(close == ']'){
                return true; 
             }
             break; 
        }
        return false; 
     }```

method i wrote

        Stack<Character> stack = new Stack<Character>(); 

        char[] arr = expression.toCharArray(); 

        for(char c : arr){
            if(isOpen(c)){
                stack.push(c); 
            }
            if(isClosed(c)){
               if(isMatching(c, stack.peek())){
                 stack.pop(); 
               }
               else{
                return false; 
               }
            }
        }
        
        return stack.isEmpty(); 
    }``` og method

[rancid gull]

you need to pass in the arguments the other way around

c is your closing bracket, in your stack you have the opening brackets

[austere panther]

public static boolean isMatching(char open, char close){
        switch(open){
            case '{' :
               return close == '}'
        //.....
        return false; 
     }

[waxen flame]

ah

yeah

that makes sense

[austere panther]

boolean is ur goal in this method, not an intermediate step

[waxen flame]

true

i guess i dont write boolean methods that often

fixed my method

but still returning false for both

        switch(open){
            case '{' :
            return close == '}'; 
            case '(' :
            return close == ')'; 
            case '[' :
            return close == ']'; 
        }
        return false; 
     }```

[rancid gull]

i need to see how that method is invoked

[austere panther]

u can replace the return false outside the switch with a default: return false case

[waxen flame]

            if(isOpen(c)){
                stack.push(c); 
            }
            if(isClosed(c)){
               if(isMatching(stack.peek(), c)){
                 stack.pop(); 
               }
            }
            return false; 
        }
        
        return stack.isEmpty(); 
    }```

here is the method invocation

[rancid gull]

have a look where the return false is located

[waxen flame]

ah

i fixed it

i made an else statement

and it worked

although and maybe this is a dumb question

and i'm certain it is but humor me i guess

i have a friend who's an experienced java programmer who tells me to never use else statements

and that they are largely unnecessary

and that you can just return it outside of the block

to check for if there are any cases in which it doesnt work

so is it that i want to create an else statement if there is even one instance in which my code will not work

which should then return a false condition

[austere panther]

completely false

[waxen flame]

and then not create an else statement if i want the code to iterate through the whole of the program before returning a false if it doesnt find the condition

[austere panther]

there is a specific type place where u use if statements where u dont use else

and thats validating preconditions

[waxen flame]

can you elaborate for me just so i can know for certain once and for all

because i have used else statements in cases where it wasnt needed

and then not used it in places where its needed

[austere panther]

go all the back to my code after i have finished cleaning it up

....i added some preconditions

this:

    public static boolean isBalanced(String expression) {
        if (expression == null || expression.isEmpty()) 
          return false;

        Stack<Character> stack = new Stack<Character>(); 
        for(char c : expression.toCharArray()){

            if(isOpenParenthesis(c)){
                stack.push(c); 

            } else if(isClosingParenthisis(c)){
                if ( isMatchingClosingParenthisis(c, stack.peek()) {
                  stack.pop();

                } else {
                  return false;
                }
            }
        }
        return stack.isEmpty();
    }

could technically be written like this:

    public static boolean isBalanced(String expression) {
        if (expression == null || expression.isEmpty()) 
          return false;
        else {
          Stack<Character> stack = new Stack<Character>(); 
          for(char c : expression.toCharArray()){
  
              if(isOpenParenthesis(c)){
                  stack.push(c); 

              } else if(isClosingParenthisis(c)){
                  if ( isMatchingClosingParenthisis(c, stack.peek()) {
                    stack.pop();

                  } else {
                    return false;
                  }
              }
          }
          return stack.isEmpty();
      }
    }

and HERE the else is pointless

[waxen flame]

the code looks very nearly identical

forgive me being dumb

but like

can you explain specifically what the difference is in conditions

[austere panther]

there is something called a precondition
its an assumption thats made that needs to exist BEFORE a method is called

if u have written any javadocs u should be aware of them

for example, in ur isBalanced method u have ASSUMED that the String expression passed in is not null and that it actually have characters in it

because ur method CANT work if those conditions are not met

[waxen flame]

ah right

[austere panther]

so when ur testing preconditions u never need an else, because if the conditions are not met, the method CANT and WORK work

[waxen flame]

gotcha! thanks

[idle elbow]

If you are finished with your post, please close it.
If you are not, please ignore this message.
Note that you will not be able to send further messages here after this post have been closed but you will be able to create new posts.

[waxen flame]

this was very helpful