I had to finish a packet for my AP JAVA class. I am confused on how to do these
ID: 3661476 • Letter: I
Question
I had to finish a packet for my AP JAVA class. I am confused on how to do these questions. Can anyone help me out? Just in case you missed it this has to be completed with JAVA, and using recursion. Thanks!!
A) Write a recursive function to match regular expressions. In regular expression, a "*" matches zero or any number of characters, a "." matches any single character. Thus "a*c" will match "ac" and "aabc", and "a.c" matches "abc". Your function should take a string and a regular expression as the input and return true if they match and otherwise return false.
B) Write a program to draw a Sierpinski triangle using the drawingPanel class. An example algorithm:
Start with an equilateral triangle.
Subdivide it into four smaller congruent equilateral triangles and remove the central one.
Explanation / Answer
A) the recursive function to match regular exressions is the following:
string is a given string and q is a character with a pointer *q.
bool recursive_match(const char *string, const char *q) {
assert(string && q);
if (*q == '') return *string == ''; //if no character then returns the end of string if
// if the next character is not '*': then it must match current character."*" matches 0 or any num of characters,
if (*(q+1) != '*') {
assert(*q != '*');
return ((*q == *string) || (*q == '.' && *string!= '')) && recursive_match(string+1, q+1);
}
// if the next character is '*' , "." matches andy single character,
while ((*q == *string) || (*q == '.' && *string != '')) {
if (recursive_match(string, q+2)) return true;
string++;
}
return recursive_match(string ,q+2);
}
B)To draw a Sierpinski triangle using drawingPanel class:
import java.awt.*;
import java.util.*;
public class Sierpinski_Triangle {
public static final int SIZE = 600; // This is the constant height of DrawingPanel we have set.
public static void main(String[] args) {
Scanner console = new Scanner(System.in);
System.out.print("Enter the level for triangle to be present ");
int lev = console.nextInt();
// we wll initialize the drawing panel here.
DrawingPanel panel = new DrawingPanel(SIZE, SIZE);
panel.setBackground(Color.CYAN);
Graphics g = panel.getGraphics();
// Fing the triangle endpoints and perform recursion
int triangleHeight = (int) Math.round(SIZE * Math.sqrt(6.0) / 4.0);
Point l = new Point(0, triangleHeight);
Point m = new Point(SIZE / 2, 0);
Point n = new Point(SIZE, triangleHeight);
drawFigure(lev, g, l, m, n);
}
// we will draw a Sierpinski fractal to the given level inside the triangle
// whose vertices are (l, m, n).
public static void drawtheFigure(int lev, Graphics g,
Point l, Point m, Point n) {
if (lev == 1) {
// base case: to draw a simple Sierpinski triangle at level 1
Polygon p = new Polygon();
panel.addPoint(l.x, l.y);
panel.addPoint(m.x, m.y);
panel.addPoint(n.x, n.y);
g.fillPolygon(panel);
} else {
// This is the recursive case which involves split into 3 triangles
Point o = midpoint(l, m);
Point p = midpoint(m, n);
Point q = midpoint(l, n);
// we will recurse on three triangular areas to create triangle
drawtheFigure(lev - 1, g, l, o, q);
drawtheFigure(lev - 1, g, o, m, p);
drawtheFigure(lev - 1, g, q, p, n);
}
}
// This function returns the midpoint of l and m which is required to create an octal in the triangle and create sierpinski triangle.
public static Point midpoint(Point l, Point m) {
return new Point((l.x + m.x) / 2, (l.y + m.y) / 2);
}
}
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.