Last Updated on May 12, 2023 by Prepbytes
Function calls and function parameters are represented by special symbols called parenthesis. Braces() indicate the beginning and end of a block of code that contains more than one executable statement. A parenthesis is represented as ‘()’, where ‘(‘ denotes the opening brace and ‘)’ denotes the closing braces.
What is a Balanced Parenthesis?
The term "balanced parenthesis" means that when the opening and closing parenthesis are equal, it is a balanced parenthesis.
Example of Balanced Parenthesis
-
*Eg 1: ( 2+5 ) 4**
There is one opening and one closing parenthesis in the preceding expression, indicating that both opening and closing brackets are equal; thus, the preceding expression is a balanced parenthesis. -
*Eg 2: 1 ( ( 3/9 ) + 10 )**
The above expression has two opening and two closing brackets, indicating that it is a balanced parenthesis. -
*Eg 3: 5 ( ( 6/8 ) + 2**
The above expression is unbalanced because it has two opening brackets and one closing bracket.
Algorithm to Check the Balanced Parenthesis
Let us now look at how we can tell if the parentheses are balanced or not.
- Make a framework for the character stack.
- Examine the expression string exp.
- If the current character is a starting bracket (‘(‘ or ” or ‘[‘), it is pushed to the stack.
- Remove the current character from the stack if it is a closing bracket (‘)’, ”, or ‘]’; otherwise, the brackets are not balanced if the popped character is the matching starting bracket.
- If there is any beginning bracket remaining in the stack after traversal, then "NOT BALANCED" is returned.
Code Implementation of Balanced Parenthesis in C
We will discuss two methods, one with a global stack and another with a dynamically created stack.
Code implementation of Balanced Parenthesis Using a Global Stack in C
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
struct stack {
char stck[MAX];
int top;
}s;
void push(char item) {
if (s.top == (MAX - 1))
printf("Stack Full\n");
else {
s.top = s.top + 1;
s.stck[s.top] = item;
}
}
void pop() {
if (s.top == -1)
printf("Stack Empty\n");
else
s.top = s.top - 1;
}
int checkPair(char val1,char val2){
return (( val1=='(' && val2==')' )||( val1=='[' && val2==']' )||( val1=='{' && val2=='}' ));
}
int checkBalanced(char expr[], int len){
for (int i = 0; i < len; i++)
{
if (expr[i] == '(' || expr[i] == '[' || expr[i] == '{')
{
push(expr[i]);
}
else
{
if (s.top == -1)
return 0;
else if(checkPair(s.stck[s.top],expr[i]))
{
pop();
continue;
}
return 0;
}
}
return 1;
}
int main() {
char exp[MAX] = "({})[]{}";
int i = 0;
s.top = -1;
int len = strlen(exp);
checkBalanced(exp, len)?printf("Balanced"): printf("Not Balanced");
return 0;
}
Output:
User Input : ({})[]{}
Output Terminal : Balanced Code Implementation of Balanced Parenthesis Using a Dynamically Created Stack in C
#include <stdio.h>
#include <stdlib.h>
#include <ctype.h>
#include <math.h>
#include <string.h>
#include <stdbool.h>
#include <limits.h>
#define MAX 100
struct Stack {
int top;
int maxSize;
char* array;
};
struct Stack* create(char max)
{
struct Stack* stack = (struct Stack*)malloc(sizeof(struct Stack));
stack->maxSize = max;
stack->top = -1;
stack->array = (char*)malloc(stack->maxSize * sizeof(char));
return stack;
}
int isFull(struct Stack* stack)
{
if(stack->top == stack->maxSize - 1){
printf("Will not be able to push maxSize reached\n");
}
return stack->top == stack->maxSize - 1;
}
int isEmpty(struct Stack* stack)
{
return stack->top == -1;
}
void push(struct Stack* stack, char item)
{
if (isFull(stack))
return;
stack->array[++stack->top] = item;
}
char pop(struct Stack* stack)
{
if (isEmpty(stack))
return '\0';
return stack->array[stack->top--];
}
int peek(struct Stack* stack)
{
if (isEmpty(stack))
return INT_MIN;
return stack->array[stack->top];
}
bool checkPair(char val1, char val2){
return (( val1=='(' && val2==')' )||( val1=='[' && val2==']' )||( val1=='{' && val2=='}' ));
}
bool checkBalanced(struct Stack* stack, char expr[], int len){
for (int i = 0; i < len; i++)
{
if (expr[i] == '(' || expr[i] == '[' || expr[i] == '{')
{
push(stack, expr[i]);
}
else
{
if (isEmpty(stack))
return false;
char topValue = pop(stack);
if(!checkPair(topValue, expr[i]))
return false;
}
}
return isEmpty(stack);
}
int main() {
char exp[MAX] = "({})[]";
int len = strlen(exp);
struct Stack* stack = create(len);
checkBalanced(stack, exp, len) ? printf("Balanced") : printf("Not Balanced");
return 0;
}
Output:
User Input : ({})[]
Output Terminal : Balanced Conclusion
We’ve learned that in programming, balanced parentheses are required to indicate the beginning and end of a block of code. This article discussed parentheses and balanced parentheses, as well as examples of both. The article then went on to explain how to use an algorithm to determine whether or not parentheses are balanced and provided two C implementation methods, one with a global stack and the other with a dynamically created stack. It is critical to check for balanced parentheses to avoid compilation errors and ensure proper code execution.
Frequently Asked Questions (FAQs)
Q1. Can parentheses be used in C?
Ans. Most modern languages have adopted the C language pattern of using parentheses: ( ) Use for functions. [ ] Use for arrays. { } Use for blocks.
Q2. What is the purpose of the parenthesis?
Ans. Because they can be used to change the precedence of another operator in an expression, parentheses are also known as precedence operators.
Q3. In C, when should you use []?
Ans. Arrays are used to store multiple values in a single variable rather than declaring separate variables for each value. In square brackets [], specify the data type (such as int) and the array name to create an array.
Q4. What do the () brackets stand for?
Ans. Parentheses, square brackets, curly brackets, and angle brackets are all examples.