Question

Regular Expression processor in Java Overview: Create a Java program that will accept a regular expression and a filename for a text file. The program will process the file, looking at every line to find matches for the regular expression and display them. Regular Expression Format The following operators are required to be accepted: + - one or more of the following character (no groups) * - zero or more of the following character (no groups) [] – no negation, no character spans – the only format is explicit, for example [0123456789] Output: The output from your program should be formatted like this: Match found on line 10, starting at position 10 and ending at position 25: aaaaaaaaaaaaaa0 If the regular expression entered was a*[01] And the input file contained at line 10: Xxdsdsasdaaaaaaaaaaaaaaa0 Restrictions Your program must implement its own regular expression functionality – you can not use the built-in regular expression mechanism, nor can you include one from a package or JAR file unless you created it and included the source code in your submission Testing Please be sure to test your code thoroughly – it will be graded using regular expressions and files that you do not have access to. Your code must work for all regular expressions and text files as described above. While you MAY NOT share code in any way, I would encourage all of you to write tests and share them with each other. You can write and test your test cases against sites like : https://regex101.com/ or using Unix/Mac grep Some Design Hints Break this down into two problems: 1) Build a list of states from the regular expression 2) Loop over the input lines, then over each character in each input line, checking the input against the states. I built a class to wrap String, adding the idea of which character is “current” and the ability to get the current character and to peek at the next character. This made my code cleaner and easier to reason about.

Answer 1

• import java.util.*;

  import java.io.*;

  class Regex {

  public static void main(String args[]) {

  String pattern = args[0];

  BufferedReader br = new BufferedReader(new FileReader(args[2]));

  String line;

  int lineNumber = 1;

  while((line = br.readLine()) != null){

  findMatches(line, pattern, lineNumber);

  lineNumber++;

  }

  }

  public void findMatches(String s, String p, int lineNumber) {

  int n = s.length();

  String temp;

  for(int i=0;i<n;i++){

  for(int j=i+1;j<=n;j++){

  temp = s.substring(i, j);

  if(isMatch(temp, p)){

  System.out.println("Match found on line " + lineNumber + ", starting at position " + (i+1) + " and ending at position " + j + ": " + temp);

  }

  }

  }

  }

  public boolean isMatch(String s, String p){

  boolean[][] d = new boolean[s.length() + 1][p.length() + 1];

  d[0][0] = true;

  for (int i = 0; i < p.length(); ++i) {

  char current = p.charAt(i);

  if (current == '*') {

  for (int j = 0; j < s.length(); ++j) {

  d[j + 1][i + 1] = d[j + 1][i - 1];

  }

  for (int j = 0; j < s.length(); ++j) {

  if ((p.charAt(i - 1) == '.') || (p.charAt(i - 1) == s.charAt(j))) {

  d[j + 1][i + 1] = d[j + 1][i + 1] || d[j][i - 1] || d[j][i + 1];

  }

  }

  } else if (current == '.') {

  for (int j = s.length() - 1; j >= 0; --j) {

  d[j + 1][i + 1] = d[j][i];

  }

  } else {

  for (int j = 0; j < s.length(); ++j) {

  if (s.charAt(j) == p.charAt(i)) {

  d[j + 1][i + 1] = d[j][i];

  }

  }

  }

  }

  return d[s.length()][p.length()];

  }

  }