Programming with Stacks WRITE IN JAVA Write a program that uses Stacks to determ

Question

Programming with Stacks

WRITE IN JAVA

Write a program that uses Stacks to determine if a line written with parentheses iswell-formed or not. This is a subtask similar to what compilers use to determine if you are missing (or have too many) curly braces or parentheses or brackets.

The program should read the user input, and should push an open ( when it is encountered, and perform a pop when a closed ) is encountered.

This way, if at the end of the program run, the stack is empty, then the line is well-formed.

If the end of the input is reached and the stack is not empty, that means there were too many open parentheses, (.

If at any time, the program sees a closed parenthesis, ), and the stack is empty already, then an exception will be thrown and this is an indicator that there are too many, or at least a misplaced, closed parenthesis.

Either situation should cause the program to indicate it is not well formed.

An example run might look like the following:

Please input a set of parentheses

()(())(())

--> Input is well-formed

Another example run might look like the following:

Please input a set of parentheses

)(())(())

--> Sorry, input is NOT well-formed

Please input a set of parentheses

()(())(())

--> Input is well-formed

Explanation / Answer

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class ExpressionValidator
{
   public static void main (String[] args) throws java.lang.Exception
   {
       // your code goes here
       Scanner input = new Scanner(System.in);
       System.out.println("Please enter the expression : ");
      
       String line = input.nextLine();
       Stack<Character> st = new Stack<Character>();
      
       int i = 0;
       for(i=0;i<line.length();i++)
       {
           if(line.charAt(i)=='(')
               st.push(new Character(line.charAt(i)));
           else
           {
               try
               {
                   st.pop();
               }
               catch (EmptyStackException e) {
                   System.out.println("Invalid expression");
                   break;
               }
           }
          
       }
      
       if(i==line.length() && st.empty())
           System.out.println("Valid expression");
       else
           System.out.println("Invalid expression");
      
      
   }
}

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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