[C++知识库]C语言：栈的应用

栈 (Stack)

在栈这种数据结构中，数据的存取过程是以后进先出的方式进行的。最后保存的数据会首先被取出。

对栈的操作包括以下几种：
· 栈的初始化
· 数据的进栈（压栈）
· 数据的出栈（弹栈）
· 检查栈是否为空

实例

#include <stdio.h>
#include <string.h>
#define MAX 100 //栈的最多保存元素数量

//栈的初始化 
char stack[MAX] = { 0 };//此示例中，栈的元素为char类型，可更改
int top = 0;//top:栈顶位置标记

//数据的进栈（压栈）
void push(char v)
{
    stack[top++] = v;
}

//数据的出栈（弹栈）
char pop()
{
    return stack[--top];
}

//检查栈是否为空
int stack_empty()
{
    return (top == 0);
}


//实例：括号匹配
//1.逐个读入输入的字符，直至输入结束时，转向6；
//2.遇到左括号，将其入栈；
//3.遇到右括号，检查当前栈顶元素（第4、5步）；
//4.若匹配，转向1；
//5.若不匹配||栈为空，输出-1，结束过程；
//6.结束过程，检查栈是否为空，若为空，输出1，否则输出-1.


int match(char* s)
{
    char* p;//建立扫描指针
    char d;//栈顶元素

    for (p = s; *p != '\0'; p++)
    {
        if (*p == '(' || *p == '[')
            push(*p);//【执行第2步】       

        else if (*p == ')' || *p == ']')//【执行第3步】
        {
            if (stack_empty())
                return -1;//【第5步，栈为空的情况】

            d = pop();//取出当前栈顶元素
           
            if ((*p == ')' && d == '(') || (*p == ']' && d == '['))//【第4步】
                continue;

            return -1;//【第5步，括号不匹配的情况】      
        }
    }
    return stack_empty() ? 1 : -1;//【第6步】
}




int main() 
{ 
    fgets(stack, MAX, stdin);
    int answer = match(stack);
    printf("%d\n", answer);
   
    return 0;
}