数据结构之栈及栈的应用（括号匹配问题）

栈简介：

栈是一种特殊的线性表，其只允许在固定的一端进行插入和删除元素操作。进行数据插入和删除操作的一段称为栈顶，另一端称为栈底。不含任何元素的栈称为空栈，其特点为 先进后出。
栈功能：可以将数据从一种序列变为另一种序列
注：图片来自网络

#pragma once

#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

#define STACK_INIT_SIZE 100;
#define STACKINCREMENT 10;
//1. 实现栈的如下接口-- - 实现成动态栈
typedef int DataType;

typedef struct Stack
{
    DataType *_array;
        int *_top; // 表示有效元素个数 表示栈顶位置 
    int _capacity; // 底层空间的总大小 
}Stack;
//栈的初始化
void StackInit(Stack* s);
// 入栈 
void StackPush(Stack* s, DataType data);
// 出栈 
void StackPop(Stack* s);
// 获取栈顶元素 
DataType StackTop(Stack* s);
// 有效元素的个数 
int StackSize(Stack* s);
// 检测栈是否为空 
int StackEmpty(Stack* s);
// 栈的应用 
//2. 用栈解决括号匹配问题，测试用例见课件
void Parenthesis_match(Stack *s, char *Str);
//3. 用栈求解后缀表达式值


//栈的初始化
void StackInit(Stack* s)
{
    s->_capacity = (Stack*)malloc(sizeof(DataType));
    if (!s->_array)
        exit(EXIT_FAILURE);   //存储分配失败
    s->_top = s->_array;
    s->_capacity = STACK_INIT_SIZE;
    return;

}
// 入栈 
void StackPush(Stack* s, DataType data)
{
    if (s->_top >= s->_capacity) //栈满，追加存储空间
    {
        s->_array = (DataType*)realloc(s->_array, ((s->_capacity) + 10)*sizeof(DataType));
        if (!s->_top)
            exit(EXIT_FAILURE);//存储分配失败
        s->_top = (s->_array)+(s->_capacity);
        s->_capacity += STACKINCREMENT;
    }
    *s->_top++ = data;
    return;
}

// 出栈 
void StackPop(Stack* s)
{
    if ((s->_top) == (s->_array))
        return;
    s->_top = NULL;
    s->_top--;

}
// 获取栈顶元素 
DataType StackTop(Stack* s)
{
    if (NULL == s->_top)
        exit(EXIT_FAILURE);
    s->_array = s->_top--;
    printf("Stack Top is =%d \n", s->_array);
    return 1;
}
// 有效元素的个数 
int StackSize(Stack* s)
{
    DataType count = 0;
    if (NULL == s->_top)
        return 0;
    while (s->_top)
    {
        s->_array = s->_top;
        count++;
    }
    return count;
}
// 检测栈是否为空 
int StackEmpty(Stack* s)
{
    assert(s);
    if (NULL == s->_top)
    {
        printf("Stack is Empty\n");
        return 0;
    }
    else
        printf("Stack isn’t Empty\n");
    return 1;
}
// 栈的应用 
//2. 用栈解决括号匹配问题，测试用例见课件
void Parenthesis_match(Stack *s, char *Str)
{
    char enter, str[100] = { 0 };
    DataType i = 0;
    DataType flag = 0;
    printf("请输入字符串:\n");
    scanf("%s", str);
    scanf("%c", &enter);
    while (str[i] != '\0')
    {
        switch (str[i])
        {
        case '(':
            StackPush(s, str[i]);
            break;
        case '[':
            StackPush(s, str[i]);
            break;
        case '{':
            StackPush(s, str[i]);
            break;
        case ')':
        {
            StackPop(str[i]);
            if (str[i] != s->_top)
                flag = 1;
        }
        break;
        case ']':
        {
            StackPop(str[i]);
            if (str[i] != s->_top)
                flag = 1;
        }
        break;
        case '}':
        {
            StackPop(str[i]);
            if (str[i] != s->_top)
                flag = 1;
        }
        break;
        }
        if (flag)
            return;
        i++;
    }
    if (!(flag && StackEmpty(s)))
        printf("括号匹配成功!\n");
    else
        printf("括号匹配失败!\n");
}