For each line, print yes if its brackets ( ) [ ] { } are balanced and no if they are not. Every bracket must be closed by the same kind, in the right order. Other characters are ignored.
What to build
A bracket checker that uses a stack of characters.
Requirements
- Push each opening bracket.
- For each closing bracket, the top of the stack must be the matching opening bracket.
- The stack must be empty at the end of the line.
Input
The first line has q (1 ≤ q ≤ 100). Each of the next q lines has a string of 1 to 100 characters with no spaces.
Output
yes or no for each line.
Constraints
1 ≤ q ≤ 100, and each line has 1 to 100 characters with no spaces.
Example
Input:
3
{a[(b)]}
(a]
((
Output:
yes
no
no
Why it works
The bracket opened most recently has to be closed first, and a stack always gives back the most recent item.
Examples
Example 1 · Input
3
{a[(b)]}
(a]
((
Expected output
yes no no
Example 2 · Input
2
)(
[]{}()
Expected output
no yes
Hints
Hint 1
Push every opening bracket on a stack of chars.
Hint 2
A closing bracket needs a matching opening bracket on top: pop it and compare.
Hint 3
At the end of the line the stack must be empty.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
#include <stdbool.h>
bool balanced(const char *s) {
char st[101];
int top = -1;
for (int i = 0; s[i] != '\0'; i++) {
char c = s[i];
if (c == '(' || c == '[' || c == '{') {
st[++top] = c;
} else if (c == ')' || c == ']' || c == '}') {
if (top == -1) return false;
char open = st[top--];
if ((c == ')' && open != '(') || (c == ']' && open != '[') || (c == '}' && open != '{')) return false;
}
}
return top == -1;
}
int main(void) {
int q;
scanf("%d", &q);
for (int i = 0; i < q; i++) {
char s[101];
scanf("%100s", s);
printf("%s\n", balanced(s) ? "yes" : "no");
}
return 0;
}