A string S consisting of N characters is considered to be properly nested if any of the following conditions is true:
- S is empty;
- S has the form "(U)" or "[U]" or "{U}" where U is a properly nested string;
- S has the form "VW" where V and W are properly nested strings.
For example, the string "{[()()]}" is properly nested but "([)()]" is not.
Write a function:
int solution(char *S);
that, given a string S consisting of N characters, returns 1 if S is properly nested and 0 otherwise.
For example, given S = "{[()()]}", the function should return 1 and given S = "([)()]", the function should return 0, as explained above.
Assume that:
- N is an integer within the range [0..200,000];
- string S consists only of the following characters: "(", "{", "[", "]", "}" and/or ")".
Complexity:
- expected worst-case time complexity is O(N);
- expected worst-case space complexity is O(N) (not counting the storage required for input arguments).
Copyright 2009–2015 by Codility Limited. All Rights Reserved. Unauthorized copying, publication or disclosure prohibited.
1. 需要注意的细节：
a.每次peek后，需要检查时候为NULL,如果缺少这一步检查而直接进行 myNode->x 操作，会产生段错误。
b.注意str的对称性问题，并不是每一次循环正常结束都是正确的，有可能存在右括号少的情况，需要判断如果stack不为空，则返回false；
c.要注意temp必须每一次都++,否则循环不能正常进行。
2.代码：
// you can write to stdout for debugging purposes, e.g.
// printf("this is a debug message\n");
#include <stdlib.h> typedef struct node{
char x;
struct node* next;
}tnode; typedef struct stack{
tnode *top;
tnode *bottom;
}tStack; void push(tnode *N,tStack *S)
{
if(S->top == NULL)
{
S->top = N;
S->bottom = N;
}
else
{
N->next = S->top;
S->top = N;
}
} tnode *peek(tStack *S)
{
if(S->top == NULL)
{
return NULL;
}
else
{
return S->top;
}
} tnode *pop(tStack *S)
{
if(S->top == NULL)
{
return NULL;
}
if(S->top == S->bottom)
{
tnode *temp = S->top;
S->top = NULL;
S->bottom = NULL;
return temp;
}
else
{
tnode *temp = S->top;
S->top = S->top->next;
return temp;
}
} int solution(char *S) {
// write your code in C99 tStack *myStack = malloc(sizeof(tStack));
myStack->top = NULL;
myStack->bottom = NULL; // int len = strlen(S);
char *temp = S;
tnode *myNode = NULL;
// int i;
while(*temp)
{
// printf("%c\n",*temp);
if(*temp == '(' || *temp == '[' ||*temp == '{')
{
myNode = malloc(sizeof(tnode));
myNode->x = *temp;
push(myNode,myStack);
}
else
{
myNode = peek(myStack);
if(myNode == NULL)
{
return ;
}
if(*temp == ')')
{
if(myNode->x == '(')
{
myNode = pop(myStack);
}
else
{
return ;
}
}
if(*temp == ']')
{
if(myNode->x == '[')
{
myNode = pop(myStack);
}
else
{
return ;
}
}
if(*temp == '}')
{
if(myNode->x == '{')
{
myNode = pop(myStack);
}
else
{
return ;
}
}
} temp++;
}
myNode = peek(myStack);
if(myNode == NULL)
{
return ;
}
else
{
return ;
} }