//program to construct Turing Machine for well formedness of parenthesis
import java.io.*;
class tm {
public static void main(String args[]) throws IOException {
BufferedReader o = new BufferedReader(new InputStreamReader(System.in));
char a[] = new char[15];
int i, j, flag = 1;
System.out.println("Enter String: ");
String str = o.readLine();
for (i = 0; i < str.length(); i++)
a[i] = str.charAt(i);
for (i = 0; i < str.length(); i++) {
if (a[i] == ')') {
for (j = i - 1; j >= 0; j--) {
if (a[j] == '(') {
a[i] = '*';
a[j] = '*';
break;
}
}
}
}
for (i = 0; i < str.length(); i++)
if (a[i] != '*')
flag = 0;
if (flag == 1)
System.out.println("Accepted");
else
System.out.println("Not Accepted");
}
}
/* output
Enter String:
(()(()))
Accepted
Process Exit...
Enter String:
(()(()
Not Accepted
Process Exit...
*/