fork download
copy 
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <stdbool.h>
  5.  
  6. #define INITIAL_SIZE 10
  7. #define EMPTY -1
  8.  
  9. struct Stack
  10. {
  11. 	int* arr;
  12. 	int currSize;
  13. 	int top;
  14. };
  15.  
  16. typedef struct Stack Stack;
  17.  
  18. /* Global char arrays for opening and closing brackets */
  19. char openBrackets[] = {'(','{','[','\0'};
  20. char closeBrackets[] = {')','}',']','\0'};
  21.  
  22.  
  23. Stack* StackCreate(){
  24. 	Stack* stack = malloc(sizeof(Stack));
  25. 	if(stack == NULL)
  26. 	{
  27. 		return NULL;
  28. 	}
  29. 	stack->arr = malloc(INITIAL_SIZE * sizeof(int));
  30. 	if(stack->arr == NULL)
  31. 	{
  32. 		free(stack);
  33. 		return NULL;
  34. 	}
  35. 	stack->currSize = INITIAL_SIZE;
  36. 	stack->top = EMPTY;
  37.  
  38. 	return stack;
  39. }
  40.  
  41. void Push(Stack* _stack, int _item){
  42. 	if(_stack == NULL)
  43. 	{
  44. 		return;
  45. 	}
  46. 	if(_stack->top == (_stack->currSize - 1))
  47. 	{
  48. 		// printf("Stack is full with %d items.\nTrying to reallocating stack to size: %d\n", _stack->currSize, 2*_stack->currSize);
  49. 		int* temp = (int*)realloc(_stack->arr, 2 * (_stack->currSize) * sizeof(int));
  50. 		if(temp == NULL)
  51. 		{
  52. 			printf("Reallocating failed!\n");
  53. 			return;
  54. 		}
  55. 		_stack->arr = temp;
  56. 		_stack->currSize = 2 * (_stack->currSize);
  57. 		// printf("Stack reallocation succeeded.\nCurrent stack size: %d\n", _stack->currSize);
  58. 	}
  59.  
  60. 	_stack->top++;
  61. 	_stack->arr[_stack->top] = _item;
  62. }
  63.  
  64. void Pop(Stack* _stack){
  65. 	if(_stack == NULL)
  66. 	{
  67. 		return;
  68. 	}
  69. 	if(_stack->top == EMPTY)
  70. 	{
  71. 		printf("Pop::Stack is empty\n");
  72. 		return;
  73. 	}
  74.  
  75. 	_stack->top--;
  76. }
  77.  
  78. int Top(Stack* _stack){
  79. 	if(_stack == NULL)
  80. 	{
  81. 		return EMPTY;
  82. 	}
  83. 	if(_stack->top == EMPTY)
  84. 	{
  85. 		printf("Top::Stack is empty\n");
  86. 		return EMPTY;
  87. 	}
  88. 	// printf("Top::Stack top: %c\n", _stack->arr[_stack->top]);
  89. 	return _stack->arr[_stack->top];
  90. }
  91.  
  92. void PrintStack(Stack* _stack){
  93. 	printf("PrintStack\n***********\n");
  94. 	int i;
  95. 	if(_stack == NULL) {
  96. 		return;
  97. 	}
  98. 	printf("Current stack size: %d, Current top index: %d\n", _stack->currSize,_stack->top);
  99. 	if(_stack->top == EMPTY) {
  100. 		printf("PrintStack::Stack is empty\n");
  101. 		return;
  102. 	}
  103. 	printf("Stack content:\n--------------\n");
  104. 	for(i = 0; i <= _stack->top; i++) {
  105. 		printf("%c ", _stack->arr[i]);
  106. 	}
  107. 	printf("\n");
  108. }
  109.  
  110. bool isOpenBracket(int _item) {
  111. 	int i = 0;
  112. 	// printf("isOpenBracket:: _item: %c\n", _item);
  113. 	while(openBrackets[i] != '\0') {
  114. 		if(openBrackets[i] == _item) {
  115. 			return true;
  116. 		}
  117. 		i++;
  118. 	}
  119.  
  120. 	return false;
  121. }
  122.  
  123. bool isCloseBracket(int _item, int *_openBracket) {
  124. 	int i = 0;
  125. 	while(closeBrackets[i] != '\0')
  126. 	{
  127. 		if(closeBrackets[i] == _item)
  128. 		{
  129. 			*_openBracket = openBrackets[i];
  130. 			return true;
  131. 		}
  132. 		i++;
  133. 	}
  134.  
  135. 	return false;
  136. }
  137.  
  138.  
  139. bool BalancedBrackets(char* _string){
  140. 	int i, _topBracket, _openBracket;
  141. 	Stack* stack = StackCreate();
  142.  
  143. 	for(i = 0; _string[i] != '\0'; i++) {
  144. 		if(isOpenBracket(_string[i])) {
  145. 			Push(stack, _string[i]);
  146. 		}
  147. 		if(isCloseBracket(_string[i], &_openBracket)) {
  148. 			_topBracket = Top(stack);
  149. 			// printf("BalancedBrackets:: _openBracket: %c\n", _openBracket);
  150. 			if(_topBracket == EMPTY) {
  151. 				return false;
  152. 			}
  153. 			if(_topBracket != _openBracket) {
  154. 				return false;
  155. 			}
  156. 			Pop(stack);			
  157. 		}
  158. 	}
  159.  
  160. 	if(stack->top != EMPTY)
  161. 	{
  162. 		return false;
  163. 	}
  164.  
  165. 	return true;
  166. }
  167.  
  168. void TestBalancedBrackets(){
  169. 	char str1[] = "if(a+{2*max(A[],5)}>7)";				//PASS
  170. 	char str2[] = "if(a+{2*max(A[],5)}>7)(";			//FAIL
  171. 	char str3[] = "}if(a+{2*max(A[],5)}>7)";			//FAIL
  172. 	char str4[] = "if(a+{2*max)(A[],5)}>7)";			//FAIL
  173. 	char str5[] = "if(a+{2*max(A[],5)}>7){([])}";		//PASS
  174. 	char str6[] = "if(a+{2*max})(A[],5)}>7)";			//FAIL
  175. 	char str7[] = "(({[{[[]]}]}))";						//PASS
  176. 	char str8[] = "(({[{[[]}]}]}))";					//FAIL
  177. 	char str9[] = "}(({[{[[]]}]}))";					//FAIL
  178. 	char str10[] = "(({[{[[]]}]})){[]}";				//PASS
  179. 	char str11[] = "(({[{[[]]}]})))";					//FAIL
  180. 	char str12[] = "((({[{[[]]}]}))";					//FAIL
  181. 	char str13[] = "%5****435,.<>)()";					//FAIL
  182.  
  183. 	if(BalancedBrackets(str1) == true)
  184. 	{
  185. 		printf("Test string1: %s has balanced brackets ---> PASS\n", str1);
  186. 	}
  187. 	else
  188. 	{
  189. 		printf("Test string1: %s ---> FAILED\n", str1);
  190. 	}
  191. 	if(BalancedBrackets(str2) == false)
  192. 	{
  193. 		printf("Test string2: %s does NOT have balanced brackets ---> PASS\n", str2);
  194. 	}
  195. 	else
  196. 	{
  197. 		printf("Test string2: %s ---> FAILED\n", str2);
  198. 	}
  199. 	if(BalancedBrackets(str3) == false)
  200. 	{
  201. 		printf("Test string3: %s does NOT have balanced brackets ---> PASS\n", str3);
  202. 	}
  203. 	else
  204. 	{
  205. 		printf("Test string3: %s ---> FAILED\n", str3);
  206. 	}
  207. 	if(BalancedBrackets(str4) == false)
  208. 	{
  209. 		printf("Test string4: %s does NOT have balanced brackets ---> PASS\n", str4);
  210. 	}
  211. 	else
  212. 	{
  213. 		printf("Test string4: %s ---> FAILED\n", str4);
  214. 	}
  215. 	if(BalancedBrackets(str5) == true)
  216. 	{
  217. 		printf("Test string5: %s has balanced brackets ---> PASS\n", str5);
  218. 	}
  219. 	else
  220. 	{
  221. 		printf("Test string5: %s ---> FAILED\n", str5);
  222. 	}
  223. 	if(BalancedBrackets(str6) == false)
  224. 	{
  225. 		printf("Test string6: %s does NOT have balanced brackets ---> PASS\n", str6);
  226. 	}
  227. 	else
  228. 	{
  229. 		printf("Test string6: %s ---> FAILED\n", str6);
  230. 	}
  231. 	if(BalancedBrackets(str7) == true)
  232. 	{
  233. 		printf("Test string7: %s has balanced brackets ---> PASS\n", str7);
  234. 	}
  235. 	else
  236. 	{
  237. 		printf("Test string7: %s ---> FAILED\n", str7);
  238. 	}
  239. 	if(BalancedBrackets(str8) == false)
  240. 	{
  241. 		printf("Test string8: %s does NOT have balanced brackets ---> PASS\n", str8);
  242. 	}
  243. 	else
  244. 	{
  245. 		printf("Test string8: %s ---> FAILED\n", str8);
  246. 	}
  247. 	if(BalancedBrackets(str9) == false)
  248. 	{
  249. 		printf("Test string9: %s does NOT have balanced brackets ---> PASS\n", str9);
  250. 	}
  251. 	else
  252. 	{
  253. 		printf("Test string9: %s ---> FAILED\n", str9);
  254. 	}
  255. 	if(BalancedBrackets(str10) == true)
  256. 	{
  257. 		printf("Test string10: %s has balanced brackets ---> PASS\n", str10);
  258. 	}
  259. 	else
  260. 	{
  261. 		printf("Test string10: %s ---> FAILED\n", str10);
  262. 	}
  263. 	if(BalancedBrackets(str11) == false)
  264. 	{
  265. 		printf("Test string11: %s does NOT have balanced brackets ---> PASS\n", str11);
  266. 	}
  267. 	else
  268. 	{
  269. 		printf("Test string11: %s ---> FAILED\n", str11);
  270. 	}
  271. 	if(BalancedBrackets(str12) == false)
  272. 	{
  273. 		printf("Test string12: %s does NOT have balanced brackets ---> PASS\n", str12);
  274. 	}
  275. 	else
  276. 	{
  277. 		printf("Test string12: %s ---> FAILED\n", str12);
  278. 	}
  279. 	if(BalancedBrackets(str13) == false)
  280. 	{
  281. 		printf("Test string13: %s does NOT have balanced brackets ---> PASS\n", str13);
  282. 	}
  283. 	else
  284. 	{
  285. 		printf("Test string13: %s ---> FAILED\n", str13);
  286. 	}
  287. }
  288.  
  289. int main()
  290. {
  291. 	TestBalancedBrackets();
  292.  
  293. 	return 0;
  294. }
Success #stdin #stdout 0s 9416KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Test string1: if(a+{2*max(A[],5)}>7) has balanced brackets ---> PASS
Test string2: if(a+{2*max(A[],5)}>7)( does NOT have balanced brackets ---> PASS
Top::Stack is empty
Test string3: }if(a+{2*max(A[],5)}>7) does NOT have balanced brackets ---> PASS
Test string4: if(a+{2*max)(A[],5)}>7) does NOT have balanced brackets ---> PASS
Test string5: if(a+{2*max(A[],5)}>7){([])} has balanced brackets ---> PASS
Top::Stack is empty
Test string6: if(a+{2*max})(A[],5)}>7) does NOT have balanced brackets ---> PASS
Test string7: (({[{[[]]}]})) has balanced brackets ---> PASS
Test string8: (({[{[[]}]}]})) does NOT have balanced brackets ---> PASS
Top::Stack is empty
Test string9: }(({[{[[]]}]})) does NOT have balanced brackets ---> PASS
Test string10: (({[{[[]]}]})){[]} has balanced brackets ---> PASS
Top::Stack is empty
Test string11: (({[{[[]]}]}))) does NOT have balanced brackets ---> PASS
Test string12: ((({[{[[]]}]})) does NOT have balanced brackets ---> PASS
Top::Stack is empty
Test string13: %5****435,.<>)() does NOT have balanced brackets ---> PASS
https://ideone.com/bninkl
language:
C (gcc 8.3)
created:
7 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!