Intel interview question: Checking if a string with 3 diff parenthesis is balanced without using stack.
Well, first question was just to implement it and I did it with ease using stack. However, if I was asked implementing it without O(n) space, I believe I'd be stuck.
Requirements: O(1) Space, and as efficient as possible in time, which should be O(n).
How would you approach this question? 3 pointers, 3 counters?
It depends on the exact requirement. If you really only need balanced parantheses, an approach with three counters would work, e.g. like this:
#include <stdio.h>
int accept(char (*next)(void))
{
char x;
int b[3] = { 0 };
while ( (x = next()) )
{
switch (x)
{
case '{':
++b[0];
break;
case '[':
++b[1];
break;
case '(':
++b[2];
break;
case '}':
--b[0];
break;
case ']':
--b[1];
break;
case ')':
--b[2];
break;
}
if (b[0] < 0 || b[1] < 0 || b[2] < 0) return 0;
}
return (b[0] == 0 && b[1] == 0 && b[2] == 0);
}
char getnextchar(void)
{
int c = getchar();
if (c == EOF) return 0;
return (unsigned char)c;
}
int main(void)
{
puts(accept(getnextchar) ? "balanced" : "unbalanced");
return 0;
}
Note the getnextchar() function is only introduced for flexibility from where to get your string. You could simplify this to directly take a char * if you like.
If the requirement is that the nesting needs to be correct as well, the only option I can see without a stack in your program would be recursion. Of course, your implementation of C very likely uses a stack for function calls, so in practice, this is useless ... but hey, there's no stack in your program! Example:
#include <stdio.h>
int accept(char (*next)(void), char c)
{
char x;
int ok = 1;
while ( (x = next()) )
{
switch (x)
{
case '{':
ok = accept(next, '}');
break;
case '[':
ok = accept(next, ']');
break;
case '(':
ok = accept(next, ')');
break;
case '}':
case ']':
case ')':
return x == c;
}
if (!ok) return 0;
}
return !c;
}
char getnextchar(void)
{
int c = getchar();
if (c == EOF) return 0;
return (unsigned char)c;
}
int main(void)
{
puts(accept(getnextchar, 0) ? "balanced" : "unbalanced");
return 0;
}
You cannot even count one kind of parentheses in honest O(1) space because you need log(n) bits for the counter.
If you can cheat and pretend integers take O(1) space, you can build a stack within a single integer. For example, pretend that [ is 0, ( is 1 and { is 2 and represent your stack contents as a base 3 number. Naturally this requires integers with O(n) bits rather than O(log(n)) bits as with one kind of parentheses.
It is actually possible to do better: there is a O(log(n)) space algorithm (pdf) due to Ritchie and Springsteel, but it's a serious CS-theoretic work, you are not supposed to discover anything like that during a job interview.
Edit If you can modify the input string, there's a simple solution that uses the scanned portion of the string for storage, as in the answer by @jxh.
O(n) does not mean a single pass. Scanning backwards to find the previous open parentheses certainly has to be considered "not a stack". To deal with the portions of the string that are "dead zones" because they are closed off, the algorithm can move newly encountered open parentheses backwards, overwriting the dead zones.
Some pseudocode:
bool matched_parens (char *s) {
char *p = s;
char *cur_open = s;
if (s == NULL || *s == '\0') return true;
if (!IS_OPEN(*s)) return false;
while (*++p) {
if (IS_OPEN(*p)) {
*++cur_open = *p;
continue;
}
if (!IS_MATCHED(*cur_open, *p)) return false;
if (cur_open > s) --cur_open;
else {
cur_open = s = ++p;
if (*p == '\0') return true;
if (!IS_OPEN(*p)) return false;
}
}
return false;
}
If you are forced to scan backwards through dead zones because the string cannot be overwritten, then the number backward scans is only bounded by the size of the string itself, and the algorithm becomes O(n2).
This can be done by keeping counters for delimiters which are incremented each time an opening delimiter is encountered, and decremented each time a closing delimiter is encountered. To account for correct nesting, a function that iterates backwards through the string from the current position each time a closing delimiter is encountered can be used. This function finds the corresponding opening delimiter by counting opening and closing delimiters encountered during this backwards traversal.
This is O(1) in space, but not O(n) in time complexity:
#include <stdio.h>
#include <string.h>
int is_balanced(const char *str);
int is_corresponding_open(const char *to, const char *from, const char c);
int main(void)
{
char input[4096];
for (;;) {
puts("Enter an expression:");
fgets(input, sizeof input, stdin);
if (input[0] == '\n') {
break;
}
input[strcspn(input, "\r\n")] = '\0';
printf("%s is %s\n",
input,
is_balanced(input) ? "balanced" : "not balanced");
}
return 0;
}
int is_balanced(const char *str_ptr)
{
const char *start = str_ptr;
int count_paren = 0;
int count_brace = 0;
int count_bracket = 0;
int valid_nesting = 1;
while (*str_ptr && valid_nesting) {
switch (*str_ptr) {
case '(':
++count_paren;
break;
case '{':
++count_brace;
break;
case '[':
++count_bracket;
break;
case ')':
if (is_corresponding_open(start, str_ptr, '(')) {
--count_paren;
} else {
valid_nesting = 0;
}
break;
case '}':
if (is_corresponding_open(start, str_ptr, '{')) {
--count_brace;
} else {
valid_nesting = 0;
}
break;
case ']':
if (is_corresponding_open(start, str_ptr, '[')) {
--count_bracket;
} else {
valid_nesting = 0;
}
break;
}
++str_ptr;
}
return !(count_paren || count_brace || count_bracket) && valid_nesting;
}
int is_corresponding_open(const char *to, const char *from, const char c)
{
int validity = 0;
int nesting = 0;
while (to <= from) {
if (nesting == 1 && *from == c) {
validity = 1;
break;
}
if (*from == ')' || *from == '}' || *from == ']') {
++nesting;
} else if (*from == '(' || *from == '{' || *from == '[') {
--nesting;
}
--from;
}
return validity;
}
Sample interaction:
Enter an expression:
(1 (2 (3)))
(1 (2 (3))) is balanced
Enter an expression:
(1 [2 {3 4}] 5)
(1 [2 {3 4}] 5) is balanced
Enter an expression:
(1 {2 [3}])
(1 {2 [3}]) is not balanced
Enter an expression:
1 [2 (3)]
1 [2 (3)] is balanced
Enter an expression:
Assuming by "three diff parenthesis" do you mean three types, so "[", "{", "("...
Without using a stack I'd try this (pseudo code... yet to try to code it up)
OPEN_PARENS = [ "{", "[", "(" ]
Find last occurrence of one of OPEN_PARENS
Find next occurrence of corresponding closing paren.
If find another closer that does not correspond then error.
When closing paren found replace it with a space (and also the opening paren)
Repeat until no opening paren is found
Check there are no closing parens.
Just an idea, yet to test it. Also it assumes the original input string is mutable.
This does not use a stack and takes up no extra memory, but is now an O(n^2)-ish parse rather than O(n) parse.
EDIT: As Matt points out this still uses memory. It is the memory already allocated for a string but if the string were const, this wouldn't work. So... as Matt suggests just storing a pointer to the last removed open parenthesis would also work. I think you would have to add a count for each type of parenthesis seen too.
Err.. maybe something like this. I don't have time now but will re-check this logic in the evening.
numSq = 0;
numCurley = 0;
numCurve = 0;
OPEN_PARENS = [ "{", "[", "(" ]
Find last occurrence of one of OPEN_PARENS before the last seen (if any other wise search from end of string),
store pointer to it and increment a count for that type of parenthesis.
If none found exit success
Find next occurrence of corresponding closing paren.
If find another closer that does not correspond then decrement count
for that closer. If count reaches negative then there is an error in string.
When closing param found start again
It works on the principle that once you have the inner most matching brackets matched, matches futher out can "ignore" them, but need to track counts because there has to be some kind of "memory" in the system. Using one pointer and 3 counters however, would be O(1) memory. Still same O(n^2)-ish parse time.
State machine to the rescue:
(hand-built, so there could be some typos ;-)
This only work for three different pairs of parentheses (well, at least not for nested sets of the same kind)
#include <stdio.h>
#include <string.h>
int check_parens(char *str)
{
int state;
/*
** 1 (
** 2 ([
** 3 ([{
** 4 ({
** 5 ({[
** 6 [
** 7 [(
** 8 [({
** 9 [{
** 10 [{(
** 11 {
** 12 {(
** 13 {([
** 14 {[
** 15 {[(
*/
for (state=0; *str; str++) {
if ( !strchr( "()[]{}", *str )) continue;
switch(state) {
case 0:
if (*str == '(') { state =1; continue; }
if (*str == '[') { state =6; continue; }
if (*str == '{') { state =11; continue; }
return -1;
case 1: /* ( */
if (*str == ')') { state =0; continue; }
if (*str == '[') { state =2; continue; }
if (*str == '{') { state = 4; continue; }
return state;
case 2: /* ([ */
if (*str == ']') { state = 1; continue; }
if (*str == '{') { state = 3; continue; }
return state;
case 3: /* ([{ */
if (*str == '}') { state = 2; continue; }
return state;
case 4: /* ({ */
if (*str == '}') { state = 1; continue; }
if (*str == '[') { state = 5; continue; }
return state;
case 5: /* ({[ */
if (*str == ']') { state = 4; continue; }
return state;
case 6: /* [ */
if (*str == ']') { state = 0; continue; }
if (*str == '(') { state = 7; continue; }
if (*str == '{') { state = 9; continue; }
return state;
case 7: /* [( */
if (*str == ')') { state = 6; continue; }
if (*str == '{') { state = 8; continue; }
return state;
case 8: /* [({ */
if (*str == '}') { state = 7; continue; }
return state;
case 9: /* [{ */
if (*str == '}') { state = 6; continue; }
if (*str == '(') { state = 10; continue; }
return state;
case 10: /* [{( */
if (*str == ')') { state = 9; continue; }
return state;
case 11: /* { */
if (*str == '}') { state = 0; continue; }
if (*str == '(') { state = 12; continue; }
if (*str == '[') { state = 14; continue; }
return state;
case 12: /* {( */
if (*str == ')') { state = 11; continue; }
if (*str == '[') { state = 13; continue; }
return state;
case 13: /* {([ */
if (*str == ']') { state = 12; continue; }
return state;
case 14: /* {[ */
if (*str == ']') { state = 11; continue; }
if (*str == '(') { state = 15; continue; }
return state;
case 15: /* {[( */
if (*str == ')') { state = 14; continue; }
return state;
}
}
return state;
}
int main(int argc, char **argv)
{
int result;
result= check_parens(argv[1]);
printf("%s := %d\n", argv[1], result);
return result;
}
Update: maching parentheses should either be adjecent, or at the outside of the string (ignoring normal characters) So we can reduce the string by just working from both sides.
int check_parens2(char *str, unsigned len)
{
while (len) {
char *cp;
str[len] = 0;
fprintf(stderr, "%s\n", str);
/* if there is any non-paren character at the beginning or end we can skip it */
cp = strchr( "()[]{}", *str ) ;
if (!cp) { len--; str++; continue; }
cp = strchr( "()[]{}", str[len-1] ) ;
if (!cp) { len--; continue; }
/* if the first two characters match : we can skip them */
/* TODO: we should also skip enclosed *normal* characters */
if (str[0] == '(' && str[1] == ')' ) { str +=2; len -= 2; continue; }
if (str[0] == '[' && str[1] == ']' ) { str +=2; len -= 2; continue; }
if (str[0] == '{' && str[1] == '}' ) { str +=2; len -= 2; continue; }
/* the same if the last two characters match */
if (str[len-2] == '(' && str[len-1] == ')' ) { len -= 2; continue; }
if (str[len-2] == '[' && str[len-1] == ']' ) { len -= 2; continue; }
if (str[len-2] == '{' && str[len-1] == '}' ) { len -= 2; continue; }
/* if begin&end match : we can skip them */
if (str[0] == '(' && str[len-1] == ')' ) { str++; len -= 2; continue; }
if (str[0] == '[' && str[len-1] == ']' ) { str++; len -= 2; continue; }
if (str[0] == '{' && str[len-1] == '}' ) { str++; len -= 2; continue; }
break;
}
return len;
}
