栈

括号的匹配

只用链栈实现

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

• C语言结构定义声明那部分没掌握扎实，以至于第一眼看上去奇怪的很：为啥来了个链表，又来了个栈结构定义，过后发现其实是栈结构里包含了链表结构，跟课本上的不一样，掌握理论还是无用，还得付诸实践学习
  书上的：

实际上：

• 老师给的代码是真有点乱了，结构名变量名一样，导致后面写出的函数混乱不堪，因为菜所以调试了好长时间才发现报错原因
  

可以根据颜色看出来在分配空间时要分配的本应是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：......((((((((((....))))))))))...((..(((((((...((((....)))).....)))))))..))(((((((..........((((((.....((((((....)))))).......))))))..))))))).

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