Ëåêöèÿ 15
Çàäà÷à 1. Ïðîâåðèòü áàëàíñ êðóãëûõ ñêîáîê â ñèìâîëüíîé ñòðîêå.
Ïðèìåðû:
1.
(()) - ïðàâèëüíûé áàëàíñ ñêîáîê
2. ())( - íåïðàâèëüíûé áàëàíñ ñêîáîê
int balanced(char *str) {
int count = 0;
while (*str) {
switch(*str) {
case '(':
++count;
break;
case ')':
if (count <= 0)
return 0;
--count;
break;
default:
break;
}
}
return count == 0;
}
Ðåøåíèå çàäà÷è 1:
#include <stdio.h>
int balanced(char *str);
int main(void) {
char str[1000];
while (1) {
printf("Input expression:\n");
gets(str);
if (!*str)
break;
printf("%s\n", balanced(str) ? "Balanced" : "Non-balanced");
}
return 0;
}
int balanced(char *str) {
int count = 0;
char c;
while (c = *(str++)) {
switch(c) {
case '(':
++count;
break;
case ')':
if (count <= 0)
return 0;
--count;
break;
default:
break;
}
}
return count == 0;
}
Çàäà÷à 2. Äëÿ íàáîðà îòðåçêîâ íà ïðÿìîé íàéòè ìàêñèìàëüíîå êîëè÷åñòâî ïåðåñåêàþùèõñÿ îòðåçêîâ. Êîíöû îòðåçêîâ íàõîäÿòñÿ â ôàéëå tmp.dat. Ïåðâîå ÷èñëî â ôàéëå — êîëè÷åñòâî îòðåçêîâ.
0
( 1 ( 2 ( 3 )
2 ( 3 ) 2 )
1 ) 0
Çàäà÷à 2 î÷åíü ïîõîæà íà çàäà÷ó 1: ëåâûé êîíåö îòðåçêà — ëåâàÿ ñêîáêà, à ïðàâûé êîíåö îòðåçêà — ïðàâàÿ ñêîáêà. Íàéòè ìàêñèìàëüíîå êîëè÷åñòâî âëîæåííûõ ñêîáîê.
Àïïàðàò struct (ñòðóêòóðà):
struct point {
double x;
int type; /* 1 – ëåâûé êîíåö îòðåçêà, -1 — ïðàâûé êîíåö îòðåçêà */
};
double x;
int count = 0;
struct point p = { x, -1 };
x = p.x;
count += p.type;
Ðåøåíèå çàäà÷è 2:
#include <stdio.h>
struct point {
double x;
int type;
};
void sort(struct point *ar, int n);
int main(void) {
FILE *IN;
int i, N, count = 0, maxCount = 0;
struct *point array = 0;
IN = fopen("input.txt", "r");
if (IN == NULL) {
printf("File not opened\n");
return -1;
}
if (fscanf(IN, "%d", &N) != 1) {
printf("File empty\n");
fclose(IN);
return -1;
}
array = (struct point*)malloc(2 * N * sizeof(array[0]));
if (array == NULL) {
printf("Memory not allocated\n");
fclose(IN);
return -1;
}
for (i = 0; i < N; i++) {
if (fscanf(IN, "%lf%lf", &array[i * 2].x, &array[i * 2 + 1].x != 2) {
printf("Not enough numbers\n");
free(array);
fclose(IN);
}
array[i * 2].type = 1;
array[i * 2 + 1].type = -1;
}
fclose(IN);
sort(array, 2 * N);
for (i = 0; i < 2 * N; i++) {
count += array[i].type;
if (count > maxCount) {
maxCount = count;
}
}
free(array);
printf("Max intersected: %d\n", maxCount);
return 0;
}
void sort(struct point *ar, int n) {
int i, j;
struct point buf;
for (i = 0; i < n; i++) {
for (j = 0; j < n - 1; j++) {
if ((ar[j].x > ar[j+1].x) ||
((ar[j].x == ar[j+1].x) &&
(ar[j].type == -1) && (ar[j+1].type == 1))) {
buf = ar[j];
ar[j] = ar[j+1];
ar[j+1] = buf;
}
}
}
}
Çàäà÷à 3. Ïðîâåðèòü, îáðàçóþò ëè îòðåçêè èç çàäà÷è 2 ïîêðûòèå îòðåçêà [0,1].