Для каждой пары скобок напечатать номера их позиций в тексте - C (СИ)
Формулировка задачи:
В текстовом фале записан текст, сбалансированный по круглым скобкам:
(текст)::= ()|(элемент)(текст)
(элемент)::= (буква)|((текст))
Требуется для каждой пары скобок напечатать номера их позиций в тексте
порядке возрастания номеров позиций открывающих скобок
codeblok
Напривер:
(какието символы(еще символы) еще символы () )
результат: 16 23 45.
задача со стеками. надо ее немного переделать.
для подсчета максимума и минимума M - максимум
м - минимум пример: M(6,m(4,5) = 6
#include <stdio.h>
#include <stdlib.h>
#include <windows.h>
typedef struct
{
int lev; // Позиция "("
int prav; // Позиция ")"
} skobki;
typedef struct st
{
skobki data; // Позиции скобок
struct st* next; // адрес предыдущего элемента
} stack;
stack* Push(stack** top, skobki y)// Функция добавления скобок в конец стека
{
stack* p = (stack*) malloc(sizeof(stack)); //Создаём новый стек
p->data = y; // записываем значение, которое помещается в стек
p->next = *top; // Добавляем элемент на вершину стека
*top = p; // новый элемент стека становится его вершиной
return *top;
}
skobki Pop(stack** top)// Функция извлечения значения из стека
{
stack* p = *top;// Временно сохраняем указатель на верхний стек
*top = p->next;// Переходим к предыдущему элементу
skobki data = p->data;// Сохраняем значение удаляемого стек
free(p); // освобождаем память, тем самым удалили вершину
return data;
}
// Функция добавления групп скобок. При добавление элементы сразу сортируются.
// Cортировки задаётся передаваемой функцией Sravn
stack * Sort(stack** top, skobki y, int (*func)(skobki*, skobki*))
{
stack* p = (stack*) malloc(sizeof(stack));// Временный стек
p->data = y; // записываем значение, которое помещается в стек
p->next = *top; // Добавляем элемент на вершину стека
stack* cur = p;// Курсор который пробегаться по списку
// Ищем нужное место
while(cur->next && (func(&y, &cur->next->data) > 0))
{cur = cur->next;}
Push(&cur->next, y); // Добавляем указанную позицию наше значение
*top = p->next; // Спускаемся к следующему элементу
free(p);// Удаление временого стека
return *top;
}
// Функция сравнения двух значений типа skobki.Предназначена для функцией Sort.
int Sravn(skobki* a, skobki* b)
{
return (a->lev > b->lev);
}
void Print(char* stroka)// функция нахождения позиций скобок и их вывод
{
stack* top = NULL; // Временный стек хранящий текущие позиции скобок
stack* result = NULL;// Результирующий список, хранящий позиции скобок в отсортированном виде
skobki data; //вспомогательная переменая
int i=0;// Позиция в строке
while (*stroka) // Перебираем элементы строки
{
i++;
switch (*stroka)
{
case '(':
// Сохраняем позицию открывающейся скобки и добавляем позицию во временный стек
data.lev = i;
Push(&top, data);
break;
case ')':
/* Извлекаем из временного стека top позицию последней открывающейся скобки
добавляем позицию закрывающейся и добавляем эти две позиции скобок в результирующий список result.
Используем для добавления функцию добавления с сортировкой Sort*/
data = Pop(&top);
data.prav = i;
Sort(&result,data,Sravn);
break;
}
stroka++;
}
printf("\nРезультат: ");
while(result)// Перебираем все элементы стека и выводим их
{
printf("%d %d; ", result->data.lev, result->data.prav);
result = result->next;
}
}
char*read_str(FILE*F) //функция чтения из файла
{
char* outstr = (char*)malloc(10000);
char temp[100];
fgets(temp,100,F);
strcpy(outstr,temp);
for(;!feof(F);)
{
fgets(temp,100,F);
strcat(outstr,temp);
}
return outstr;
}
void main()
{
SetConsoleCP(1251);
SetConsoleOutputCP(1251);
FILE*f;
if((f= fopen("f2.txt","r"))==NULL)
{
printf("ошибка чтения файла"); getch(); return;
}
char*stroka=read_str(f);
puts(stroka);
Print(stroka);
getch();
}Решение задачи: «Для каждой пары скобок напечатать номера их позиций в тексте»
textual
Листинг программы
int s2i(char *b, char *e, int r) {return b>e ? r : s2i(b+1,e,r*10+*b-'0');}
int mx(int a, int b) {return a>b ? a : b;}
int mn(int a, int b) {return a<b ? a : b;}
char* strend(char *b) {return *b ? strend(b+1) : b-1;}
char* ps(char *b, char *e, int l) {
int dl = *b=='(' ? 1 : (*b==')' ? -1 : 0);
return ((l==0 && *b==',') || b>=e) ? b : ps(b+1,e,l+dl);
}
int f(char *b, char *e) {
char *m = ps(b+2,e,0);
switch (*b) {
case 'M':
return mx(f(b+2,m-1), f(m+1,e-1));
case 'm':
return mn(f(b+2,m-1), f(m+1,e-1));
case '(':
return f(b+1,e-1);
default:
return s2i(b,e,0);
}
}
int main() {
char t[] = "m(M(M(m(37,643),75),m(45,5)),M(67,13))";
cout << f(t,strend(t));
return 0;
}
Объяснение кода листинга программы
- В первой функции
s2iпроисходит преобразование строки в целое число. - Вторая функция
mxвозвращает максимальное значение из двух чисел. - Третья функция
mnвозвращает минимальное значение из двух чисел. - Четвертая функция
strendвозвращает указатель на последний символ в строке. - Пятая функция
psищет пару скобок в строке и возвращает указатель на закрывающую скобку. - Шестая функция
fрекурсивно обрабатывает каждый символ в строке и применяет соответствующие операции в зависимости от типа символа. - В функции
mainопределяется входная строка и вызывается функцияfдля обработки этой строки. Результат выводится на экран.