In programming, parentheses (or brackets) are often used to group expressions, define function calls, or indicate blocks of code. Ensuring that every opening parenthesis has a matching closing parenthesis is crucial. Unbalanced parentheses can cause compilation errors or runtime bugs. One efficient way to check balanced parentheses is by using a stack, a data structure that follows Last In, First Out (LIFO) principle. This article explains how to implement such a check in C with examples and best practices.
Understanding the Problem
A balanced expression is one in which every opening parenthesis '(', '{', or '[' is matched by the correct closing parenthesis ')', '}', or ']'. Proper nesting is also required, meaning a closing parenthesis must correspond to the most recent unmatched opening parenthesis. This problem is common in compilers, interpreters, and text editors, making it an essential algorithm to understand.
Program 1: Using Stack Implemented with Array
This approach uses a fixed-size array to implement the stack. Each opening parenthesis is pushed onto the stack, and each closing parenthesis is matched against the top of the stack.
#include <stdio.h>
#include <stdlib.h>
#define MAX 100
char stack[MAX];
int top = -1;
void push(char c) {
if (top < MAX - 1) {
stack[++top] = c;
}
}
char pop() {
if (top >= 0) {
return stack[top--];
}
return '\0';
}
int isMatchingPair(char open, char close) {
if (open == '(' && close == ')') return 1;
if (open == '{' && close == '}') return 1;
if (open == '[' && close == ']') return 1;
return 0;
}
int isBalanced(char exp[]) {
for (int i = 0; exp[i] != '\0'; i++) {
char c = exp[i];
if (c == '(' || c == '{' || c == '[') {
push(c);
} else if (c == ')' || c == '}' || c == ']') {
if (top == -1 || !isMatchingPair(pop(), c)) {
return 0;
}
}
}
return top == -1;
}
int main() {
char expression[MAX];
printf("Enter an expression: ");
scanf("%s", expression);
if (isBalanced(expression)) {
printf("The expression is balanced.\n");
} else {
printf("The expression is not balanced.\n");
}
return 0;
}This program iterates through each character in the expression. Opening parentheses are pushed onto the stack, while closing parentheses are matched against the top of the stack. If there is a mismatch or the stack is not empty at the end, the expression is considered unbalanced.
Program 2: Using Stack Implemented with Linked List
For expressions of unknown or very large length, a dynamic stack using a linked list is more efficient. It avoids the fixed size limitation of arrays and can grow as needed.
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
char data;
struct Node *next;
} Node;
Node* push(Node *top, char c) {
Node *newNode = (Node*)malloc(sizeof(Node));
newNode->data = c;
newNode->next = top;
top = newNode;
return top;
}
Node* pop(Node *top, char *c) {
if (top) {
*c = top->data;
Node *temp = top;
top = top->next;
free(temp);
return top;
}
*c = '\0';
return NULL;
}
int isMatchingPair(char open, char close) {
if (open == '(' && close == ')') return 1;
if (open == '{' && close == '}') return 1;
if (open == '[' && close == ']') return 1;
return 0;
}
int isBalanced(char exp[]) {
Node *stack = NULL;
char popped;
for (int i = 0; exp[i] != '\0'; i++) {
char c = exp[i];
if (c == '(' || c == '{' || c == '[') {
stack = push(stack, c);
} else if (c == ')' || c == '}' || c == ']') {
if (!stack || !isMatchingPair(stack->data, c)) {
return 0;
}
stack = pop(stack, &popped);
}
}
return stack == NULL;
}
int main() {
char expression[100];
printf("Enter an expression: ");
scanf("%s", expression);
if (isBalanced(expression)) {
printf("The expression is balanced.\n");
} else {
printf("The expression is not balanced.\n");
}
return 0;
}This program uses dynamic memory allocation to create a stack that can grow with the input. Each opening parenthesis is added to the stack, and each closing parenthesis is checked against the most recent element. Memory is freed as elements are popped, making it efficient for long expressions.
FAQs
Q1: Can this program handle nested parentheses?
Yes, the stack ensures that the most recently opened parenthesis is matched first, correctly handling nested and complex structures.
Q2: Can we use a linked list for the stack instead of an array?
Absolutely. Using a linked list allows the stack to grow dynamically and removes the fixed-size limitation of arrays.
Q3: What if the input contains characters other than parentheses?
The program ignores non-parenthesis characters, processing only (), {}, and [].
Q4: Is this method efficient for long expressions?
Yes, both array and linked-list implementations have a time complexity of O(n), where n is the length of the expression. Linked lists are preferred for extremely long inputs due to their dynamic memory allocation.
Conclusion
Checking balanced parentheses using a stack is a fundamental technique in programming. The array-based implementation works well for expressions with known or limited length, while a linked-list implementation provides flexibility for larger inputs. By handling edge cases carefully and avoiding common mistakes, you can ensure that your program correctly identifies balanced and unbalanced expressions.
References & Additional Resources
A curated collection of textbooks and tutorials for learning stacks, their applications, and implementation in C.
- Kernighan, B. W., & Ritchie, D. M. (1988). The C Programming Language (2nd Edition). Prentice Hall – The classic text covering C fundamentals, including pointers and memory handling essential for stack implementation.
- Thareja, R. (2011). Data Structures Using C. Oxford University Press – Comprehensive coverage of stack data structures, algorithms, and their implementations in C.
- TutorialsPoint: Stack Data Structure – Explains the stack concept, operations, and algorithms.
- GeeksforGeeks: Balanced Parentheses Problem – Demonstrates stack applications in solving real-world problems.
- Programiz: Stack Implementation in C – Practical guide with C examples of stack operations and usage.
- GeeksforGeeks: Stack Data Structure – In-depth explanation of stack concepts, use cases, and variations.
- C Standard Library Documentation – Official reference for C libraries, functions, and memory operations.
