Using Stack ADT, write a program to test if a given input string containing the

Question

Using Stack ADT, write a program to test if a given input string containing the exactly one character ‘$’ is in the following set. L = { w$w’: w is an empty string or a string of characters such that each character belongs to the English alphabet {a, b, c, ……, x, y, z} and w’ = reverse(w)} For example, $, abc$cba, raoli$iloar are in L. usca$caus, rao$li, abc$abc are not in L. Here are sample runs of your program.

Please input a string containing $: $

$ is in that given set.

Please input a string containing: raoli$iloar

raoli$iloar is in that given set.

Please input a string containing $: abc$cnbc

abc$cnbc is not in that given set.

Explanation / Answer

import java.util.Scanner;
import java.util.Stack;
import java.util.regex.Pattern;

public class TestLanguage {

   /**
   * @param args
   */
   public static void main(String[] args) {
       Scanner sc = new Scanner(System.in);
       System.out.println("Please input a string containing $: ");

       String input = sc.nextLine();
       // First split the String into two parts based on $.
       // Case 1. both parts are null , means String only contain $ , it is in Set
       // Case 2 .Compare length of both parts if unequal then String is not in set
       // If length is equal , find the reverse of one part and compare the reverse
       // with other part , if same then String is in set otherwise not

       Stack stack = new Stack<>();

       String[] parts = input.split(Pattern.quote("$"));
       String part1 = null;
       String part2 = null;
       if (parts.length <= 1) {
           System.out.println(input + " is not in that given set. ");
       } else if (parts.length > 1) {
           part1 = parts[0];
           part2 = parts[1];

           if ((part1 == null || part2 == null) && parts.length > 1) {
               System.out.println(input + " is not in that given set. ");
           } else if (part1 != null && part2 != null && part1.length() != part2.length()) {
               System.out.println(input + " is not in that given set. ");
           } else {
               // find reverse of one part using stack
               // First push into stack then pop
               for (int i = 0; i < part2.length(); i++) {
                   stack.push(part2.charAt(i));
               }
               String reverse = "";
               while (!stack.isEmpty()) {
                   reverse += stack.pop();
               }

               if (part1.equals(reverse)) {
                   System.out.println(input + " is in that given set. ");
               } else {
                   System.out.println(input + " is not in that given set. ");
               }
           }
       }

   }

}

output

Please input a string containing $:
$
$ is not in that given set.

Please input a string containing $:
abcd$dcba
abcd$dcba is in that given set.

Related Questions

Navigate

• Browse (All)
• Browse U
• Subjects

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