Balanced parentheses and Reversing list
To check for balanced parentheses in C, a Stack data
structure is used to ensure every opening bracket has a matching closing
bracket in the correct order
Algorithm
- Initialize an
empty stack.
- Traverse the
expression:
Push opening brackets
((, {, [) onto the stack.
Pop and check for
matches if a closing bracket (), }, ]) appears.
If the stack is empty at a
closing bracket, or if a match fails, the expression is not balanced.
- Final
Check: The expression is balanced only if the stack is empty at the
end.
Program:
#include <stdio.h>
#include <string.h>
#define MAX 100
char stack[MAX];
int top = -1;
// Push function
void push(char c)
{
if (top == MAX - 1)
{
printf("Stack
overflow\n");
return;
}
stack[++top] = c;
}
// Pop function
char pop()
{
if (top == -1)
{
return '\0';
}
return stack[top--];
}
// Function to check matching pair
int isMatchingPair(char open, char close)
{
if (open
== '(' && close == ')')
return 1;
if (open
== '{' && close == '}')
return 1;
if (open
== '[' && close == ']')
return 1;
return
0;
}
// Function to check balance
int isBalanced(char expr[])
{
for (int i = 0; i < strlen(expr); i++)
{
char ch = expr[i];
// If opening bracket, push
if (ch == '(' || ch == '{'
|| ch == '[')
{
push(ch);
}
// If closing bracket
else if (ch == ')' || ch ==
'}' || ch == ']')
{
char popped = pop();
if (popped == '\0' || !isMatchingPair(popped,
ch))
{
return
0; // Not balanced
}
}
}
return (top == -1); // Balan
}
// Main function
int main()
{
char expr[MAX];
printf("Enter expression:
");
scanf("%s", expr);
if (isBalanced(expr))
printf("Balanced
Parentheses\n");
else
printf("Not
Balanced\n");
return
0;
}
Reversing a list:
#include <stdio.h>
#define MAX 100
int stack[MAX];
int top = -1;
void push(int x)
{
if
(top == MAX - 1)
printf("Stack
Overflow\n");
else
stack[++top] = x;
}
int pop()
{
if
(top == -1)
printf("Stack
Underflow\n");
else
return stack[top--];
}
void reverse(int arr[],
int n)
{
for
(int i = 0; i < n; i++)
{
push(arr[i]);
}
for
(int i = 0; i < n; i++)
{
arr[i]
= pop();
}
}
int main()
{
int
arr[],n;
printf("Enter size of the array ");
scanf("%d
", &n);
printf("Enter
array values ");
for
(int i = 0; i < n; i++)
{
scanf("%d
", &arr[i]);
}
reverse(arr,
n);
printf("Reversed
array: ");
for
(int i = 0; i < n; i++)
{
printf("%d
", arr[i]);
}
return
0;
}
Comments
Post a Comment