栈

栈的实现

/*
 * 栈的实现可以用链表或数组的方式(下面代码为数组实现)
 * 栈的应用:平衡符号
 * 算法说明:创建一个栈,顺序读取文本的每个字符,遇到开放符号则进栈;
 * 遇到闭合符号时,弹出栈顶元素并与读取的闭合符号比较,是否为成对的符号
 */
#include <stdio.h>
#include <stdlib.h>
#define Error(Str)    FatalError(Str);
#define FatalError(Str)    fprintf(stderr, "%s\n", Str), exit(1)
#define EmptyTOS    (-1)
#define MinStackSize    (5)
typedef char ElementType;
struct StackRecord;
typedef struct StackRecord *Stack;
struct StackRecord
{
    int Capacity;
    int TopOfStack;
    ElementType *Array;
};
Stack CreateStack(int MaxElements);
void DisposeStack(Stack S);
int IsEmpty(Stack S);
int IsFull(Stack S);
void MakeEmpty(Stack S);
void Push(ElementType X, Stack S);
ElementType Top(Stack S);
void Pop(Stack S);
ElementType TopAndPop(Stack S);
/*
 * 栈的创建
 */
 Stack CreateStack(int MaxElements)
 {
     Stack S;
     
     if(MaxElements < MinStackSize)
         Error("Out of space!!!");
         
     S = malloc(sizeof(struct StackRecord));
     if(S == NULL)
         FatalError("Out of space!!!");
     
     S->Array = malloc(sizeof(ElementType) * MaxElements);
     if(S->Array == NULL)
         FatalError("Out of space!!!");
     S->Capacity = MaxElements;
     MakeEmpty(S);
     
     return S;
 }
 
/*
 * 将栈置空
 */
void MakeEmpty(Stack S)
{
    S->TopOfStack = EmptyTOS;
}
 
/*
 * 栈的释放
 */
void DisposeStack(Stack S)
{
    if(S != NULL)
    {
        free(S->Array);
        free(S);
    }
}
/*
 * 检测一个栈是否为空
 */
int IsEmpty(Stack S)
{
    return S->TopOfStack == EmptyTOS;
}
/*
 * 检测一个栈是否已满
 */
int IsFull(Stack S)
{
    return S->TopOfStack == S->Capacity - 1;
}
/*
 * 进栈
 */
void Push(ElementType X, Stack S)
{
    if(IsFull(S))
    {
        Error("Full stack");
    }
    else
        S->Array[++S->TopOfStack] = X;
}
/*
 * 将栈顶返回
 */
ElementType Top(Stack S)
{
    if(!IsEmpty(S))
        return S->Array[S->TopOfStack];
    Error("Empty stack");
    return 0;
}
/*
 * 从栈弹出元素
 */
void Pop(Stack S)
{
    if(IsEmpty(S))
    {
        Error("Empty stack");
    }
    else
        S->TopOfStack--;
}
/*
 * 给出栈顶元素并从栈弹出
 */
ElementType TopAndPop(Stack S)
{
    if(!IsEmpty(S))
        return S->Array[S->TopOfStack--];
    
    //Error("Empty stack");
    
    return 0;
}
int main()
{
    FILE *stream;
    int ch,is_empty;
    ElementType close_ch;
    stream = fopen("./code.txt","r");
    
    //创建一个能存放1000个元素的栈
    Stack stacker;
    stacker = CreateStack(1000);
    int line = 1,flag = 1;
    while((ch=fgetc(stream))!=EOF)
    {    
        //开放符号进栈
        if(ch == '{' || ch == '(')
            Push(ch, stacker);
        //闭合符号,和栈顶元素进行成对比较
        if(ch == '}' || ch == ')')
        {
               close_ch = TopAndPop(stacker);
            switch(ch)
            {
                case '}':
                    if(close_ch != '{')
                    {
                        flag = 0;
                        printf("第%d行的符号不平衡,皮卡！⊙﹏⊙‖\n", line);
                    }
                    break;
                case ')':
                    if(close_ch != '(')
                    {
                        flag = 0;
                        printf("第%d行的符号不平衡,皮卡！⊙﹏⊙‖\n", line);
                    }
                    break;
                default:
                    break;
            }
        }
        //文本行数统计
        if(ch == '\n')
            line++;
    }
    fclose(stream);
    is_empty = IsEmpty(stacker);
    if(flag)
    {
        if(is_empty)
            printf("文本没有不平衡的符号,皮卡！^_^\n");
        else
            printf("第%d行的符号不平衡,皮卡！⊙﹏⊙‖\n", line);
    }    
}

栈的应用

四则运算

后缀表达式的计算

函数调用：当在主函数中调用新函数时，需要先将主函数中的所有局部变量、执行新函数时的位置保存在栈中，当新函数执行完成后，再从栈中取数据并继续往下执行；