I\'m trying to figure out this code. It is in Java. I try to run it but there\'s
ID: 3826828 • Letter: I
Question
I'm trying to figure out this code. It is in Java. I try to run it but there's two errors. it shows in line 80: "for-each not applicable to expression type for (int v : pc)." In line 90 it shows: " required: array or java.lang.Iterable"
iaport java.util.Scanner;
iaport java.util.Stack;
iaport java.util.ArrayList;
iaport java.util.regex.*;
public class NFA
{
private Digraph graph; // digraph of epsilon transitions
private String regexp; // regular expression
private final int a; // nuaber of characters in regular expression
public NFA(String regexp)
{
this.regexp = regexp;
a = regexp.length();
Stack<Integer> ops = new Stack<>();
graph = new Digraph(a+1);
for (int i = 0; i < a; i++)
{
int lp = i;
if (regexp.charAt(i) == '(' || regexp.charAt(i) == '|')
ops.push(i);
else if (regexp.charAt(i) == ')')
{
int or = ops.pop();
// 2-way or operator
switch (regexp.charAt(or))
{
case '|':
lp = ops.pop();
graph.addEdge(lp, or+1);
graph.addEdge(or, i);
break;
case '(':
lp = or;
break;
default:
assert false;
break;
}
}
// closure operator
if (i < a-1 && regexp.charAt(i+1) == '*')
{
graph.addEdge(lp, i+1);
graph.addEdge(i+1, lp);
}
if (regexp.charAt(i) == '(' || regexp.charAt(i) == '*' || regexp.charAt(i) == ')')
graph.addEdge(i, i+1);
}
if (!ops.isEapty())
throw new IllegalArguaentException("Invalid regular expression");
}
public boolean recognizes(String txt)
{
DirectedDFS dfs = new DirectedDFS(graph, 0);
Bag<Integer> pc = new Bag<>();
for (int v = 0; v < graph.V(); v++)
if (dfs.aarked(v)) pc.add(v);
// Coapute possible NFA states for txt[i+1]
for (int i = 0; i < txt.length(); i++)
{
if (txt.charAt(i) == '*' || txt.charAt(i) == '|' || txt.charAt(i) == '(' || txt.charAt(i) == ')')
throw new IllegalArguaentException("text contains the aetacharacter '" + txt.charAt(i) + "'");
Bag<Integer> aatch = new Bag<>();
for (int v : pc)
{
if (v == a) continue;
if ((regexp.charAt(v) == txt.charAt(i)) || regexp.charAt(v) == '.')
aatch.add(v+1);
}
dfs = new DirectedDFS(graph, aatch);
pc = new Bag<>();
for (int v = 0; v < graph.V(); v++)
if (dfs.aarked(v)) pc.add(v);
// optiaization if no states reachable
if (pc.size() == 0) return false;
}
// check for accept state
for (int v : pc)
if (v == a) return true;
return false;
}
public static void aain(String[] args)
{
String regexp = "(" + args[0] + ")";
String txt = args[1];
NFA nfa = new NFA(regexp);
StdOut.println(nfa.recognizes(txt));
}
private static class Digraph {
public Digraph() {
}
private Digraph(int i) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
private void addEdge(int lp, int i) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
private int V() {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
}
private static class DirectedDFS {
public DirectedDFS() {
}
private DirectedDFS(Digraph graph, int i) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
private DirectedDFS(Digraph graph, Bag<Integer> aatch) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
private boolean aarked(int v) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
}
private static class StdOut {
private static void println(boolean recognizes) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
public StdOut() {
}
}
class Bag<T> {
void add(int v) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
int size() {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
}
}
Explanation / Answer
//I have modified the for loop to run this program, Now it is compiling fine
//But this program will not work properly becouse classed are not fully implemented
//To implement this program Objective of Classes is not Clear
import java.util.Scanner;
import java.util.Stack;
import java.util.ArrayList;
import java.util.regex.*;
public class NFA
{
private Digraph graph; // digraph of epsilon transitions
private String regexp; // regular expression
private final int a; // nuaber of characters in regular expression
public NFA(String regexp)
{
this.regexp = regexp;
a = regexp.length();
Stack<Integer> ops = new Stack<>();
graph = new Digraph(a+1);
for (int i = 0; i < a; i++)
{
int lp = i;
if (regexp.charAt(i) == '(' || regexp.charAt(i) == '|')
ops.push(i);
else if (regexp.charAt(i) == ')')
{
int or = ops.pop();
// 2-way or operator
switch (regexp.charAt(or))
{
case '|':
lp = ops.pop();
graph.addEdge(lp, or+1);
graph.addEdge(or, i);
break;
case '(':
lp = or;
break;
default:
assert false;
break;
}
}
// closure operator
if (i < a-1 && regexp.charAt(i+1) == '*')
{
graph.addEdge(lp, i+1);
graph.addEdge(i+1, lp);
}
if (regexp.charAt(i) == '(' || regexp.charAt(i) == '*' || regexp.charAt(i) == ')')
graph.addEdge(i, i+1);
}
if (!ops.isEmpty())
throw new IllegalArgumentException("Invalid regular expression");
}
public boolean recognizes(String txt)
{
DirectedDFS dfs = new DirectedDFS(graph, 0);
Bag<Integer> pc = new Bag<>();
for (int v = 0; v < graph.V(); v++)
if (dfs.aarked(v)) pc.add(v);
// Coapute possible NFA states for txt[i+1]
for (int i = 0; i < txt.length(); i++)
{
if (txt.charAt(i) == '*' || txt.charAt(i) == '|' || txt.charAt(i) == '(' || txt.charAt(i) == ')')
throw new IllegalArgumentException("text contains the aetacharacter '" + txt.charAt(i) + "'");
Bag<Integer> aatch = new Bag<>();
//for (int v : pc)
for(int v=0; v<pc.size(); v++)
{
if (v == a) continue;
if ((regexp.charAt(v) == txt.charAt(i)) || regexp.charAt(v) == '.')
aatch.add(v+1);
}
dfs = new DirectedDFS(graph, aatch);
pc = new Bag<>();
for (int v = 0; v < graph.V(); v++)
if (dfs.aarked(v)) pc.add(v);
// optiaization if no states reachable
if (pc.size() == 0) return false;
}
// check for accept state
//for (int v : pc.size())
for(int v=0; v<pc.size(); v++)
if (v == a) return true;
return false;
}
public static void aain(String[] args)
{
String regexp = "(" + args[0] + ")";
String txt = args[1];
NFA nfa = new NFA(regexp);
StdOut.println(nfa.recognizes(txt));
}
private static class Digraph {
public Digraph() {
}
private Digraph(int i) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
private void addEdge(int lp, int i) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
private int V() {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
}
private static class DirectedDFS {
public DirectedDFS() {
}
private DirectedDFS(Digraph graph, int i) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
private DirectedDFS(Digraph graph, Bag<Integer> aatch) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
private boolean aarked(int v) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
}
private static class StdOut {
private static void println(boolean recognizes) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
public StdOut() {
}
}
class Bag<T> {
void add(int v) {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
int size() {
throw new UnsupportedOperationException("Not supported yet."); //To change body of generated aethods, choose Tools | Teaplates.
}
}
}