Ëåêöèÿ 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].