C Program To Check Balanced Parantheses using Stack Data Structure
Learn How To Check Balanced Parantheses using Stack Data Structure in C Programming Language. This C Program checks if Parantheses of an Expression are Balanced or Not using Stack Data Structure. If the parantheses do not match or if the Number is not even, then the expression will have unbalanced parantheses. This C Program checks Nesting of Parantheses in an Expression as well.
The parantheses used in an algebraic expression are: { [ ( and its matching Right parantheses. The Number of Paratheses should, therefore be even or in other words, the opening parantheses should be equivalent to the closing parantheses. For every opening bracket, there should be a similar closing bracket.
Algorithm To Check if Parantheses are Balanced or Not
- Declare A Stack
- Input Algebraic Expression from the User
- Traverse the Expression
- Push the Current Character to Stack if it is an Opening Parantheses such as (, [ or {.
- Pop the Current Character from Stack if the Expression has a Closing Bracket such as ), ] or }.
- If the Popped Character is matching the starting parantheses, then the Expression is Balanced else it includes Unbalanced Parantheses.
- After Traversal is completed, if there is any remaining Left Bracket in the Stack, then the Parantheses are not Balanced.
Must Read: C Program To Reverse a Stack String
C Program To Check Balanced Parantheses using Stack in an Algebraic Expression
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 | #include<stdio.h> #include<stdlib.h> #include<string.h> #define MAX 25 int top = -1; int stack[MAX]; void push(char item) { if(top == (MAX - 1)) { printf("Stack is Full\n"); return; } top++; stack[top] = item; } char pop() { if(top == -1) { printf("Stack is Empty\n"); exit(1); } return(stack[top--]); } int match_paranthesis(char a, char b) { if(a == '[' && b == ']') { return 1; } else if(a == '{' && b == '}') { return 1; } else if(a == '(' && b == ')') { return 1; } return 0; } int check_paranthesis(char expression[]) { int count; char temp; for(count = 0; count < strlen(expression); count++) { if(expression[count] == '(' || expression[count] == '{' || expression[count] == '[') { push(expression[count]); } if(expression[count] == ')' || expression[count] == '}' || expression[count] == ']') { if(top == -1) { printf("The Right Parentheses are more than the Left Parentheses\n"); return 0; } else { temp = pop(); if(!match_paranthesis(temp, expression[count])) { printf("The Mismatched Parentheses in the Expression are:\t%c and %c\n", temp, expression[count]); return 0; } } } } if(top == -1) { printf("\nThe Expression has Balanced Parentheses\n"); return 1; } else { printf("The Expression has unbalanced parentheses\n"); return 0; } } int main() { char expression[MAX]; int validity; printf("\nEnter an Algebraic Expression:\t"); scanf("%s", expression); validity = check_paranthesis(expression); if(validity == 1) { printf("The Expression is Valid\n"); } else { printf("The Expression is Invalid\n"); } return 0; } |
Output
If you have any compilation errors or doubts in this Data Structure Program to Find Balanced Parantheses in C Programming, let us know about in the Comment Section below. Find more about Stack and Queues on cs.cmu.edu.
Thanks for the algorithm! This is too good! It has helped me to understand the program code with much ease.
You have simplified the code for balanced parantheses. I finally could understand the logic now.
Simple and easy to understand.
Amazing Parantheses Checker C Program!
Helped a lot in understanding stack, Thank You!
Pleasure! 🙂