125 views
Balanced Parenthesis in C
Checking for balanced parentheses in an expression is a common problem in computer science and programming. You can use a stack data structure to implement a C program that checks whether a given expression has balanced parentheses. Here’s a simple example:
C
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
// Define a structure for the stack
struct Stack {
char data;
struct Stack* next;
};
// Function to create a new stack node
struct Stack* newNode(char data) {
struct Stack* stackNode = (struct Stack*)malloc(sizeof(struct Stack));
stackNode->data = data;
stackNode->next = NULL;
return stackNode;
}
// Function to check if a character is an opening parenthesis
bool isOpeningParenthesis(char ch) {
return (ch == '(' || ch == '{' || ch == '[');
}
// Function to check if two characters form a matching pair of parentheses
bool areMatching(char opening, char closing) {
return ((opening == '(' && closing == ')') ||
(opening == '{' && closing == '}') ||
(opening == '[' && closing == ']'));
}
// Function to check for balanced parentheses in an expression
bool isBalanced(char expression[]) {
struct Stack* stack = NULL;
for (int i = 0; expression[i]; i++) {
if (isOpeningParenthesis(expression[i])) {
struct Stack* newNode = newNode(expression[i]);
newNode->next = stack;
stack = newNode;
} else {
if (stack == NULL || !areMatching(stack->data, expression[i])) {
return false;
}
struct Stack* temp = stack;
stack = stack->next;
free(temp);
}
}
return (stack == NULL);
}
int main() {
char expression[100];
printf("Enter an expression: ");
fgets(expression, sizeof(expression), stdin);
if (isBalanced(expression)) {
printf("The expression has balanced parentheses.\n");
} else {
printf("The expression does not have balanced parentheses.\n");
}
return 0;
}
In this program:
- We define a
struct Stack
to represent a stack data structure for storing opening parentheses. - The
newNode
function creates a new stack node with the given character. - The
isOpeningParenthesis
function checks if a character is an opening parenthesis. - The
areMatching
function checks if two characters form a matching pair of parentheses. - The
isBalanced
function checks for balanced parentheses by using a stack to keep track of opening parentheses and matching them with closing parentheses. - In the
main
function, the user inputs an expression, and we call theisBalanced
function to check if the expression has balanced parentheses.
Compile and run the program, and it will tell you whether the input expression has balanced parentheses or not.