Check a line of round brackets, and measure how deeply they are nested.
What to build
A checker for round brackets that also reports the deepest nesting.
Requirements
- Print
balanced Dwhen the brackets match, whereDis the largest number of brackets open at one time. - Print
not balancedwhen a closing bracket has nothing to match, or a bracket is left open.
Input
One line of 1 to 100 characters, each ( or ).
Output
One line.
Constraints
The line has no spaces and no other characters.
Example
Input:
(()())
Output:
balanced 2
Why it works
The number of brackets open at any moment is the height of the stack a full checker would use. It may never go below zero, and it must be zero at the end.
Examples
Example 1 · Input
(()())
Expected output
balanced 2
Example 2 · Input
())(
Expected output
not balanced
Hints
Hint 1
With one kind of bracket, every item on the stack would be the same, so a counter can stand in for the stack.
Hint 2
Add one for an opening bracket. For a closing bracket, fail if the counter is 0, and otherwise subtract one.
Hint 3
Remember the largest value the counter reaches.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int main(void) {
char s[101];
scanf("%100s", s);
int depth = 0, deepest = 0, ok = 1;
for (int i = 0; s[i] != '\0' && ok; i++) {
if (s[i] == '(') {
depth++;
if (depth > deepest) deepest = depth;
} else {
if (depth == 0) ok = 0;
else depth--;
}
}
if (ok && depth == 0) printf("balanced %d\n", deepest);
else printf("not balanced\n");
return 0;
}