【栈和队列应用】1、括号匹配

// createStack.cpp
#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#define TYPE int
//#define TYPE biTree*
//#define TYPE char
//#define TYPE Recursion
struct biTree {
    char data;
    struct biTree *lchild;
    struct biTree *rchild;
};
struct Recursion {
    int no;
    int val;
};
struct Stack
{
    TYPE* arr;    //内存首地址
    int  len;    //栈的容量
    int top;     //栈的下标
};
/* --------------以下为实现函数--------------------*/
//创建一个栈
Stack *createStack(int size) {
    struct Stack *stack = (struct Stack*)malloc(sizeof(struct Stack));//给栈分配空间
    stack->arr = (TYPE *)malloc(sizeof(TYPE)*size);//给内存首地址分配空间，大小用户指定
    stack->len = size;//栈容量
    stack->top = -1;//栈顶下标，当前无元素，故为-1
    return stack;
}
//判断栈满
bool full(Stack *stack) {
    return stack->top + 1 >= stack->len;
}
//判断栈空
bool empty(Stack *stack) {
    return stack->top == -1;
}
//入栈
bool push(Stack *stack, TYPE p) {
    if (full(stack)) return false;
    *(stack->arr + ++stack->top) = p;
    return true;
}
//出栈
bool pop(Stack *stack) {
    if (empty(stack)) return false;
    stack->top--;
    return true;
}
//查看栈顶元素
TYPE top(Stack *stack) {
    if (empty(stack)) return NULL;
    return *(stack->arr + stack->top);
}
//销毁
void destory(Stack *stack) {
    free(stack->arr);
    free(stack);
}
//判断是否含有某个元素
bool contain(Stack *stack, TYPE r) {
    if (empty(stack)) return false;
    for (int i = stack->top; i >= 0; i--) {
        if (r == *(stack->arr + i) ){//疯了，我居然把==写成了=
            return true;
        }
    }
    return false;
}

/*
    假设一个算法表达式包含圆括号、方括号、和花括号3种类型的括号，编写一个算法来判断表达式里的括号是否配对，以字符‘\0’作为
    算术表达式的结束符。
    分析：
        我们利用队列来存储算术表达式，再利用一个栈来进行判定，具体流程为：依次从队列中取出表达式，如果是左括号则入栈，
        如果是右括号则取出栈顶元素，比对是否配对，如果不匹配，终止，匹配则继续。
*/
struct LinkQueue {
    struct Link *front, *rear;
};
struct Stack
{
    char* arr;    //内存首地址
    int  len;    //栈的容量
    int top;     //栈的下标
};
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
bool matchBracket(LinkQueue *lq, Stack *s) {
    char letterQ, letterS;
    bool isEmpty(LinkQueue *);
    bool deQueue(LinkQueue *, char *);
    bool push(Stack *, char);
    char top(Stack *);
    bool pop(Stack *);
    bool empty(Stack *);
    while (!isEmpty(lq)) {//如果队列不空
        deQueue(lq, &letterQ);//取出队首元素
        if (letterQ == '(' || letterQ == '{' || letterQ == '[') {//如果是左括号，入栈
            push(s, letterQ);
        }
        else {//如果是右括号，取出栈顶元素对比
            if (empty(s)) {
                return false;
            }
            letterS = top(s);
            pop(s);
            switch (letterQ) {
            case ')': if (letterS != '(')return false; break;
            case ']': if (letterS != '[' ) return false; break;
            case '}': if (letterS != '{' ) return false; break;
            default:break;
            }
        }
    }
    if (empty(s)) {
        return true;
    }
    else {
        return false;
    }
}
int main() {
    int n;//栈的大小
    char letter;
    struct LinkQueue *lq;
    struct Stack *s;
    LinkQueue *create();
    bool enQueue(LinkQueue *, char);
    void printQ(LinkQueue *);
    Stack *createStack(int);
    lq = create();
    printf("请输入栈的大小：n=");
    scanf("%d", &n);
    for (int i = 0; i < n; i++) {
        scanf("\n%c", &letter);
        enQueue(lq, letter);
    }
    printQ(lq);
    printf("\n");
    s = createStack(n);
    if (matchBracket(lq, s)) {
        printf("该算术表达式配对");
    }
    else {
        printf("该算术表达式不配对");
    }
    return 0;
}