JAVA

Requirements This assignment lets you get familiar with simple parsing and dynamic programming algorithm design. It is worth 5% of your total course marks. You need to solve one of the following two problems Problem 1: Nested List Sets We have a special type of set where the syntax is depicted by the following grammar: ")" Set Elementlist := | List List Element Atom := "{" Element!ist := Element | Element "," List Atom I Set stands for the empty word, i.e., the list in a set can be empty Note the alphabet consists of the characters which are also used for the syntax of the set. At first thought one may think that it is not possible to decide efficiently if a word consisting of "(", )" and "," is a syntactically correct representation of a set or not. However, using dynamic programming design techniques, your task is to write an efficient program that will decide this problem. Input Specification The first line of the input file contains a number representing the number of lines to follow Each line consists of a word, for which your program has to decide if it is a syntactically correct representation of a set. You may assume that each word consists of between 1 and 300 characters from the set { (", )", , } Output Specification Output for each test case whether the word is a set or not. Adhere to the format shown in the sample output Sample Input 4 0 Sample Output Word #1: Set Requirements This assignment lets you get familiar with simple parsing and dynamic programming algorithm design. It is worth 5% of your total course marks. You need to solve one of the following two problems Problem 1: Nested List Sets We have a special type of set where the syntax is depicted by the following grammar: ")" Set Elementlist := | List List Element Atom := "{" Element!ist := Element | Element "," List Atom I Set stands for the empty word, i.e., the list in a set can be empty Note the alphabet consists of the characters which are also used for the syntax of the set. At first thought one may think that it is not possible to decide efficiently if a word consisting of "(", )" and "," is a syntactically correct representation of a set or not. However, using dynamic programming design techniques, your task is to write an efficient program that will decide this problem. Input Specification The first line of the input file contains a number representing the number of lines to follow Each line consists of a word, for which your program has to decide if it is a syntactically correct representation of a set. You may assume that each word consists of between 1 and 300 characters from the set { (", )", , } Output Specification Output for each test case whether the word is a set or not. Adhere to the format shown in the sample output Sample Input 4 0 Sample Output Word #1: Set