Отправлено: 24.01.20 20:18. Заголовок: Программа на языке C проверки парности круглых скобок в строке с использованием стека.

Очень часто в качестве примера использования стека начинающим программистам дают задание написать программу проверки парности скобок (например, круглых скобок) в строке с помощью стека.

Подобная программа, написанная на C, усложняется тем, что начинающему программисту требуется самостоятельно реализовать стек.

Вот один из вопросов, касающихся подобного задания, на сайте Stackoverflow Pop works only once in specific function

И хотя мой ответ помечен знаком минус, объективно это лучший ответ, так как он более подробно описывает недостатки представленного в вопросе кода, а также демонстрирует, как такое задание можно реализовать. Тот, кто минусовал мой ответ, очевидно, имел мотивы, не связанные с оценкой ответа с точки зрения программирования.

Я уверен, что очень трудно будет найти более лучший и полный код на C решения поставленной задачи в ответах на Stackoverflow, касающихся данной задачи.

Так что можно смело игнорировать поставленный минус. Более того, автор минуса даже не оставил свой комментарий, объясняющий, что неверно в представленном ответе с точки зрения программирования. И уж, тем более, он мог бы оставить свой ответ на данный вопрос Ничего этого сделано не было.

Не секрет, что есть немало пользователей на Stackoverflow, которые при оценке вопросов и ответов руководствуются своими личными пристрастиями, не имеющими отношения к программированию.

Но вернемся к решению поставленной задачи.

Соответствующая демонстрационная программа, в которой показано, как реализовать стек в виде односвязного списка и функцию, проверяющую правильность расстановки парных круглых скобок, показана ниже.

 
 #include <stdio.h> 
 #include <stdlib.h> 
  
 struct stack 
 { 
 	char c; 
 	struct stack *next; 
 }; 
  
 char * top( struct stack **stack ) 
 { 
 	return *stack == NULL ? NULL : &( *stack )->c; 
 } 
  
 int push( struct stack **stack, char c ) 
 { 
 	struct stack *current = malloc( sizeof( struct stack ) ); 
 	int success = current != NULL; 
 	 
 	if ( success ) 
 	{ 
 		current->c = c; 
 		current->next = *stack; 
 		 
 		*stack = current; 
 	} 
  
 	return success; 
 } 
  
 void pop( struct stack **stack ) 
 { 
 	if ( *stack ) 
 	{ 
 		struct stack *current = *stack; 
 		*stack = ( *stack )->next; 
 		 
 		free( current ); 
 	} 
 } 
  
 int empty( struct stack **stack ) 
 { 
 	return *stack == NULL; 
 } 
  
 void clear( struct stack **stack ) 
 { 
 	while ( *stack ) pop( stack ); 
 } 
  
 int bracket_balance( const char *s ) 
 { 
 	struct stack *stack = NULL; 
 	 
 	int balanced = 1; 
 	 
 	for ( ; *s && balanced; ++s ) 
 	{ 
 		if ( *s == '(' ) 
 		{ 
 			push( &stack, *s ); 
 		} 
 		else if ( *s == ')' ) 
 		{ 
 			if ( ( balanced = !empty( &stack ) && *top( &stack ) == '(' ) ) 
 			{ 
 				pop( &stack ); 
 			} 
 		} 
 	} 
 	 
 	balanced = balanced && empty( &stack ); 
 	 
 	clear( &stack ); 
 	 
 	return balanced; 
 } 
  
 int main(void)  
 { 
 	const char * s[] =  
 	{ 
 		"", "(", ")", "()", ")(", "( ( ) )", "( )( )", "( ) ) (", "Hello" 
 	}; 
 	 
 	for ( size_t i = 0; i < sizeof( s ) / sizeof( *s ); i++ ) 
 	{ 
 		if ( bracket_balance( s ) ) 
 		{ 
 			printf( "\"%s\" has balanced brackets\n", s ); 
 		} 
 		else 
 		{ 
 			printf( "\"%s\" does not have balanced brackets\n", s ); 
 		} 
 	}		 
  
 	return 0; 
 }

Вывод программы на консоль:

 
 "" has balanced brackets 
 "(" does not have balanced brackets 
 ")" does not have balanced brackets 
 "()" has balanced brackets 
 ")(" does not have balanced brackets 
 "( ( ) )" has balanced brackets 
 "( )( )" has balanced brackets 
 "( ) ) (" does not have balanced brackets 
 "Hello" has balanced brackets

Как показывают вопросы на Stackoverflow, обычно главную трудность для начинающих программистов составляет реализация односвязного списка без использования глобальных переменных, а также передача указателей в функции по ссылке.

Думаю, что данная созданная тема будет в любом случае полезна начинающим программистам, кто приступает к изучению языка C на примере реализации односвязных списков и стеков.