【数据结构】 利用栈求解 括号匹配问题

前端之家收集整理的这篇文章主要介绍了【数据结构】 利用栈求解 括号匹配问题前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

括号是否匹配问题求解

以下为代码演示:

  1. /***
  2. // 括号匹配问题
  3. InitStack ( &S) : 栈的初始化
  4. Push ( &S,e) :进栈
  5. Pop (&S ) : 出栈
  6. GetTop (S ): 取栈顶元素
  7. IsEmpty (S): 判栈空否
  8. ***/
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11.  
  12. #define STACK_MAX 1000
  13. typedef char ElemType;
  14.  
  15. typedef struct Stack
  16. {
  17. int top;
  18. ElemType elem[STACK_MAX];
  19. }Stack,*Pstack;
  20.  
  21. void InitStack (Pstack S) ; // 栈的初始化
  22. void Push (Pstack S,ElemType elem) ; // 进栈
  23. void Pop (Pstack S ) ; // 出栈
  24. ElemType GetTop (Pstack S ); // 取栈顶元素
  25. bool IsEmpty (Pstack S); // 判栈空否
  26. bool match(char a,char b);
  27.  
  28. void main()
  29. {
  30. int i = 0;
  31. bool bMatch = true;
  32. char s[100] = "";
  33. scanf("%s",s);
  34.  
  35. Stack data;
  36. Pstack S = &data;
  37.  
  38. InitStack(S);
  39.  
  40. while (s[i] != '\0')
  41. {
  42. char elem = s[i];
  43.  
  44. if (elem == '{' || elem == '[' || elem == '(')
  45. Push(S,elem);
  46. else
  47. {
  48. if (IsEmpty(S))
  49. {
  50. bMatch = false;
  51. break;
  52. }
  53.  
  54. if (match(elem,GetTop(S)))
  55. {
  56. Pop(S);
  57. }
  58. else
  59. {
  60. bMatch = false;
  61. break;
  62. }
  63. }
  64. i++;
  65. }
  66.  
  67. if (bMatch && IsEmpty(S))
  68. {
  69. printf("括号匹配\n");
  70. }
  71. else
  72. {
  73. printf("括号不匹配\n");
  74. }
  75. }
  76.  
  77.  
  78. bool match(char a,char b)
  79. {
  80. switch(a)
  81. {
  82. case '}':
  83. if (b == '{')
  84. return true;
  85. case ']':
  86. if (b == '[')
  87. return true;
  88. case ')':
  89. if (b == '(')
  90. return true;
  91. break;
  92. default :
  93. exit(-1);
  94. }
  95. }
  96. void InitStack (Pstack S) // 栈的初始化
  97. {
  98. S->top = 0;
  99.  
  100. for (int i = 0; i < STACK_MAX; i++)
  101. S->elem[i] = 0;
  102. }
  103.  
  104. void Push (Pstack S,ElemType elem) // 进栈
  105. {
  106. if (S->top != STACK_MAX) // 判断是否栈满
  107. S->elem[(S->top)++] = elem;
  108. }
  109.  
  110. void Pop (Pstack S ) // 栈顶元素出栈
  111. {
  112. S->elem[-- (S->top)] = 0;
  113. }
  114.  
  115. ElemType GetTop (Pstack S ) // 取栈顶元素
  116. {
  117. if (!IsEmpty(S))
  118. return S->elem[S->top-1];
  119. else
  120. printf("栈空~~\n");
  121. }
  122.  
  123. bool IsEmpty (Pstack S) // 判栈空否
  124. {
  125. return (S->top == 0);
  126. }

猜你在找的数据结构相关文章