stacks

[Mark Sully]

Hello,

I'm new to Java. I have to write a program which takes in a string and tells you if the grouping symbols match or not and also the position where the mismatch occurs. I have to use boolean to disdinguish if there is a match or not.

here is my code:

import java.util.*;
import java.util.Scanner;
import java.util.Stack;

public class Assignment3a
  
{ 
    private static int i;
    private static final char LEFTPARENT     = '(';
    private static final char RIGHTPARENT    = ')';
    private static final char LEFTBRACE      = '{';
    private static final char RIGHTBRACE     = '}';
    private static final char LEFTBRACKET    = '[';
    private static final char RIGHTBRACKET   = ']';
   
    public static boolean isBalanced(String s)           
    {
         Stack<Character> stack = new Stack<Character>(); 
           for (i = 0; i < s.length(); i++)          
        {

             if (s.charAt(i) == LEFTPARENT)   stack.push(LEFTPARENT); 

                  else if (s.charAt(i) == LEFTBRACE)   stack.push(LEFTBRACE);  

                     else if (s.charAt(i) == LEFTBRACKET) stack.push(LEFTBRACKET);   

                       else if (s.charAt(i) == RIGHTPARENT) 
            {
                if (stack.isEmpty())                     
                  return false;      
                if (stack.pop() != LEFTPARENT)    
                  return false;
            }
            else if (s.charAt(i) == RIGHTBRACE)   
            {
                if (stack.isEmpty())                     
                  return false;
                if (stack.pop() != LEFTBRACE)      
                  return false;                   
            }
            else if (s.charAt(i) == RIGHTBRACKET) 
            {
                if (stack.isEmpty())              
                  return false;
                if (stack.pop() != LEFTBRACKET)    
                  return false;                   
            }                                          
           }
        return stack.isEmpty();                   
    }
public static void main(String args[])
{
  Scanner input = new Scanner(System.in);
  System.out.println("Enter a string with Parentheses, Brackets or curly braces: ");
  String s = input.next(); 
     
  {
    if (isBalanced(s)) 
      System.out.println("The grouping symbols in"+" \""+ s +"\" "+"match");
    else              
      System.out.println("The grouping symbols in"+" \""+ s +"\" "+ "do not match");
      System.out.println();
  }
}
}

[Christophe Verré]

Hi, welcome to the ranch

Please UseCodeTags the next time you'd like to post some code. I've added them for you this time.

[Seetharaman Venkatasamy]

your program is fine to me. but still you can improve your coding style.

   
private static int i;
for (i = 0; i < s.length(); i++) 

instead of this you can declare variable i in for loop itself . and another thing is that when you use if else statement, apply curly braces .
write

if (s.charAt(i) == LEFTPARENT) 
{  
    stack.push(LEFTPARENT);
}

instead of

if (s.charAt(i) == LEFTPARENT)   stack.push(LEFTPARENT);

[John Eipe]

I have realigned your code:

import java.util.*;
import java.util.Scanner;
import java.util.Stack;

public class Assignment3a
{ 
    private static final char LEFTPARENT     = '(';
    private static final char RIGHTPARENT    = ')';
    private static final char LEFTBRACE      = '{';
    private static final char RIGHTBRACE     = '}';
    private static final char LEFTBRACKET    = '[';
    private static final char RIGHTBRACKET   = ']';

    public static boolean isBalanced(String s)           
    {
        Stack<Character> stack = new Stack<Character>(); 
        for (int i = 0; i < s.length(); i++)          
        {
            if (s.charAt(i) == LEFTPARENT)   
                stack.push(LEFTPARENT); 
            else if (s.charAt(i) == LEFTBRACE)   
                stack.push(LEFTBRACE);  
            else if (s.charAt(i) == LEFTBRACKET) 
                stack.push(LEFTBRACKET);   
            else if (s.charAt(i) == RIGHTPARENT) 
            {
                if (stack.isEmpty())                     
                    return false;      
                if (stack.pop() != LEFTPARENT)    
                    return false;
            }
            else if (s.charAt(i) == RIGHTBRACE)   
            {
                if (stack.isEmpty())                     
                    return false;
                if (stack.pop() != LEFTBRACE)      
                    return false;                   
            }
            else if (s.charAt(i) == RIGHTBRACKET) 
            {
                if (stack.isEmpty())              
                    return false;
                if (stack.pop() != LEFTBRACKET)    
                    return false;                   
            }                                          
        }
        return stack.isEmpty();                   
    }

    public static void main(String args[])
    {
        Scanner input = new Scanner(System.in);
        System.out.println("Enter a string with Parentheses, Brackets or curly braces: ");
        String s = input.next(); 
        if (isBalanced(s)) 
               System.out.println("The grouping symbols in"+" \""+ s +"\" "+"match");
        else              
            System.out.println("The grouping symbols in"+" \""+ s +"\" "+ "do not match");
            System.out.println();
    }
}

Its working fine. :-)

[Wouter Oet]

Also some if-statements can be compressed:

if (s.charAt(i) == LEFTPARENT)      
    stack.push(LEFTPARENT);    
else if (s.charAt(i) == LEFTBRACE)      
    stack.push(LEFTBRACE);     
else if (s.charAt(i) == LEFTBRACKET)    
    stack.push(LEFTBRACKET);    

Becomes

char c = s.charAt(i);
if(c == LEFTPARENT || c == LEFTBRACE || c == LEFTBRACKET)
    stack.push(c);

[Rob Spoor]

I agree with Seetharaman - always add brackets ({}). This allows you to add a simple statement (System.out.println anyone?) without breaking your code because the original statement all of a sudden is no longer part of the if-statement.

[Campbell Ritchie]

Welcome to the Ranch

I was not quite sure about the use of the == operator, because you usually use the equals() method, but in this case boxing and unboxing will take care of that.
Have you considered a Map?

Map<Character, Character> pairs;
 . . .
pairs = new HashMap<Character, Character>();
pairs.put('(', ')'); // Your constants are of course much more elegant than writing '(' etc.
pairs.put('[', ']');
// etc

Or even . . .

pairs.put(')', '('); // etc

Then when you find a character in your String, you can see whether the character at the top of the stack matches it.

Just an idea . . . it might not suit your purposes.

[Wouter Oet]

Campbell Ritchie wrote:I was not quite sure about the use of the == operator, because you usually use the equals() method, but in this case boxing and unboxing will take care of that.

String.charAt returns a char and the constants are also chars so autoboxing doesn't come into play there. Only at stack.push(stuff);

[Christophe Verré]

Campbell's comment is still valid about the != operator on the stack.pop() call. (you owe me one )

[Wouter Oet]

damm I overlooked that one But he said == not !=

[Mark Sully]

Thank you guys for your responses. I probably wasn't clear what my actual problem is. I cannot figure out the position when a mismatch occurs and display it. f.e. (ab[c) should give position #3 where the mismatch occurs.
Thank you again for all the hints you gave me for the rest of the code.

[Campbell Ritchie]

Shut up Wouter. I have to make the most of it when I get something right

[Wouter Oet]

Hahaha the next time that you get something right I will praise you

[Kurt Van Etten]

Hi Mark,

In your original post you say you need to identify where the mismatch occurs, but you also say that you need to use a boolean to distinguish if there is a match or not. I'm not sure how to reconcile those two things, but typically if you want to identify where something happens in a String, you would have your method return an int giving the index where something first happens (and have it return a value like -1 if it never finds a mismatch).

One way to do this would be to push the index of the char into the stack along with the char as you process the String, and then you can return the index if you have a mismatch.

[Mark Sully]

That is my problem. I don't know how.

[Campbell Ritchie]

Create a class which incorporates an int (for the index) and the char.

[Mark Sully]

That is my problem. I don't know how.

[Kurt Van Etten]

Hi Mark,

If you have a bunch of related data that you want to treat as a unit, so that you can keep them together in a data structure like a list or a stack, create a little helper class to hold them. For your program you could do something like:

class Pair {
  private char ch;
  private int idx;

  public Pair (char ch, int idx) {
    this.ch = ch;
    this.idx = idx;
  }

  char getCh() {return ch;}
  int getIdx() {return idx;}
}

You'd want to place this in your program file outside of the Assignment3a class declaration. Then later in your program when you create your stack, it would be a stack of Pair instead of a stack of Character, and you would be pushing and popping Pair objects. You'll need to modify your logic a little bit to handle the indexes, but that should be pretty straightforward.

By the way, in your main method when you prompt the user for input, you probably want to use nextLine() instead of next(), so that the input can contain blanks between the words and symbols.

[Mark Sully]

Thank you Kurt,

it makes sense to me that I can resolve this by creating a new class. Like I mention before, I'm a total newbie to Java. And coming from C, I didn't know that Java is so much more advanced than C.
You suggestion is great, but I can't use it, because we did not covered "this" yet. I did some research on it and kinda get it. This assignment has really silly requirements: We have to use boolean and have to get the position.
But thank you again for your help and patience.

[Kurt Van Etten]

Well, there is also the kludgy way to do it, which is to simply have two stacks: one char and one int, and do your pushing and popping in parallel as you scan through the string.

BTW, I'm really just using the Pair class as a glorified struct, if you're coming at this from a C background. And you could strip it down to the bare minimum:

class Pair {
  char ch;
  int idx;
}

...and just access the member attributes directly, although that's bad form from a OO perspective.

[Campbell Ritchie]

Kurt Van Etten wrote: . . . that's bad form from a OO perspective.

Agree.

[Mark Sully]

Thanks Kurt. I even tried the kludgy way and tried to create a new class and all I get are error messages. Maybe I still think too much in C. However, I appriciate your time and efford by helping me. I still learned a lot. I just turn it in the way it is without the position matching. At least the boolean part is working.
Thanks again.