C/C++数据结构-完整代码（二）栈（栈的顺序存储，栈的链式存储，就近匹配,中缀表达式和后缀表达式）

以你之姓@ 2022-09-09 06:03 106阅读 0赞

<table> 
 <thead> 
  <tr> 
   <th></th> 
   <th></th> 
  </tr> 
 </thead> 
 <tbody> 
  <tr> 
   <td><a href="https://code100.blog.csdn.net/article/details/119809355" rel="nofollow">C/C++数据结构-完整代码（一）数据结构的理论，线性表（动态数组，链表）（完整的算法代码-增删改查-代码解析+运行结果解析）</a></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td><a href="https://code100.blog.csdn.net/article/details/119984925" rel="nofollow">C/C++数据结构-完整代码（二）栈（栈的顺序存储，栈的链式存储，就近匹配,中缀表达式和后缀表达式）</a></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td><a href="https://code100.blog.csdn.net/article/details/120165289" rel="nofollow">C/C++数据结构-完整代码（三）队列【Queue】（顺序存储，链式存储）增删改查</a></td> 
   <td></td> 
  </tr> 
  <tr> 
   <td><a href="https://blog.csdn.net/qq_44757034/article/details/120254584" rel="nofollow">C/C++数据结构-完整代码（四）队列【Queue】（树和二叉树）（二叉树代码实现）</a></td> 
   <td></td> 
  </tr> 
 </tbody> 
</table>

## 一、受限线性表：栈（Stack） ##

### 1、栈的顺序存储 ###

#### （1）栈的基本概念 ####

*  概念:  
    首先它是一个线性表，也就是说，栈元素具有线性关系，即前驱后继关系。  
    只不过它是一种特殊的线性表而已。  
    定义中说是在线性表的表尾进行插入和删除操作，这里表尾是指栈顶，而不是栈底。
 *  特性（先进后出的数据结构）  
    它的特殊之处在于限制了这个线性表的插入和删除的位置，它始终只在栈顶进行。这也  
    就使得∶栈底是固定的，最先进栈的只能在栈底加  
    栈不可以遍历、只有栈顶元素可以被外界访问到（遍历:不重复不遗漏访问容器中的所有数据  
    遍历算法属于非质变算法）
 *  操作  
    栈的插入操作(push)，叫做进栈，也成压栈。（在进栈的时候可以统计个数）  
    关似子弹入弹夹(如下图所示)栈的删除操作，叫做出栈，  
    也有的叫做弹栈(pop)，退栈。（在出栈的时候不可以统计个数(size)）  
    如同弹夹中的子弹出夹(如下图所示)  
    ![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16]

#### （2）栈的设计（栈是属于一种先进后出的数据结构） ####

*  栈顶在数组的首地址还是尾地址?

钱顶设计在尾地址（数组的尾部进行频繁的插入删除效率比头部更高）

struct SStack{
        
    	
    	void * data[1024];
    	int m_size;//栈的大小（栈当中元素个数）
    	
    }

#### （3）栈的顺序存储 ####

//栈的结构体

struct SStack{
        
        void * data[MAX];//栈的数组
        //栈的元素个数
        int m_Size;
    };

typedef void * seqStack;

//初始化栈

seqStack init_SeqStack(){
        
    
        struct SStack *  stack = malloc (sizeof (struct SStack));
    
        if(stack == NULL){
        
            return NULL;
        }
        //清空数组当中的元素
        //将栈当中的数据清空，清空为0，清空的大小为 栈当中每个元素sizeof(void *)乘以每个元素的大小
        memset (stack->data,0,sizeof(void *) *MAX );
        stack->m_Size = 0;
    
        return stack;
    
    }

//入栈

void push_SeqStack(seqStack stack,void * data){
        
    
        if(stack == NULL){
        
            return;
        }
        if(data == NULL){
        
            return;
        }
        //判断栈是否已经满了,如果满了不可以再入栈了
        struct SStack * myStack = stack;
        if(myStack->m_Size == MAX){
        
            return;
        }
        myStack->data[myStack->m_Size] = data;//入栈尾插
        myStack->m_Size++;//更新栈的大小
    
    }

//出栈

void pop_SeqStack(seqStack stack){
        
    
        if(stack == NULL){
        
            return;
        }
        //如果是空栈不执行空栈
        struct SStack * myStack = stack;
        if(myStack->m_Size <= 0){
        
            return;
        }
        //执行出栈
        myStack->data[myStack->m_Size-1] = NULL;
        //更新栈的大小
        myStack->m_Size -- ;
    
    }

//获取栈顶元素

void * top_SeqStack(seqStack stack){
        
    
        if(stack == NULL){
        
            return NULL;
        }
        struct  SStack * myStack = stack;
    
        //如果是空栈
        if(myStack->m_Size == 0){
        
            return NULL;
        }
        return myStack->data[myStack->m_Size-1];
    
    }

//栈的大小

int size_SeqStack(seqStack stack){
        
    
        if(stack == NULL){
        
            return -1;
        }
        struct SStack * myStack = stack;
        return myStack->m_Size;
    }

//判断栈是否为空
    int isEmpty_SeqStack(seqStack stack){
        
    
        if(stack == NULL){
        
            return -1;//真
        }
        struct SStack * myStack = stack;
        if(myStack->m_Size <= 0){
        
            return -1;//真
        }
        return 0;//返回假代表不是空栈
    }

//销毁栈
    void destory_SeqStack(seqStack stack){
        
        if(stack == NULL)
        {
        
            return;
        }
        free (stack);
        stack = NULL;
    
    }

测试代码全部代码

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #define LINE "---------------------------------------\n"
    #define MAX 1024
    
    //栈的结构体
    struct SStack{
        
        void * data[MAX];//栈的数组
        //栈的元素个数
        int m_Size;
    };
    typedef void * seqStack;
    
    //初始化栈
    seqStack init_SeqStack(){
        
    
        struct SStack *  stack = malloc (sizeof (struct SStack));
    
        if(stack == NULL){
        
            return NULL;
        }
        //清空数组当中的元素
        //将栈当中的数据清空，清空为0，清空的大小为 栈当中每个元素sizeof(void *)乘以每个元素的大小
        memset (stack->data,0,sizeof(void *) *MAX );
        stack->m_Size = 0;
    
        return stack;
    
    }
    //入栈
    void push_SeqStack(seqStack stack,void * data){
        
    
        if(stack == NULL){
        
            return;
        }
        if(data == NULL){
        
            return;
        }
        //判断栈是否已经满了,如果满了不可以再入栈了
        struct SStack * myStack = stack;
        if(myStack->m_Size == MAX){
        
            return;
        }
        myStack->data[myStack->m_Size] = data;//入栈尾插
        myStack->m_Size++;//更新栈的大小
    
    }
    //出栈
    void pop_SeqStack(seqStack stack){
        
    
        if(stack == NULL){
        
            return;
        }
        //如果是空栈不执行空栈
        struct SStack * myStack = stack;
        if(myStack->m_Size <= 0){
        
            return;
        }
        //执行出栈
        myStack->data[myStack->m_Size-1] = NULL;
        //更新栈的大小
        myStack->m_Size -- ;
    
    }
    //获取栈顶元素
    void * top_SeqStack(seqStack stack){
        
    
        if(stack == NULL){
        
            return NULL;
        }
        struct  SStack * myStack = stack;
    
        //如果是空栈
        if(myStack->m_Size == 0){
        
            return NULL;
        }
        return myStack->data[myStack->m_Size-1];
    
    }
    //栈的大小
    int size_SeqStack(seqStack stack){
        
    
        if(stack == NULL){
        
            return -1;
        }
        struct SStack * myStack = stack;
        return myStack->m_Size;
    }
    //判断栈是否为空
    int isEmpty_SeqStack(seqStack stack){
        
    
        if(stack == NULL){
        
            return -1;//真
        }
        struct SStack * myStack = stack;
        if(myStack->m_Size <= 0){
        
            return -1;//真
        }
        return 0;//返回假代表不是空栈
    }
    
    
    //销毁栈
    void destory_SeqStack(seqStack stack){
        
        if(stack == NULL)
        {
        
            return;
        }
        free (stack);
        stack = NULL;
    
    }
    
    //测试
    struct Person{
        
        char name[64];
        int age;
    };
    void test01(){
        
    
        //准备数据
        struct  Person p1 = {
        "aaa",10};
        struct  Person p2 = {
        "bbb",20};
        struct  Person p3 = {
        "ccc",30};
        struct  Person p4 = {
        "ddd",40};
        struct  Person p5 = {
        "fff",50};
    
        //初始化栈
        seqStack stack  = init_SeqStack();
        push_SeqStack (stack,&p1);
        push_SeqStack (stack,&p2);
        push_SeqStack (stack,&p3);
        push_SeqStack (stack,&p4);
        push_SeqStack (stack,&p5);
        printf("stack size = %d\n", size_SeqStack (stack));
        void * ss =  top_SeqStack(stack);
        printf ("%s\n",LINE);
        printf ("stack top = %s\n",ss);
        printf ("%s\n",LINE);
        while (isEmpty_SeqStack (stack) == 0){
        //如果栈不为空 ,进行访问栈顶的元素并且出栈
            struct  Person * pTop=  top_SeqStack(stack);
            printf ("Top stack : Name =  %s , Age = %d \n",pTop->name,pTop->age);
            printf ("Pop stack\n");
            pop_SeqStack (stack);
        }
        printf ("%s\n",LINE);
        printf("stack size = %d\n", size_SeqStack (stack));
        printf ("%s\n",LINE);
        printf ("destory_SeqStack\n");
        destory_SeqStack(stack);
        printf("stack size = %d\n", size_SeqStack (stack));
        printf ("%s\n",LINE);
    }
    
    int main(){
        
    
        test01();
    
        return 0;
    
    
    }

运行结果  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 1]

### 2、栈（Stack）栈的链式存储 ###

//节点的结构体

struct StackNode{
        
        struct StackNode * next;//只维护指针域
    };

//链式的栈结构体

struct LStack{
        
    
        struct StackNode pHeader;//头节点
        int m_Size;//栈的大小
    
    };

//初始化栈

typedef void * LinkStack;
    
    //初始化栈
    LinkStack init_LinkStack(){
        
    
        struct LStack * myStack = malloc (sizeof( struct  LStack ));
    
        if(myStack == NULL){
        
            return NULL;
        }
    
        myStack->pHeader.next = NULL;
        myStack->m_Size = 0;
    
        return myStack;
    }

//入栈

void push_LinkStack(LinkStack stack,void * data){
        
    
        if(stack == NULL){
        
            return;
        }
        if(data == NULL){
        
            return;
        }
        //入栈 就是 头插入
    
        struct  LStack * myStack = stack;//(还原为原来的数据类型，因为用户只知道LinkStack而不知道LStack)
    
        //获取到用户数据的前四个字节
        struct StackNode * myNode = data;
    
        //插入节点
        myNode->next = myStack->pHeader.next;//将当前节点的指针域指向链表的头结点
        myStack->pHeader.next = myNode;//头结点指向插入的节点
    
        //更新栈的大小
        myStack->m_Size++;
    
    }

//出栈

void pop_LinkStack(LinkStack stack){
        
    
        if(stack == NULL){
        
            return;
        }
        struct LStack * myStack = stack;
    
        //如果是空栈就不出栈
        if(myStack->m_Size <= 0){
        
            return;
        }
        //保存第一个有数据的节点 栈顶的元素
        struct StackNode * pFirst = myStack->pHeader.next;
    
        myStack->pHeader.next = pFirst->next;//将第二个节点指针域当中指向第一个结点指针域指向的地方也就是下一个元素的地址
    
        //更新一下栈的大小
        myStack->m_Size--;
    
    }

//返回栈顶元素

void * top_LinkStack(LinkStack stack){
        
        if(stack == NULL){
        
            return NULL;
        }
        struct LStack * myStack = stack;
    
        if(myStack->m_Size <= 0){
        
            return NULL;
        }
        return myStack->pHeader.next;//将第一个有数据的结点返回就可以了
    }

//返回栈的大小

int size_LinkStack(LinkStack stack){
        
    
        if(stack == NULL){
        
            return -1;
        }
        struct LStack * myStack = stack;
        return myStack->m_Size;
    }

//判断是否为空

int isEmpty_LinkStack(LinkStack stack){
        
        if(stack == NULL){
        
            return -1;
        }
        struct LStack * myStack = stack;
        if(myStack->m_Size <=0){
        
            return 1;
        }
        return 0;
    }

//销毁

void destory_LinkStack(LinkStack stack){
        
        if(stack == NULL){
        
            return;
        }
        free (stack);
        stack = NULL;
    }

//测试

struct Person{
        
        char name[64];
        int age;
    };

测试代码以及全部代码

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    #define LINE "---------------------------------------\n"
    #define MAX 1024
    //节点的结构体
    struct StackNode{
        
        struct StackNode * next;//只维护指针域
    };
    //链式的栈结构体
    struct LStack{
        
    
        struct StackNode pHeader;//头节点
        int m_Size;//栈的大小
    
    };
    typedef void * LinkStack;
    
    //初始化栈
    LinkStack init_LinkStack(){
        
    
        struct LStack * myStack = malloc (sizeof( struct  LStack ));
    
        if(myStack == NULL){
        
            return NULL;
        }
    
        myStack->pHeader.next = NULL;
        myStack->m_Size = 0;
    
        return myStack;
    }
    
    //入栈
    void push_LinkStack(LinkStack stack,void * data){
        
    
        if(stack == NULL){
        
            return;
        }
        if(data == NULL){
        
            return;
        }
        //入栈 就是 头插入
    
        struct  LStack * myStack = stack;//(还原为原来的数据类型，因为用户只知道LinkStack而不知道LStack)
    
        //获取到用户数据的前四个字节
        struct StackNode * myNode = data;
    
        //插入节点
        myNode->next = myStack->pHeader.next;//将当前节点的指针域指向链表的头结点
        myStack->pHeader.next = myNode;//头结点指向插入的节点
    
        //更新栈的大小
        myStack->m_Size++;
    
    }
    
    //出栈
    void pop_LinkStack(LinkStack stack){
        
    
        if(stack == NULL){
        
            return;
        }
        struct LStack * myStack = stack;
    
        //如果是空栈就不出栈
        if(myStack->m_Size <= 0){
        
            return;
        }
        //保存第一个有数据的节点 栈顶的元素
        struct StackNode * pFirst = myStack->pHeader.next;
    
        myStack->pHeader.next = pFirst->next;//将第二个节点指针域当中指向第一个结点指针域指向的地方也就是下一个元素的地址
    
        //更新一下栈的大小
        myStack->m_Size--;
    
    }
    
    //返回栈顶元素
    void * top_LinkStack(LinkStack stack){
        
        if(stack == NULL){
        
            return NULL;
        }
        struct LStack * myStack = stack;
    
        if(myStack->m_Size <= 0){
        
            return NULL;
        }
        return myStack->pHeader.next;//将第一个有数据的结点返回就可以了
    }
    //返回栈的大小
    int size_LinkStack(LinkStack stack){
        
    
        if(stack == NULL){
        
            return -1;
        }
        struct LStack * myStack = stack;
        return myStack->m_Size;
    }
    
    //判断是否为空
    int isEmpty_LinkStack(LinkStack stack){
        
        if(stack == NULL){
        
            return -1;
        }
        struct LStack * myStack = stack;
        if(myStack->m_Size <=0){
        
            return 1;
        }
        return 0;
    }
    //销毁
    void destory_LinkStack(LinkStack stack){
        
        if(stack == NULL){
        
            return;
        }
        free (stack);
        stack = NULL;
    }
    //测试
    struct Person{
        
        struct StackNode node;
        char name[64];
        int age;
    };
    
    void test01(){
        
    
        //准备数据
        struct  Person p1 = {
        NULL,"aaa",10};
        struct  Person p2 = {
        NULL,"bbb",20};
        struct  Person p3 = {
        NULL,"ccc",30};
        struct  Person p4 = {
        NULL,"ddd",40};
        struct  Person p5 = {
        NULL,"fff",50};
        LinkStack linkStack = init_LinkStack();
    
        push_LinkStack(linkStack,&p1);
        push_LinkStack(linkStack,&p2);
        push_LinkStack(linkStack,&p3);
        push_LinkStack(linkStack,&p4);
        push_LinkStack(linkStack,&p5);
        printf ("LinkStack size :%d\n", size_LinkStack (linkStack));
        printf (LINE);
    
        struct  Person * p = top_LinkStack (linkStack);
        printf ("name: %s age:%d\n",p->name,p->age);
        printf (LINE);
        while (isEmpty_LinkStack (linkStack) == 0){
        
            struct  Person * pTop = top_LinkStack (linkStack);
            printf ("name: %s age:%d\n",pTop->name,pTop->age);
            //出栈
            pop_LinkStack (linkStack);
    
        }
        printf (LINE);
    
        printf ("LinkStack size :%d\n", size_LinkStack (linkStack));
    
        printf("destory_LinkStack");
    
        destory_LinkStack (linkStack);
        printf (LINE);
    
    }
    
    
    int main(){
        
        test01();
    
        return 0;
    }

运行结果  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_19_color_FFFFFF_t_70_g_se_x_16]

### 3、栈应用 ###

#### （1）就近匹配 ####

几乎所有的编译器都具有检测括号是否匹配的能力,

那么如何实现编译器中的符号成对

检测?  
如下字符串:,

5+5*(6)+9/3*1)-(1+3(

算法思路  
从第一个字符开始扫描  
当遇见普通字符时忽略  
当遇见左括号时压入柱中·  
当遇见右括号时从楼中弹出栈顶符号  
并进行匹配匹配成功:继续读入下一个字符  
匹配失败:立即停止  
并报错·结束:  
成功:所有字符扫描完毕，且栈为空  
失败:匹配失败或所有字符扫描完毕但栈非空

√总结  
当需要检测成对出现但又互不相邻的事物时可以使用钱“后进先出”的特性  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 2]

##### 1）实现右括号匹配左括号代码实现 #####

int IsLeft(char ch ){
        
        return ch == '(';
    }
    //判断字符是否是右括号
    int IsRigt(char ch ){
        
        return ch == ')';
    }
    void printError(char * str, char * errMsg){
        
    
        printf ("What is the wrong message:%s\n",errMsg);
        printf ("Wrong symbol:%s\n",str);
    
    }

void test01(){
        
        char * str = "5+5*(6)+9/3*1)-(1+3(";
        char * p = str;//定义指针p指向字符串第一个位置
        //初始化栈
        seqStack  stack =  init_SeqStack();
        while (* p != '\0'){
        
            //如果在左括号  入栈
            if(IsLeft (*p)){
        
                push_SeqStack (stack,p);
            }
            //如果是右括号，就弹出栈中栈顶元素
            if(IsRigt (*p)){
        
                //如果栈的元素个数大于0，可以匹配
                if(size_SeqStack (stack) > 0){
        
                    //弹出栈顶元素
                    pop_SeqStack (stack);
                }else{
        
                    //空栈匹配失败
                    printError(str,"The right bracket does not match the left bracket");
                    break;
                }
            }
            p++;
        }
    }
    
    int main () {
        
        test01();
        printf ("Hello, World!\n");
        return 0;
    }

运行结果  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 3]  
设置打印显示出错的地方  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 4]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 5]  
防止手残代码

int IsLeft(char ch ){
        
        return ch == '(';
    }
    //判断字符是否是右括号
    int IsRigt(char ch ){
        
        return ch == ')';
    }
    void printError(char * str, char * errMsg, char * pos){
        
    
        printf ("What is the wrong message:%s\n",errMsg);
        printf ("Wrong symbol:\n%s\n",str);
    
        //计算打印空格的数量
        int num = pos - str;
        for(int i = 0; i < num;i++){
        
            printf (" ");
        }
        printf ("^\n");
    
    }
    
    void test01(){
        
        char * str = "5+5*(6)+9/3*1)-(1+3(";
        char * p = str;//定义指针p指向字符串第一个位置
        //初始化栈
        seqStack  stack =  init_SeqStack();
        while (* p != '\0'){
        
            //如果在左括号  入栈
            if(IsLeft (*p)){
        
                push_SeqStack (stack,p);
            }
            //如果是右括号，就弹出栈中栈顶元素
            if(IsRigt (*p)){
        
                //如果栈的元素个数大于0，可以匹配
                if(size_SeqStack (stack) > 0){
        
                    //弹出栈顶元素
                    pop_SeqStack (stack);
                }else{
        
                    //空栈匹配失败
                    printError(str,"The right bracket does not match the left bracket",p);
                    break;
                }
            }
            p++;
        }
    }
    
    int main () {
        
        test01();
        printf ("Hello, World!\n");
        return 0;
    }

运行结果  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_15_color_FFFFFF_t_70_g_se_x_16]

##### 2）实现左括号匹配右括号代码实现 #####

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 6]  
防止手残 全部的全都代码直接复制运行即可

#include <stdio.h>
    #include "stack.h"
    seqStack init_SeqStack(){
        
    
        struct SStack *  stack = malloc (sizeof (struct SStack));
    
        if(stack == NULL){
        
            return NULL;
        }
        //清空数组当中的元素
        //将栈当中的数据清空，清空为0，清空的大小为 栈当中每个元素sizeof(void *)乘以每个元素的大小
        memset (stack->data,0,sizeof(void *) *MAX );
        stack->m_Size = 0;
    
        return stack;
    
    }
    //入栈
    void push_SeqStack(seqStack stack,void * data){
        
    
        if(stack == NULL){
        
            return;
        }
        if(data == NULL){
        
            return;
        }
        //判断栈是否已经满了,如果满了不可以再入栈了
        struct SStack * myStack = stack;
        if(myStack->m_Size == MAX){
        
            return;
        }
        myStack->data[myStack->m_Size] = data;//入栈尾插
        myStack->m_Size++;//更新栈的大小
    
    }
    //出栈
    void pop_SeqStack(seqStack stack){
        
    
        if(stack == NULL){
        
            return;
        }
        //如果是空栈不执行空栈
        struct SStack * myStack = stack;
        if(myStack->m_Size <= 0){
        
            return;
        }
        //执行出栈
        myStack->data[myStack->m_Size-1] = NULL;
        //更新栈的大小
        myStack->m_Size -- ;
    
    }
    //获取栈顶元素
    void * top_SeqStack(seqStack stack){
        
    
        if(stack == NULL){
        
            return NULL;
        }
        struct  SStack * myStack = stack;
    
        //如果是空栈
        if(myStack->m_Size == 0){
        
            return NULL;
        }
        return myStack->data[myStack->m_Size-1];
    
    }
    //栈的大小
    int size_SeqStack(seqStack stack){
        
    
        if(stack == NULL){
        
            return -1;
        }
        struct SStack * myStack = stack;
        return myStack->m_Size;
    }
    //判断栈是否为空
    int isEmpty_SeqStack(seqStack stack){
        
    
        if(stack == NULL){
        
            return -1;//真
        }
        struct SStack * myStack = stack;
        if(myStack->m_Size <= 0){
        
            return -1;//真
        }
        return 0;//返回假代表不是空栈
    }
    
    
    //销毁栈
    void destory_SeqStack(seqStack stack){
        
        if(stack == NULL)
        {
        
            return;
        }
        free (stack);
        stack = NULL;
    
    }
    
    /*
    从第一个字符开始扫描
    当遇见普通字符时忽略
    当遇见左括号时压入柱中·
    当遇见右括号时从楼中弹出栈顶符号
    并进行匹配匹配成功:继续读入下一个字符
    匹配失败:立即停止
    并报错·结束:
    成功:所有字符扫描完毕，且栈为空
    失败:匹配失败或所有字符扫描完毕但栈非空
     */
    
    //判断字符是否是左括号
    
    int IsLeft(char ch ){
        
        return ch == '(';
    }
    //判断字符是否是右括号
    int IsRigt(char ch ){
        
        return ch == ')';
    }
    void printError(char * str, char * errMsg, char * pos){
        
    
        printf ("What is the wrong message:%s\n",errMsg);
        printf ("Wrong symbol:\n%s\n",str);
    
        //计算打印空格的数量
        int num = pos - str;
        for(int i = 0; i < num;i++){
        
            printf (" ");
        }
        printf ("^\n");
    
    }
    
    void test01(){
        
        char * str = "5+5*(6)+9/3*1-(1+3(";
        char * p = str;//定义指针p指向字符串第一个位置
        //初始化栈
        seqStack  stack =  init_SeqStack();
        while (* p != '\0'){
        
            //如果在左括号  入栈
            if(IsLeft (*p)){
        
                push_SeqStack (stack,p);
            }
            //如果是右括号，就弹出栈中栈顶元素
            if(IsRigt (*p)){
        
                //如果栈的元素个数大于0，可以匹配
                if(size_SeqStack (stack) > 0){
        
                    //弹出栈顶元素
                    pop_SeqStack (stack);
                }else{
        
                    //空栈匹配失败
                    printError(str,"The right bracket does not match the left bracket",p);
                    break;
                }
            }
            p++;
        }
        //判断是否为空栈
        while (size_SeqStack (stack) > 0){
        //如果栈当中元素大于0
    
            printError (str,"The left bracket does not match the right bracket", top_SeqStack (stack));
            //弹出栈顶元素
            pop_SeqStack (stack);
        }
        //销毁栈
        destory_SeqStack (stack);
        stack = NULL;
    }
    
    int main () {
        
        test01();
        printf ("Hello, World!\n");
        return 0;
    }

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 7]

#### （2）中缀表达式和后缀表达式 ####

*  后缀表达式(由波兰科学家在20世纪50年代提出)
    
     *  将运算符放在数宁后面`===》` 符合计算机运算
     *  我们习惯的数学表达式叫做中缀表达式`===》`符合人关思考习惯
 *  实例
    
     *  `5 +4 = >54 +`
     *  `1+2*3 => 12 3*+`
     *  `8+ ( 3- 1)* 5 = >831 - 5*+e`
 *  中缀转后缀算法∶  
    遍历中缀表达式中的数字和符号∶
    
     *  对于数字∶直接输出
     *  对于符号∶
        
         *  左括号∶进栈
         *  运算符号∶与栈页符号进行优先级比较
         *  运算符号∶与栈顶符号进行优先级比较  
            》若栈顶符号优先级低:此符号进栈  
            (默认栈顶若是左括号，左括号优先级最低)  
            》若栈顶符号优先级不低∶将栈顶符号弹出并输出，之后进栈
         *  右括号∶将栈顶符号弹出并输出，  
            直到匹配左括号,将左括号和右括号同时舍弃遍历结束:将栈中的所有符号弹出并输出

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_18_color_FFFFFF_t_70_g_se_x_16]

![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 8]  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 9]

*  基于后缀表达式计算
    
     *  思考  
        计算机是如何基于后缀表达式计算的?  
        例如∶`8 3 1 - 5 *`
     *  计算规则,  
        遍历后缀表达式中的数字和符号
        
         *  对于数字∶进栈。
         *  对于符号:
         *  从栈中弹出右操作数
         *  从栈中弹出左操作数
         *  根据符号进行运算,
         *  将运算结果压入栈中

遍历结束∶栈中的唯一数字为计算结果  
![在这里插入图片描述][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 10]

[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/c42dd9a34308437881d6d5eeb900c7ed.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/df605c1745484ebfbffc4e626731a096.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_19_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/a87a14de43e043e8b73913b90b4f97a5.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 2]: /images/20220829/d063396c29b84e49825450515842891c.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 3]: /images/20220829/27d14740b6e64c55b20b6fa59352241f.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 4]: /images/20220829/9f17a071a9d14ff5991518f025dd0e09.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 5]: /images/20220829/3edcbe0d9ccc4b4bbe757686c394a87d.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_15_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/e56e226bd797469daa9426867aeba533.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 6]: /images/20220829/7c91844d735f44e8be183d9b9f60e097.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 7]: /images/20220829/6730f403d7514ded86a8166257231620.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_18_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/033bad1387e045b3b19e0a3d7a78a964.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 8]: /images/20220829/17ced92a89674efb88379566e05e4fe2.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 9]: /images/20220829/f7440b117fe445f882d7254be4621772.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6JOd55uS5a2QaXRibHVlYm94_size_20_color_FFFFFF_t_70_g_se_x_16 10]: /images/20220829/65f2548dad4843359f3ddb6a0898ec1b.png