2 questions in C Programming - $20

[RedJoker]

Need it Monday. These problems should be very basic, unfortunately it's all jiberish to me. C programming only, C++ is no good to me.

$20 to first person who posts complete solutions without syntax errors, I don't think they'll be too long. Or we can do $10 per solution, w/e. Transfers on Stars.

Note: In some places I've changed the [] to {} because things went into italics when I put it around an i. If you need to include [ i] in your code, please leave it as [] when posting so that I can go to quote and copy the text.

I'm posting in BBV4L because I know there are people here with programming skillz and there isn't enough traffic in the software forum.

<font color="blue"> 1. Write a program which implements the bracket matching function as indicated in the
second slide of strings(6).nb, under the section “Exercise”. </font>

Exercise:

An opening (curved)bracket ASCII 40 at position i matches a closing bracket ASCII 41 at position j&gt;i if the number of ASCII 40 characters match the number of ASCII 41 characters in the sublist i-&gt;j . This statement can also be read as implying that the closing bracket at j matches the opening bracket at i.
Write a function
[ QUOTE ]
int matching(int k,char * x,int n)

[/ QUOTE ]
which returns the index of the bracket matching the bracket at k. Return -1 if no matching bracket exists or the character at k is not an opening or closing (curved) bracket.

<font color="blue"> 2. Implement the triangulation program as described in the sixth slide of pointers(5).nb. </font>

Triangulation program described in the slide:

(Step 1)Write a function

[ QUOTE ]
int Diagonal(int * x,int * y, int n,int i ,int j)

[/ QUOTE ]

which returns 1 if the segment i-&gt;j is a diagonal and returns 0 otherwise. Note that:
The segment i-&gt;j is a diagonal iff
1. the edge k-&gt;l with l=(k+1)%n with both k and l different from i and j does not intersect i-&gt;j for all k=0,...,n-1
2. i-&gt;j is internal to the vertex at i (i.e i-1-&gt;i-&gt;i+1 with suitable modification when either i=0 or i=n-1)
Use the polygon defined in polygon.txt for test purposes. In particular confirm that the output due to

[ QUOTE ]
//Process data
printf("The diagonals are:\n");
for(i=0;i&lt;n;i++)
for(j=i+1;j&lt;n;j++)
if(Diagonal(x,y,n,i,j))
printf("\t%d -&gt; %d \n",i,j);
//End processing

[/ QUOTE ]

Is

[ QUOTE ]
The diagonals are:
1 -&gt; 3
1 -&gt; 4
1 -&gt; 5
1 -&gt; 7
1 -&gt; 8
2 -&gt; 4
2 -&gt; 5
2 -&gt; 6
2 -&gt; 7
2 -&gt; 8
3 -&gt; 6
3 -&gt; 7
3 -&gt; 8
4 -&gt; 6
4 -&gt; 7
5 -&gt; 7

[/ QUOTE ]

(Step 2) Use an array flag to form sub polygons defined by including or excluding the i-th vertex according to whether flag[i} is 1 or 0.
A vertex is called an ear if ib-&gt;ia is a diagonal where
ib is the index of the vertex before i with flag[ib] equal to 1 (skip vertices with flag[ib] equal to 0)
ia is the index of the vertex before i with flag[ia] equal to 1 (skip vertices with flag[ia] equal to 0)

[ QUOTE ]
int EarQ(int i, int * x,int * y, int * flag, int n)

[/ QUOTE ]

On including all points, confirm that

[ QUOTE ]
for(i=0;i&lt;n;i++) flag{i}=1;
printf("The Ears are:\n");
for(i=0;i&lt;n;i++)
if(flag{i}&amp;&amp;EarQ(i,x,y,flag,n)) printf("\t%d\n",i);

[/ QUOTE ]

gives the output

[ QUOTE ]
The Ears are:
0
2
3
5
6

[/ QUOTE ]

and that the exclusion of vertices 0,2 and 3

[ QUOTE ]
for(i=0;i&lt;n;i++) flag{i}=1;
flag[0]=0;flag[2]=0;flag[3]=0;
printf("The Ears are:\n");
for(i=0;i&lt;n;i++)
if(flag{i}&amp;&amp;EarQ(i,x,y,flag,n)) printf("\t%d\n",i);

[/ QUOTE ]

gives the output

[ QUOTE ]
The Ears are:
4
5
6
8

[/ QUOTE ]

(Step 3) The basic result here is that every triangulation of a polygon of n vertices uses n-3 diagonals and consists of n-2 triangles. (See O'Rourke)
Create a function

[ QUOTE ]
int Triangulate(int * x,int * y,int n,int * indS,int * indE);

[/ QUOTE ]

where memory for n-3 integers has been allocated for the starting(resp. ending) indices of the triangulating diagonals.
A Triangulation algorithm is
set up an internal(i.e to Triangulate) integer array flag of length n
set all elements to 1 to initially include all vertices
set up an internal integer array ear
set ear{i} to 1(resp. 0) if i is(resp. is not) an ear for i=0,...,n-1
while the number of diagonals found is less than n-3
locate the next ear i among the currently included vertices(i.e flag{i} is 1)
find the index ib(resp. ia) of the nearest included before(resp. after) vertex.
Note that both flag[ib] and flag[ia] must be 1
update the number of diagonals found
add the start and end of the diagonal found(i.e ib and ia) to indS and indE
exclude the vertex i (i.e set flag{i} to 0)
update the ear status of ib and ia

Confirm that

[ QUOTE ]
ndiag=1,i=0 ia=8 ib=1
ndiag=2,i=1 ia=8 ib=2
ndiag=3,i=2 ia=8 ib=3
ndiag=4,i=5 ia=4 ib=6
ndiag=5,i=6 ia=4 ib=7
ndiag=6,i=8 ia=7 ib=3

[/ QUOTE ]