BALANCING PARANTHESIS USING STACK:
A bracket is considered to be any one of the following characters: (, ), {, }, [, or ].Two brackets are considered to be a matched pair if the an opening bracket (i.e., (, [, or () occurs to the left of a closing bracket (i.e., ), ], or }) of the exact same type. There are three types of matched pairs of brackets: []}, and ().A matching pair of brackets is not balanced if the set of brackets it encloses are not matched. For example, {[()} is not balanced because the contents in between { and } are not balanced. The pair of square brackets encloses a single, unbalanced opening bracket, (, and the pair of parentheses encloses a single, unbalanced closing square bracket, ].
By this logic, we say a sequence of brackets is balanced if the following conditions are met:
• It contains no unmatched brackets.
• The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets.
Given n strings of brackets, determine whether each sequence of brackets is balanced. If a string is balanced, return YES. Otherwise, return NO.
Function Description
Complete the function isBalanced in the editor below. It must return a string: YES if the sequence is balanced or NO if it is not.
isBalanced has the following parameter(s):
⚫s: a string of brackets
Input Format
The first line contains a single integer n, the number of strings. Each of the next n lines contains a single string s, a sequence of brackets.
Constraints
1≤ n ≤10 3
1 Isl≤ 103,where Is is the length of the sequence.
Output Format
For each string, return YES or NO.
Sample Input
3
{[()]}
{[([[()]])}
{[()]}
Sample Output
YES
NO
YES
Sample input
3
{[()]}
{[(])}
{{[[(())]]}}
Sample output
YES
NO
Program:
#include <stdio.h>
#include <string.h>
#define MAX_LEN 1000
int isPairBalanced(char opening, char closing) {
if (opening == '(' && closing == ')')
return 1;
else if (opening == '{' && closing == '}')
return 1;
else if (opening == '[' && closing == ']')
return 1;
else
return 0;
}
char* isBalanced(char* s) {
int len = strlen(s);
char stack[MAX_LEN];
int top = -1;
for (int i = 0; i < len; i++) {
if (s[i] == '(' || s[i] == '{' || s[i] == '[')
stack[++top] = s[i];
else if (s[i] == ')' || s[i] == '}' || s[i] == ']') {
if (top == -1 || !isPairBalanced(stack[top], s[i]))
return "NO";
else
top--;
}
}
if (top == -1)
return "YES";
else
return "NO";
}
int main() {
int n;
char s[MAX_LEN];
scanf("%d", &n);
for (int i = 0; i < 2; i++) {
scanf("%s", s);
printf("%s\n", isBalanced(s));
}
}
Explanation:
Program that checks if a given string containing brackets (i.e., parentheses, curly braces, and square brackets) is balanced. The program reads in the number of test cases (n) and then for each test case, it reads in a string (s) and checks if the string is balanced. If the string is balanced, it prints "YES" to the console. Otherwise, it prints "NO" to the console.
Here's how the program works:
1.The first two lines of the program include the standard input/output library (stdio.h) and the string library (string.h).
2.The third line defines a constant value MAX_LEN as 1000.
3.The next function isPairBalanced takes two characters (opening and closing) and returns 1 if they form a balanced pair of brackets (i.e., ( and ), { and }, or [ and ]). Otherwise, it returns 0.
4.The next function isBalanced takes a string s and checks if it is balanced. It first calculates the length of the string and initializes a stack (implemented as an array) to hold opening brackets. The variable top keeps track of the top of the stack.
5.The function then loops over each character in the string. If the character is an opening bracket (i.e., (, {, or [), it pushes it onto the stack. If the character is a closing bracket (i.e., ), }, or ]), it checks if the top of the stack holds a matching opening bracket using the isPairBalanced function. If the brackets match, it pops the opening bracket from the stack. Otherwise, the function returns "NO".
6.After the loop, the function checks if the stack is empty. If it is, it returns "YES". Otherwise, it returns "NO".
7.The main function reads in the number of test cases (n) and then loops over each test case. For each test case, it reads in a string (s) and prints the result of the isBalanced function to the console.
Overall, this program implements a stack-based algorithm to check if a given string of brackets is balanced.
0 Comments