首页 > 代码库 > string stack操作要注重细节问题
string stack操作要注重细节问题
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.代码：
1 // you can write to stdout for debugging purposes, e.g. 2 // printf("this is a debug message\n"); 3 #include <stdlib.h> 4 5 typedef struct node{ 6 char x; 7 struct node* next; 8 }tnode; 9 10 typedef struct stack{ 11 tnode *top; 12 tnode *bottom; 13 }tStack; 14 15 void push(tnode *N,tStack *S) 16 { 17 if(S->top == NULL) 18 { 19 S->top = N; 20 S->bottom = N; 21 } 22 else 23 { 24 N->next = S->top; 25 S->top = N; 26 } 27 } 28 29 tnode *peek(tStack *S) 30 { 31 if(S->top == NULL) 32 { 33 return NULL; 34 } 35 else 36 { 37 return S->top; 38 } 39 } 40 41 tnode *pop(tStack *S) 42 { 43 if(S->top == NULL) 44 { 45 return NULL; 46 } 47 if(S->top == S->bottom) 48 { 49 tnode *temp = S->top; 50 S->top = NULL; 51 S->bottom = NULL; 52 return temp; 53 } 54 else 55 { 56 tnode *temp = S->top; 57 S->top = S->top->next; 58 return temp; 59 } 60 } 61 62 int solution(char *S) { 63 // write your code in C99 64 65 tStack *myStack = malloc(sizeof(tStack)); 66 myStack->top = NULL; 67 myStack->bottom = NULL; 68 69 // int len = strlen(S); 70 char *temp = S; 71 tnode *myNode = NULL; 72 // int i; 73 while(*temp) 74 { 75 // printf("%c\n",*temp); 76 if(*temp == ‘(‘ || *temp == ‘[‘ ||*temp == ‘{‘) 77 { 78 myNode = malloc(sizeof(tnode)); 79 myNode->x = *temp; 80 push(myNode,myStack); 81 } 82 else 83 { 84 myNode = peek(myStack); 85 if(myNode == NULL) 86 { 87 return 0; 88 } 89 if(*temp == ‘)‘) 90 { 91 if(myNode->x == ‘(‘) 92 { 93 myNode = pop(myStack); 94 } 95 else 96 { 97 return 0; 98 } 99 }100 if(*temp == ‘]‘)101 {102 if(myNode->x == ‘[‘)103 {104 myNode = pop(myStack);105 }106 else107 {108 return 0;109 }110 }111 if(*temp == ‘}‘)112 {113 if(myNode->x == ‘{‘)114 {115 myNode = pop(myStack);116 }117 else118 {119 return 0;120 }121 }122 }123 124 temp++;125 }126 myNode = peek(myStack);127 if(myNode == NULL)128 {129 return 1;130 }131 else132 {133 return 0;134 }135 136 }
string stack操作要注重细节问题