给定仅有括号的字符串,如: >( { } ) [ ( ) ]

判断这些括号是不是都闭合了(有左括号就有右括号匹配)。以上括号就是闭合的,但如下就是不闭合:

( { } ) ( ) ]

借助 stack 的属性就很好处理这个问题。stack 是先进后出(first in last out)。所以对于字符串中的每一个括号,如果是左括号就直接入栈,如果是右括号,就和栈顶元素做对比。如果是匹配的右括号,就让栈顶元素出栈。如此循环一直到遍历整个字符串。如果最终栈是空,那么就说明字符串都闭合了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <stdlib.h>
#include <stdio.h>
#include <string.h>

typedef enum { false, true } bool;

typedef struct tagSNode{
  char value;
  struct tagSNode *pNext;
}SNode;

SNode* create(value){
  SNode *node = malloc(sizeof(SNode));
  node->value=value;
  node->pNext=NULL;
  return node;
}

bool match(char top, char key){
  if(top == '('){
    return ((key == ')') ? true : false);
  }else if(top == '{'){
    return ((key == '}') ? true : false);
  }else if(top == '['){
    return ((key == ']') ? true : false);
  }else{
    return false;
  }
}

void verify(char *str){
  int size = (unsigned int)strlen(str);
  printf("%i\n", size);
  SNode *head = create('&');
  SNode *cur = create(str[0]);
  head->pNext = cur;

  for(int i=1;i<size;i++){

    if(str[i] != cur->value){
      if(match(cur->value,str[i])){
        cur = NULL;
        cur = head;
      }else{
        cur->pNext = create(str[i]);
        cur = cur->pNext;
      }
    }else{
      cur->pNext = create(str[i]);
      cur = cur->pNext;
    }
  }
  if(cur->value == '&'){
    puts("match!");
  }else{
    puts("no match!");
  }
};

int main(){
  char str[] = "()(){}((({\{[]";
  verify(str);
}