Given a String of parenthesis delimiters ( \'(\' and \')\' ), modify the stack a

Question

  Given a String of parenthesis delimiters ( '(' and ')' ), modify the stack algorithm that checks for matching delimiters to calculate the maximum nesting level. The string may have unmatched parentheses. In that case, return -1.  Examples:  " ( ) " --> 1  " ( ( ( ) ( ) ) )" --> 3  " ( ( ( () ) ) ) " --> 4  " ( () () () ) " --> 2  " ) ) ( " --> -1  " " --> 0  Constraints on the code:  -- You may use Stack. You may use Java objects and classes for doing char stream I/O. You may not use any other Java objects and classes.  -- Note: the input may have unbalanced delimiters. You must make use of the algorithm for matching delimiters.  

Explanation / Answer

import java.io.BufferedReader;

import java.io.BufferedWriter;

import java.io.File;

import java.io.FileInputStream;

import java.io.FileNotFoundException;

import java.io.FileOutputStream;

import java.io.IOException;

import java.io.InputStreamReader;

import java.io.OutputStreamWriter;

import java.util.Stack;

public class MatchDelimiters {

   public static void main(String args[]) throws IOException

   {

       BufferedReader br = readFile();

       BufferedWriter bw = writeFile();

       String line = null;

       while( (line = br.readLine())!= null ) {

      System.out.println(line + " --> " + maxNesting(line));

      }

       br.close();

       bw.close();      

   }

   public static BufferedReader readFile() throws FileNotFoundException

   {

       File file = new File("input");

       return new BufferedReader(new InputStreamReader(new FileInputStream(file)));      

   }

   public static BufferedWriter writeFile() throws FileNotFoundException

   {

       File file = new File("output");

       return new BufferedWriter(new OutputStreamWriter(new FileOutputStream(file)));

   }

   public static int maxNesting(String input)

   {

       int nesting = 0;

       int maxNesting = 0;

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

       for(int i = 0; i < input.length(); i++)

       {

           Character c = input.charAt(i);

           if(c.charValue() == '(')

           {

               stack.push(c);

               nesting = 0;

           }              

           else if(c.charValue() == ')')

           {

               if(!stack.isEmpty())

               {

                   Character delimter = stack.pop();

                   if(delimter.charValue() == '(')

                       nesting++;

               }

           }

           if(nesting > maxNesting)

               maxNesting = nesting;          

       }

       return maxNesting;

   }

}

Related Questions

Navigate

• Browse (All)
• Browse G
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.