CODEWITHSUNDEEP
javabracketsstack
Jonny_Appleby12
Jonny_Appleby12

Reputation: 61

using stacks to check for matching brackets in java

hi guys I am trying to create a program to allow a user to input a sequence of brackets (one at a time) and check to see whether there is a corresponding ending bracket. The brackets are entered on a new line every time to aid in the reading. I've set up an ADT for it but just cant think of how to get the while loop going and the checking...... I know if an ( bracket is entered i should push that into the stack and when a ( is entered i should pop one of the stack but I just cant work out the bits in the middle any help would be loved :)

//main code   
import java.util.*;

public class SameBrackets
{
   public static void main(String[] args)
   {
      Stack bracket = new Stack();
      Scanner kybd = new Scanner(System.in);

      System.out.print("Enter bracket > ");
      String bracketentered = kybd.next();


          if ("(".equals(bracketentered) )
          {
                 bracket.push(bracketentered);
                 System.out.println(") needed");
          }
          else if (")".equals(bracketentered))
          {
              bracket.pop();
              System.out.println("( needed");
          }


      }
  }

//ADT code

public class Stack
{
    private String[] a;         //String array
    private int top;

    public Stack()
    {
       a = new String[1];           //create String array
       top = 0;                      
    }

    public boolean isEmpty()
    {
         return top == 0;
    }

    public String pop()          //pop String element
    {
        top--;
        return(a[top]);         //underflow not protected
    }

    public void push(String x)      //push String element
    {
        if (top == a.length)
        {
            resize();
        }
        a[top] = x;
        top++;
    }  

    private void resize()
    {
        String[] temp = new String[a.length * 2];   //resize String array
        for (int i = 0; i < a.length; i++)
        {
            temp[i] = a[i];
         }
        a = temp;
    }
}

Upvotes: 0

Views: 6387

Answers (3)

zapl
zapl

Reputation: 63955

You don't need to implement your own stack, a LinkedList (specifically the Deque interface it implements) can do that already. But it's a good exercise.

Your code is missing two thing.

  • a loop that continues until some end is reached. The end of System.in is unfortunately not that easy to reach when you enter text from the console. It's usually Ctrl-D that can end. Adding your own stop mechanism is a good idea, most people don't know how to end the program otherwise.
  • you need to check that the bracket popped off the stack matches the bracket just entered.
  • you should check that the stack is actually empty at the end.

If you do that you end up with something like

// a stack. You can use your own instead.
Deque<String> stack = new LinkedList<String>();
Scanner kybd = new Scanner(System.in);

String bracketentered;

// 1) repeat while there is more, CTRL-D should end here.
while (kybd.hasNext()) {
    System.out.print("Enter bracket or 'q' to quit:");
    bracketentered = kybd.next();

    if (bracketentered.equals("q")) {
        break; // end this loop
    }

    if ("(".equals(bracketentered)) {
        // just push to stack
        stack.push(bracketentered);
    }
    else if (")".equals(bracketentered)) {
        // in case the stack is empty:
        // stack.pop() throws an exception
        // stack.poll() returns null
        String opposingBracket = stack.poll();

        // there must be a "(" on the stack(
        if (!"(".equals(opposingBracket)) {
            System.out.println("Wrong bracket");
        }
    }
    else {
        // in case it's not ( or )
        System.out.println("Illegal input:" + bracketentered);
    }
}
// 3) loop finished via "q" or end of input - check that stack is empty
if (!stack.isEmpty()) {
    System.out.println("You forgot to close the following brackets:");
    while (!stack.isEmpty()) {
        System.out.print(stack.poll() + " ");
    }
    System.out.println();
}

Regarding stack vs counting brackets in a loop: A very simple bracket counting algorithm that checks only at the end would allow ) (, a smarter one that checks during each step may fail for multi bracket combinations like [ ( ] ). A stack makes sure they are correctly hierarchical, e.g. [ () ].

Upvotes: 1

OldCurmudgeon
OldCurmudgeon

Reputation: 65821

Are you looking for something like:

if ("(".equals(bracketentered) ) {
    bracket.push(bracketentered);
} else if (")".equals(bracketentered)) {
    bracket.pop();
}
if ( bracket.isEmpty () ) {
    System.out.println("( needed");
} else {
    System.out.println(") needed");
}

Upvotes: 1

Itay Karo
Itay Karo

Reputation: 18296

  • why do you need a stack? you can just have a counter, increment it on '(' and decrement it on ')' - every time you decrement it make sure its value is still non-negative.
  • not sure what is your question about the loop. you can have a while loop that is terminated by specific input (for example - 'q').

As for your loop question:

input = getInput(scanner);
while(input != null) {
  // do what you want with the input

  input = getInput(scanner);
}

private static String getInput(Scanner scanner) {
  get the input from the scanner here - return null if no more input.
}

Upvotes: 1

Related Questions