基于C语言实现的括号匹配问题

sweettalk

发布日期: 2018-12-07 20:58:45 浏览量: 882
评分:
star star star star star star star star star_border star_border
*转载请注明来自write-bug.com

1 解题思路

构造包含顶指针,底指针和增量的结构体。以此建立一个空栈。然后依次读入输入的字符,存放至栈中。最后从栈中依次读出字符。分别设置三种括号的标志。当右括号读出时标志加一,当左括号读出时标志减一。如果表达式括号匹配,则三种标志位都等于0,如果括号不匹配则标志位不等于0,最后输出结果。

2 各函数功能

  1. // 构造一个空栈
  2. int InitStack(SqStack *S);
  3. // 让e入栈
  4. int Push(SqStack *S, char e);
  5. // 让e出栈
  6. int Pop(SqStack *S, char *e);
  7. // 判断栈是否为空,空返回0,非空返回1
  8. int isEmpty(SqStack *S);
  9. // 判断括号是否匹配,通过计数器计算前后括号数量。如果三个计数器都为0,括号匹配
  10. int match(SqStack *S, int counter);
  11. // 流程控制,并且建立栈S
  12. int main();

3 函数调用图

4 测试

5 源代码

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <malloc.h>
  4. #define STACK_INIT_SIZE 100 /*存储空间初始分配量*/
  5. #define STACKINCREMENT 20 /*存储空间分配增量*/
  6. typedef struct {
  7. char *top;
  8. char *base;
  9. int stacksize;
  10. }SqStack;
  11. int InitStack (SqStack *S) { /*构造一个空栈*/
  12. S -> base = (char*)malloc(STACK_INIT_SIZE*sizeof(char));
  13. S -> top = S -> base;
  14. S -> stacksize = STACK_INIT_SIZE;
  15. return 1;
  16. }
  17. int Push (SqStack *S, char e) { /*插入元素e为新的栈顶元素*/
  18. if (S -> top - S -> base >= S -> stacksize) {
  19. S -> base = (char*)realloc(S -> base, (S -> stacksize + STACKINCREMENT)*sizeof(char));
  20. if (!S -> base) { /*栈溢出*/
  21. return -1;
  22. }
  23. S -> top = S -> base + S -> stacksize;
  24. S -> stacksize += STACKINCREMENT;
  25. }
  26. *(S -> top) = e; /*先赋值在将指针加1*/
  27. S -> top ++;
  28. return 1;
  29. }
  30. int Pop (SqStack *S, char *e) { /*退栈*/
  31. if (S -> top == S -> base) { /*栈空*/
  32. return 0;
  33. } else {
  34. S -> top --; /*先将指针减1在出栈*/
  35. *e = *(S -> top);
  36. }
  37. return 1;
  38. }
  39. int isEmpty (SqStack *S) { /*判断栈是否为空*/
  40. if (S -> top == S -> base) {
  41. return 0;
  42. } else {
  43. return 1;
  44. }
  45. }
  46. int match (SqStack *S, int counter) { /*判断括号是否匹配*/
  47. int i, flag1 = 0, flag2 = 0, flag3 = 0; /*标志位flag1,2,3, 记录三种括号()[]{}的次数*/
  48. char e;
  49. if (isEmpty(S) == 0) { /*判断栈是否为空*/
  50. printf("输入的字符为空!");
  51. } else { /*不为空就弹栈*/
  52. for (i = 0; i < counter; i++) {
  53. Pop(S, &e);
  54. switch (e) { /*判断括号是否匹配*/
  55. case '(': flag1--;break;
  56. case ')': flag1++;break;
  57. case '[': flag2--;break;
  58. case ']': flag2++;break;
  59. case '{': flag3--;break;
  60. case '}': flag3++;break;
  61. default: break;
  62. }
  63. }
  64. if ((flag1 == 0 && flag2 == 0) && (flag3 == 0 && (counter != 0))) {
  65. printf("括号匹配!");
  66. } else {
  67. printf("括号不匹配!");
  68. }
  69. }
  70. return 1;
  71. }
  72. int main() {
  73. int counter; /*定义计数器,记录入栈次数*/
  74. char c = 0;
  75. SqStack *S;
  76. InitStack(&S);
  77. printf("请依次输入字符(回车键表示结束):\n");
  78. while (c != '\n') { /*当输入的字符是回车时,停止输入*/
  79. c = getchar();
  80. if (c != '\n') { /*当输入的字符不是回车时,将其放入栈*/
  81. Push(&S, c);
  82. counter++;
  83. }
  84. }
  85. match(&S, counter);
  86. return 1;
  87. }
上传的附件 cloud_download 括号匹配问题.7z ( 152.84kb, 2次下载 )
error_outline 下载需要4点积分

发送私信

我们走得很慢,但终有一天是会走到的

15
文章数
24
评论数
最近文章
eject