Найти количество правильных скобочных выражений - C (СИ)
Формулировка задачи:
Помогите пожалуйста, ничего не приходит в голову.
Найти количество правильных скобочных выражений длины N (1 ≤ N ≤ 100), составленных из скобок M (1 ≤ M ≤ 3) типов.
Определение правильного скобочного выражения (на примере M = 2 – круглые и квадратные скобки).
Пустое выражение правильное.
Если E – правильное выражение, то (E) и [E] – тоже правильные выражения.
Если E и F – правильные скобочные выражения, то EF – тоже.
Примеры правильных скобочных выражений:
()
[()]([[()]])[][[[(())]]]
Примеры неправильных скобочных выражений:
(
]
([)]
(][)
Во входном файле содержатся записанные через пробел числа N и M.
В выходной файл выводится одно число.
Пример ввода 1
4 2
Пример вывода 1
8
Пример ввода 2
1 3
Пример вывода 2
0
Решение задачи: «Найти количество правильных скобочных выражений»
textual
Листинг программы
#include <iostream.h>
#include <string.h>
/* Рекурсивная процедура проверки правильности
скобочной структуры */
int chkPexpr(char * Arr, int b, int e)
{
int i,j,k;
for (i=b; i<=e; i++)
{
if (*(Arr+i)=='(')
{
k=1;
for (j=i+1; j<=e; j++)
{
if (*(Arr+j)=='(')
k++;
if (*(Arr+j)==')')
{
k--;
if (k==0)
return chkPexpr(Arr,i+1,j-1) * chkPexpr(Arr,j+1,e);
}
}
return 0;
}
if (*(Arr+i)=='[')
{
k=1;
for (j=i+1; j<=e; j++)
{
if (*(Arr+j)=='[')
k++;
if (*(Arr+j)==']')
{
k--;
if (k==0)
return chkPexpr(Arr,i+1,j-1) * chkPexpr(Arr,j+1,e);
}
}
return 0;
}
if ((*(Arr+i)==')') || (*(Arr+i)==']')) return 0;
}
return 1;
}
int main(int argc, char* argv[])
{
char A[]="((a s d)(1 2 3))";
cout << chkPexpr(A,0,strlen(A)-1) << endl;
return 0;
}
Объяснение кода листинга программы
- chkPexpr(Arr,b,e) - рекурсивная функция для проверки правильности скобочной структуры.
- Arr - массив символов, в котором проверяется скобочная структура.
- b и e - индексы, определяющие диапазон проверки скобочной структуры.
- i, j, k - временные переменные, используемые внутри функции для выполнения проверки.
- k используется для отслеживания количества открытых скобок и квадратных скочек в выражении.
- *if ((Arr+i)=='(')** - проверка наличия открывающей скобки.
- *if ((Arr+i)=='[')** - проверка наличия открывающей квадратной скобки.
- if (((Arr+i)==')') || ((Arr+i)==']')) return 0; - проверка наличия закрывающей скобки или закрывающей квадратной скочки.
- *return chkPexpr(Arr,i+1,j-1) chkPexpr(Arr,j+1,e);** - рекурсивный вызов функции для проверки вложенных скобочных структур.
- *int main(int argc, char argv[])** - главная функция программы.
- char A[]=
((a s d)(1 2 3)); - определение строки, которую необходимо проверить на правильность скобочной структуры. - cout << chkPexpr(A,0,strlen(A)-1) << endl; - вывод результата проверки в консоль.
- return 0; - завершение работы программы.