栈~括号的匹配

博主： Xherlock
发布时间：2021 年 10 月 05 日
998 次浏览
暂无评论
3432字数
分类：数据结构与算法

# **栈**

## **括号的匹配**

**只用链栈实现**

**这部分上数据结构与算法课时也做了实验，当时写得一塌糊涂，过后仔细研究了发现当时没写好两大原因**

* **C语言结构定义声明那部分没掌握扎实，以至于第一眼看上去奇怪的很：为啥来了个链表，又来了个栈结构定义，过后发现其实是栈结构里包含了链表结构，跟课本上的不一样，掌握理论还是无用，还得付诸实践学习**
  **书上的：**
  ![EF5FDF2290E0F0D2B3D0929B55D1D881.png](http://120.78.215.15/usr/uploads/2021/10/3999217146.png)
  **实际上：**
  ![image-20211005165618548.png](http://120.78.215.15/usr/uploads/2021/10/2824884954.png)
* **老师给的代码是真有点乱了，结构名变量名一样，导致后面写出的函数混乱不堪，因为菜所以调试了好长时间才发现报错原因**
  ![image-20211005165754946.png](http://120.78.215.15/usr/uploads/2021/10/2221551627.png)

**可以根据颜色看出来在分配空间时要分配的本应是linked_list_stack的结构空间，结果分配的是形参变量的空间**
  **后面形参变量改成linked_list_stack1才通过**
  **所以下回吸取教训，直接大改特改老师的代码**

**实验后自己又按着自己的理解想法敲出了可以实现匹配括号的功能**

**能够同时匹配()、{}**

### **头部**

**命名全部最简化了**

```
#include<stdio.h>
#include<malloc.h>
#include<string.h>

typedef struct node
{
    char data1;  // 括号类型
    int data2;  // 括号位置
    struct node *next;
} node;

typedef struct stack
{
    struct node *top;   // 其实base指针没必要了，判断为空一句话就可以了
} stack;
```

### **函数声明**

**只留下了初始化（创建栈）、入栈、出栈的功能**

```
stack *InitStack(void);
void Push(stack *S, char e, int n);
void Pop(stack *S, char *e, int *n);
```

### **主函数**

**采用while+switch+while来匹配正确括号（主函数有点臃肿）**

```
int main(void)
{
    stack *S = InitStack();
    printf("请输入表达式：");
    char ch[100];
    scanf("%s", ch);
    int i = 0;
    char x;
    int n;
    while(i < strlen(ch))
    {
        switch(ch[i])
        {
            case '{':
            case '(':
                Push(S, ch[i], i);
                break;
            case ')':
                if(S->top != 0)
                {
                    Pop(S, &x, &n);
                    // 没有按照课本里的
                    // 如果出现‘{(}’这样的情况不加下面的循环会导致‘(’和最后的‘}’匹配
                    while(x != '(') // 这里一定要注意要单引号，因为x是字符，卡这里不少时间......开始还想着用strcmp来着，但实际上不行
                    {
                        Pop(S, &x, &n);
                    } 
                    printf("%c %d, %d )\n", x, n + 1, i + 1);    // 数值加一，按照正常计数来排列
                }
                break;
            case '}':
                if(S->top != 0)
                {
                    Pop(S, &x, &n);
                    while(x != '{')
                    {
                        Pop(S, &x, &n);
                    } 
                    printf("%c %d, %d }\n", x, n + 1, i + 1); 
                }
                break;
        }
        i++;
    }
}
```

### **初始化**

```
stack *InitStack(void)
{
    stack *S = (stack *)malloc(sizeof(stack));
    S->top = 0;
    return S;
}
```

### **入栈**

```
void Push(stack *S, char e, int n)
{
    node *p = (node *)malloc(sizeof(node));
    p->data1 = e;
    p->data2 = n;
    p->next = S->top;
    S->top = p;
}
```

### **出栈**

```
void Pop(stack *S, char *e, int *n)
{
    if(S->top != 0)
    {
        node *p = S->top;
        *e = p->data1;
        *n = p->data2;
        p = p->next;
        free(S->top);
        S->top = p;
    }
}
```

**实现效果：**

**input：......((((((((((....))))))))))...((..(((((((...((((....)))).....)))))))..))(((((((..........((((((.....((((((....)))))).......))))))..))))))).**

![image-20211005171814598.png](http://120.78.215.15/usr/uploads/2021/10/2098822785.png)

**input: {{((())}}{}()..()**

![image-20211005171906203.png](http://120.78.215.15/usr/uploads/2021/10/1854075172.png)

最后修改：2021 年 10 月 25 日