C语言数据结构篇——用栈实现四则运算

作者名：Demo不是emo 

主页面链接：主页传送门
创作初心：舞台再大，你不上台，永远是观众，没人会关心你努不努力，摔的痛不痛，他们只会看你最后站在什么位置，然后羡慕或鄙夷
座右铭：不要让时代的悲哀成为你的悲哀
专研方向：网络安全，数据结构

每日emo：我爱你，希望你有机会可以把这句话还给我

我们都知道给计算机一个运算式时计算机可以迅速计算出其结果，若运算式有错误，计算机也能立刻检查出错误并报告，那么计算机是如何做到的呢？

其实计算机在进行运算的过程中，将运算表达式换成了逆波兰表达式，这是一种不需要括号的后缀表达式（我们常用的是中缀表达式），再对该后缀表达式进行计算，进而得出答案；在中缀表达式转换的过程中，这些数据保存在栈中，需要计算时再利用栈先进后出的特点进行字符的匹配检查。 

一，中缀表达式转后缀表达式

1、遵循的原则

中缀表达式转后缀表达式的数据用栈来存储，在遍历中缀表达式的时遵循以下原则：

●对于数字，直接输出

●对于符号：

左括号：不管栈中是否有元素直接进栈

运算符：若栈为空：直接进栈

               若栈中有元素，则与栈顶符号进行优先级比较；

                        若新符号优先级高（默认左括号优先级最低），则直接入栈；

                        否则就需要弹 出并输出栈顶元素，并将新符号压栈，

右括号：不断将栈顶符号弹出并输出，直到栈顶符号与右括号匹配（即栈顶符号是左括号），再讲栈顶的左括号弹出即可（只需要弹出，不需要输出）

优先级大小：乘除号>加减号>左括号

●遍历结束后，将栈内的元素全部弹出并输出

2、图文举例（超详细）

下面以中缀表达式“1+3*(2+5)”转换为后缀表达式的过程为例

第一步：遍历中缀表达式，第一个读取到的字符是1，按照转换的原则“数字直接输出”，所以将‘1’直接添加到我们的结果中，如图：

第二步： 第二个读取到的字符是‘+’,为运算符，此时栈中为空，所以直接将‘+’入栈，如图：

第三步：遍历到‘3’，与第一步同理，数字直接输出，所以将‘3’添加到结果中，此时结果为1 3； 

第四步：遍历到‘*’，栈不为空，所以与栈顶元素比较优先级，此时栈顶元素为‘+’，‘*’的优先级比‘+’号高，所以还是将‘*’直接入栈，与第二步步操作相同，这里就不多画图了。

第五步： 此时遍历到了‘（’，因为“左括号直接入栈”，所以同前一步一样，将‘（’入栈即可。

第六步：此时遍历到了‘’2”，是数字，同理与，第一步一样，将‘2’添加到结果中，此时结果为1 3 2

 第七步：此时遍历到了‘+’，是运算符，所以需要与栈顶的‘（’比较优先级大小，‘+’的优先级高，所以将‘+’直接压栈即可。

第八步：此时遍历到了‘5’，是数字所以继续将‘5’添加到结果，此时遍历情况与结果如图：

第九步：遍历到了‘)’ ,所以需要进行括号匹配,从栈中不断弹出并输出栈顶元素,直到匹配到的栈顶元素是左括号，再将左括号弹出即可，具体步骤如图：

第十步：中缀表达式已经遍历完，但栈中还有元素，所以将栈中全部元素弹出并输出（添加到结果中）即可，最后如图：

此时的结果“1 3 2 5 + * +”就是我们的中缀表达式 “1+3*(2+5)”转换的后缀的表达式

3、编程实现

1，引入链栈

因为该转换我是用的链栈实现的，所以我们先引入使用链栈需要的函数，方便待会进行操作，这里就不多讲了，对链栈不太熟悉的同学也可以看我的上一篇博客，链接如下：C语言数据结构篇——栈的链式存储_Grande joie的博客-CSDN博客_c语言栈的链式存储结构 

下面为此题需要的链栈相关封装函数：

typedef struct node//数据节点，压栈和出栈都在栈顶进行(这里的栈顶指与头结点连接第一个数据节点)
{
    char val;//数据域
    struct node* next;//指针域
}pnode;
typedef struct seqstack
{
    int size;//记录栈的大小
    pnode* top;//指向栈顶元素
}phead;
phead*  initstack()//创建栈
{
    phead* istack=(phead*)malloc(sizeof(phead));//为头节点分配空间
    if(istack!=NULL)//健壮性判断
    {
        istack->top=NULL;
        istack->size=0;
    }
    return istack;//返回创建好的头结点
}
int isempty(phead* istack)//判断栈为是否空
{
    if(istack->top==NULL)
    {
        return 1;//栈为空
    }
    return 0;//栈不为空
}
pnode* seqstack_top(phead* istack)//获取栈顶元素的数据节点
{
    if(istack->size!=0)//栈不为空
    {
        return istack->top;//返回的是栈顶的数据节点而不是栈顶的元素
    }
    return NULL;
}
pnode* seqstack_pop(phead* istack)//弹出栈顶元素
{
    if(isempty(istack)==0)//栈不为空
    {
        pnode* account=istack->top;//记录栈顶的数据节点
        istack->top=istack->top->next;//指向栈顶下一个元素
        istack->size--;//记录栈的大小
        return account;//返回弹出的数据节点
    }
    return NULL;
}
void seqstack_push(phead* istack,char x)//将字符压栈(入栈)
{
   pnode* temp;//进行压栈的数据节点
   temp=(pnode*)malloc(sizeof(pnode));
   temp->val=x;//填充数据域
   temp->next=istack->top;//连接栈顶的数据节点
   istack->top=temp;//充当栈顶
   istack->size++;//记录栈大小的变化
   return;
}

2，封装相关函数

链栈的相关函数我们已经引入，让我们再来封装中缀转后缀需要的函数，如下：

char buffer[256]={0};//即对数组中每个数据都初始化为'\0'(\0的ascill码是0)
//上方的例子中始终有一个“结果”用来保存输出的数据，这里的buffer就充当“结果”，用来保存输出的数据
 void char_put(char ch)//用来将字符放入结果串，方便使用
 {
     static int index=0;//static定义静态变量,放函数中表示index只初始化一次,只保留index的改变
     buffer[index++]=ch;
 }
 int priority(char ch)//返回该字符的优先级
 {
     int ret=0;//可以达到题目中'('默认优先级最小的要求
     switch(ch)
     {
        case '+'://case穿透,即上一个case没有break语句时会继续向下执行
        case '-':
            ret=1;
            break;
        case '*':
        case '/':
            ret=2;
            break;
        default://这里直接break也可以
            break;
     }
     return ret;
 }
 int is_number(char ch)//判断遍历到的字符是不是数字
 {
     return(ch>='0'&&ch<='9');//数字返回1，否则返回0
 }
 int is_operator(char ch)//判断遍历到的字符是不是运算符
 {
     return(ch=='+'||ch=='-'||ch=='*'||ch=='/');
 }
 int is_left(char ch)//是不是左括号
 {
     return(ch=='(');
 }
 int is_right(char ch)//是不是右括号
 {
     return(ch==')');
 }
 int transform(char str[])//使用const保护数据,函数用来将中缀转换成后缀,str[]是中缀表达式
 {
     phead* istack=initstack();//创建一个栈
     int i=0;//作为遍历字符串的索引（下标）
     while(str[i]!='\0')//遍历整个字符串
    {
        //判断是不是数字
        if(is_number(str[i])==1)
        {
            if(is_number(str[i+1])==1)//后面1也是数字,则直接放
            {
                char_put(str[i]);//数字直接放入结果串(即输出)
            }
            else//后面不是数字,添加一个空格作为分隔符（数字与运算符间加空格以解决多位数问题）
            {
                char_put(str[i]);
                char_put(' ');
            }
        }
        //判断是不是运算符
        else if(is_operator((str[i]))==1)
        {
            if(str[i+1]=='0'&&str[i]=='/')
            {
                printf("ILLEGAL");//解决除数为0的问题
                return 0;
            }
            if(isempty(istack)==0)//栈不为空
            {
                while((isempty(istack)==0)&&(priority(str[i])<=(priority(seqstack_top(istack)->val))))//栈不为空并且新运算符优先级不高于栈顶
                {
                    char_put(seqstack_pop(istack)->val);//满足条件的栈顶就弹出直到不满足
                    char_put(' ');//同样为了解决多位数问题
                }
            }
            seqstack_push(istack,str[i]);//再将该运算符入栈
        }
        else if(is_left(str[i]))//左括号则直接入栈
        {
            seqstack_push(istack,str[i]);
        }
        else if(is_right(str[i]))//判断是不是右括号
        {
            while(is_left(seqstack_top(istack)->val)!=1)//栈顶不是左括号的情况
            {
                char_put(seqstack_pop(istack)->val);//将栈顶元素弹出并存储到结果串
                if(isempty(istack)==1)//栈为空仍未找到左括号
                {
                    printf("没有匹配到左括号\n");
                    return -1;
                }
            }
            //执行到此时则代表匹配到了左括号
            seqstack_pop(istack);
            //弹出左括号,这里并不用保存,即两个括号相抵消
        }
        else
        {
            printf("有不能识别的字符\n");
            return -1;
        }
        i++;
    }
    //遍历完了已经
    if(str[i]=='\0')//成功遍历到字符串末尾
    {
        while(isempty(istack)==0)//弹出全部栈中元素
        {
            if(seqstack_top(istack)->val=='(')//栈顶元素为左括号
            {
                printf("有没有匹配到的'(',缺少')'\n");
                return -1;
            }
            char_put(seqstack_pop(istack)->val);//将栈中元素放入最终串
        }
    }
    else
    {
        printf("遍历没有完成！\n");
    }
    return 1;
 }

3，完整代码

到这里我们中缀表达式换后缀表达式就完成了，让我们来试试：

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node//压栈和出栈都在栈顶进行(这里的栈顶指前一段)
{
    char val;//数据
    struct node* next;//指针
}pnode;
typedef struct seqstack
{
    int size;//记录栈的大小
    pnode* top;//指向栈顶元素
}phead;
phead*  initstack()//创建栈
{
    phead* istack=(phead*)malloc(sizeof(phead));//为头节点分配空间
    if(istack!=NULL)//健壮性判断
    {
        istack->top=NULL;
        istack->size=0;
    }
    return istack;
}
int isempty(phead* istack)//判断栈为空
{
    if(istack->top==NULL)
    {
        return 1;//栈为空
    }
    return 0;//栈不为空
}
pnode* seqstack_top(phead* istack)//获取栈顶元素的数据节点
{
    if(istack->size!=0)//栈不为空
    {
        return istack->top;//返回的是栈顶的数据节点而不是栈顶的元素
    }
    return NULL;
}
pnode* seqstack_pop(phead* istack)//弹出栈顶元素
{
    if(isempty(istack)==0)//栈不为空
    {
        pnode* account=istack->top;//记录栈顶的数据节点
        istack->top=istack->top->next;//指向栈顶下一个元素
        istack->size--;//记录栈的大小
        return account;//返回弹出的数据节点
    }
    return NULL;
}
void seqstack_push(phead* istack,char x)//压栈(入栈)
{
   pnode* temp;//进行压栈的数据节点
   temp=(pnode*)malloc(sizeof(pnode));
   temp->val=x;//填充数据域
   temp->next=istack->top;//连接栈顶的数据节点
   istack->top=temp;//充当栈顶
   istack->size++;//记录栈大小的变化
   return;
}
 //下面是中缀表达式转后缀表达式的函数
 char buffer[256]={0};//即对数组中每个数据都初始化为'\0'(\0的ascill码是0)
 //buffer为结果串
 void char_put(char ch)//用来将字符放入放入结果串
 {
     static int index=0;//static定义静态变量,放函数中表示index只初始化一次,只保留index的改变
     buffer[index++]=ch;
 }
 int priority(char ch)//用来比较优先级
 {
     int ret=0;
     switch(ch)
     {
        case '+'://case穿透,即上一个case没有break语句时会继续向下执行
        case '-':
            ret=1;
            break;
        case '*':
        case '/':
            ret=2;
            break;
        default://这里直接break也可以
            break;
     }
     return ret;
 }
 int is_number(char ch)//是不是数字
 {
     return(ch>='0'&&ch<='9');//数字返回1，否则返回0
 }
 int is_operator(char ch)//是不是运算符
 {
     return(ch=='+'||ch=='-'||ch=='*'||ch=='/');
 }
 int is_left(char ch)//是不是左括号
 {
     return(ch=='(');
 }
 int is_right(char ch)//是不是右括号
 {
     return(ch==')');
 }
 int transform(char str[])//使用const保护数据,函数用来将中缀转换成后缀
 {
     phead* istack=initstack();//创建一个栈
     int i=0;
     while(str[i]!='\0')//遍历整个字符串
    {
        //判断是不是数字
        if(is_number(str[i])==1)
        {
            if(is_number(str[i+1])==1)//后面1也是数字,则直接放
            {
                char_put(str[i]);//数字直接放入结果串(即输出)
            }
            else//后面不是数字,添加一个空格作为分隔符
            {
                char_put(str[i]);
                char_put(' ');
            }
        }
        else if(is_operator((str[i]))==1)
        {
            if(str[i+1]=='0'&&str[i]=='/')
            {
                printf("ILLEGAL");
                return 0;
            }
            if(isempty(istack)==0)//栈不为空
            {
                while((isempty(istack)==0)&&(priority(str[i])<=(priority(seqstack_top(istack)->val))))//栈不为空并且新运算符优先级不高于栈顶
                {
                    char_put(seqstack_pop(istack)->val);//满足条件的栈顶就弹出直到不满足条件
                    char_put(' ');
                }
            }
            seqstack_push(istack,str[i]);//再将该运算符入栈
        }
        else if(is_left(str[i]))//左括号直接入栈
        {
            seqstack_push(istack,str[i]);
        }
        else if(is_right(str[i]))//判断是不是右括号
        {
            while(is_left(seqstack_top(istack)->val)!=1)//栈顶不是左括号的情况
            {
                char_put(seqstack_pop(istack)->val);//弹出并存储到结果串
                if(isempty(istack)==1)//栈为空仍未找到左括号
                {
                    printf("没有匹配到左括号\n");
                    return -1;
                }
            }
            //此时匹配到了左括号
            seqstack_pop(istack);
            //弹出左括号,这里并不用保存,即两个括号相抵消
        }
        else
        {
            printf("有不能识别的字符\n");
            return -1;
        }
        i++;
    }
    //遍历完了已经
    if(str[i]=='\0')//成功遍历到字符串末尾
    {
        while(isempty(istack)==0)//弹出全部栈中元素
        {
            if(seqstack_top(istack)->val=='(')//栈顶元素为左括号
            {
                printf("有没有匹配到的'(',缺少')'\n");
                return -1;
            }
            char_put(seqstack_pop(istack)->val);//将栈中元素放入最终串
        }
    }
    else
    {
        printf("遍历没有完成！\n");
    }
    return 1;
 }
int main()
{
    char str[1024]={0};//将数组每个元素赋值为'\0'
    printf("请输入四则运算表达式:\n");
    scanf("%s",str);
    int number=transform(str);
    if(number==-1)
    {
        printf("表达式转换错误:\n");
    }
    else if(number==1)
    {
        printf("转化后的表达式: %s\n",buffer);
    }
    else
    {
        return 0;
    }
}

随便写一个中缀表达式看看效果吧。效果如下：

请输入四则运算表达式:
2*(1+2)-3
转化后的表达式: 2 1 2 +* 3 - 

到这里我们的中缀表达式换后缀表达式就完成了，接下来就是对后缀表达式的计算了 

二，后缀表达式的计算 

 将中缀表达式换成后缀表达式后，计算机会根据后缀表达式进行求值运算，计算过程中的数据也是存储在栈中，但相比中缀表达式转后缀表达式会更简单一点。

1、计算原则 

●对于数字，直接进栈

●对于符号，先弹出一个栈顶元素作为右操作数（即待会运算时放在运算符右边），再弹出一个元素作为左操作数，根据符号运算出结果，再将结果压入栈中。

●遍历结束，栈中剩下的最后一个数就是运算结果 

2、图文举例： 

这里以刚转换好的后缀表达式“1 3 2 5 + * +”为例进行计算，对后缀表达式进行遍历；

第一~四步： 前四位都是数字，按照原则直接全部进栈，如图：

第五步：此时遍历到了‘+’号，所以将栈顶的‘5’弹出作为右操作数，再将‘2’弹出作为左操作数，计算2+5的运算结果为7，再将7压栈，此时栈中数据从栈顶到栈尾依次是为“7 3 1”，如图： 

第六步：此时遍历到“*”号，则依次弹出两个元素并计算，即3*7=21，在将21入栈，此时栈中元素按栈顶到栈底为“21 1”；

第七步: 此时遍历到‘+’号，即的1+21=22；将22压栈

第八步：此时后缀表达式遍历完了且栈中只有一个元素，所以栈中的元素即为最后答案，所以结果为22 

 再回想一下我们原来的中缀表达式“1+3*（2+5）”，也等于22，说明我们的计算没有问题

3、编程实现

[1]、引入链栈（整型）

因为计算过程中我们数据存在栈中，所以我们也要引入链栈，但是这里因为要计算压栈，以及把运算结果压栈等操作，这里链栈的数据节点的数据域为int类型更合适，对应的部分函数也需要更改返回值，所以需要对上方封装的链栈函数进行部分修改，这里我们就复制下来，改一小部分地方，再给这些函数改一个新的名字就可以了,此处栈涉及到的封装函数如下：

typedef struct node1//这里的栈是整型栈
{
    int val;//数据
    struct node1* next;//指针
}pnode1;
typedef struct seqstack1
{
    int size;//记录栈的大小
    pnode1* top;//指向栈顶元素
}phead1;
phead1*  initstack1()//创建栈
{
    phead1* istack=(phead1*)malloc(sizeof(phead1));//为头节点分配空间
    if(istack!=NULL)//健壮性判断
    {
        istack->top=NULL;
        istack->size=0;
    }
    return istack;
}
int isempty1(phead1* istack)//判断栈为空
{
    if(istack->top==NULL)
    {
        return 1;//栈为空
    }
    return 0;//栈不为空
}
int seqstack_top1(phead1* istack)//获取栈顶元素
{
    if(istack->size!=0)//栈不为空
    {
        return istack->top->val;//返回的是栈顶的数据
    }
    return 99999;
}
int seqstack_pop1(phead1* istack)//弹出栈顶元素
{
    if(isempty1(istack)==0)//栈不为空
    {
        int account=istack->top->val;//记录栈顶的数据节点
        istack->top=istack->top->next;//指向栈顶下一个元素
        istack->size--;//记录栈的大小
        return account;//返回弹出的数据节点
    }
    return 99999;
}
void seqstack_push1(phead1* istack,int x)//压栈(入栈)
{
   pnode1* temp;//进行压栈的数据节点
   temp=(pnode1*)malloc(sizeof(pnode1));
   temp->val=x;//填充数据域
   temp->next=istack->top;//连接栈顶的数据节点
   istack->top=temp;//充当栈顶
   istack->size++;//记录栈大小的变化
   return;
}

[2]、封装相关的函数 

 int express(int left,int right,char op)//op为运算符,返回运算结果
 {
     switch (op)
     {
        case '+':
            return left+right;
        case '-':
            return left-right;
        case '*':
            return left*right;
        case '/':
            if(right==0)
            {
                return 999;
            }
            return left/right;
        default:
            break;
     }
     return -1;
 }
 int getsize(phead1* stack)//获取链栈的大小
 {
     return stack->size;
 }
 int calculate(char str[])//计算后缀表达式
 {
     phead1* istack2=initstack1();//创建栈
     int i=0;
     while(str[i]!='\0')//遍历整个后缀表达式
    {
        char a[6]={0};
        int index=0;
        if(is_number(str[i])==1)
        {
            while(is_number(str[i])==1)
            {
                a[index]=str[i];
                index++;
                i++;
            }
            //成功读取数字
            seqstack_push1(istack2,atoi(a));//将该整数入栈，stoi函数可以将字符串改成数字形式
        }
        else if(is_operator(str[i])==1)
        {
            int right=seqstack_pop1(istack2);
            int left=seqstack_pop1(istack2);
            int ret=express(left,right,str[i]);
            if(ret==999)//被除数为0了
            {
                printf("ILLEGAL");
                return 999;
            }
            seqstack_push1(istack2,ret);//运算结果入栈
        }
        else if(str[i]==' ')//因为多位数的原因，我们的中缀表达式会有空格出现，直接遍历过去就行
        {

        }
        else
        {
            printf("error\n");
            break;
        }
        i++;
    }
    if(str[i]=='\0'&&getsize(istack2))
    {
        return seqstack_top1(istack2);
    }
    return 0;
 }

注意 ，计算后缀表达式涉及的函数包括前面的判断某个字符是不是数字，是不是操作符等函数，这里没有再多写

三，用栈实现四则运算的完整代码

（先把中缀表达式换成后缀表达式，再计算后缀表达式） 

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
typedef struct node//压栈和出栈都在栈顶进行(这里的栈顶指前一段)
{
    char val;//数据
    struct node* next;//指针
}pnode;
typedef struct seqstack
{
    int size;//记录栈的大小
    pnode* top;//指向栈顶元素
}phead;
phead*  initstack()//创建栈
{
    phead* istack=(phead*)malloc(sizeof(phead));//为头节点分配空间
    if(istack!=NULL)//健壮性判断
    {
        istack->top=NULL;
        istack->size=0;
    }
    return istack;
}
int isempty(phead* istack)//判断栈为空
{
    if(istack->top==NULL)
    {
        return 1;//栈为空
    }
    return 0;//栈不为空
}
pnode* seqstack_top(phead* istack)//获取栈顶元素的数据节点
{
    if(istack->size!=0)//栈不为空
    {
        return istack->top;//返回的是栈顶的数据节点而不是栈顶的元素
    }
    return NULL;
}
pnode* seqstack_pop(phead* istack)//弹出栈顶元素
{
    if(isempty(istack)==0)//栈不为空
    {
        pnode* account=istack->top;//记录栈顶的数据节点
        istack->top=istack->top->next;//指向栈顶下一个元素
        istack->size--;//记录栈的大小
        return account;//返回弹出的数据节点
    }
    return NULL;
}
void seqstack_push(phead* istack,char x)//压栈(入栈)
{
   pnode* temp;//进行压栈的数据节点
   temp=(pnode*)malloc(sizeof(pnode));
   temp->val=x;//填充数据域
   temp->next=istack->top;//连接栈顶的数据节点
   istack->top=temp;//充当栈顶
   istack->size++;//记录栈大小的变化
   return;
}
 //下面是中缀表达式转后缀表达式的函数
 char buffer[256]={0};//即对数组中每个数据都初始化为'\0'(\0的ascill码是0)
 //buffer为结果串
 void char_put(char ch)//用来将字符放入放入结果串
 {
     static int index=0;//static定义静态变量,放函数中表示index只初始化一次,只保留index的改变
     buffer[index++]=ch;
 }
 int priority(char ch)//用来比较优先级
 {
     int ret=0;
     switch(ch)
     {
        case '+'://case穿透,即上一个case没有break语句时会继续向下执行
        case '-':
            ret=1;
            break;
        case '*':
        case '/':
            ret=2;
            break;
        default://这里直接break也可以
            break;
     }
     return ret;
 }
 int is_number(char ch)//是不是数字
 {
     return(ch>='0'&&ch<='9');//数字返回1，否则返回0
 }
 int is_operator(char ch)//是不是运算符
 {
     return(ch=='+'||ch=='-'||ch=='*'||ch=='/');
 }
 int is_left(char ch)//是不是左括号
 {
     return(ch=='(');
 }
 int is_right(char ch)//是不是右括号
 {
     return(ch==')');
 }
 int transform(char str[])//使用const保护数据,函数用来将中缀转换成后缀
 {
     phead* istack=initstack();//创建一个栈
     int i=0;
     while(str[i]!='\0')//遍历整个字符串
    {
        //判断是不是数字
        if(is_number(str[i])==1)
        {
            if(is_number(str[i+1])==1)//后面1也是数字,则直接放
            {
                char_put(str[i]);//数字直接放入结果串(即输出)
            }
            else//后面不是数字,添加一个空格作为分隔符
            {
                char_put(str[i]);
                char_put(' ');
            }
        }
        else if(is_operator((str[i]))==1)
        {
            if(str[i+1]=='0'&&str[i]=='/')
            {
                printf("ILLEGAL");
                return 0;
            }
            if(isempty(istack)==0)//栈不为空
            {
                while((isempty(istack)==0)&&(priority(str[i])<=(priority(seqstack_top(istack)->val))))//栈不为空并且新运算符优先级不高于栈顶
                {
                    char_put(seqstack_pop(istack)->val);//满足条件的栈顶就弹出直到不满足条件
                    char_put(' ');
                }
            }
            seqstack_push(istack,str[i]);//再将该运算符入栈
        }
        else if(is_left(str[i]))//左括号直接入栈
        {
            seqstack_push(istack,str[i]);
        }
        else if(is_right(str[i]))//判断是不是右括号
        {
            while(is_left(seqstack_top(istack)->val)!=1)//栈顶不是左括号的情况
            {
                char_put(seqstack_pop(istack)->val);//弹出并存储到结果串
                if(isempty(istack)==1)//栈为空仍未找到左括号
                {
                    printf("没有匹配到左括号\n");
                    return -1;
                }
            }
            //此时匹配到了左括号
            seqstack_pop(istack);
            //弹出左括号,这里并不用保存,即两个括号相抵消
        }
        else
        {
            printf("有不能识别的字符\n");
            return -1;
        }
        i++;
    }
    //遍历完了已经
    if(str[i]=='\0')//成功遍历到字符串末尾
    {
        while(isempty(istack)==0)//弹出全部栈中元素
        {
            if(seqstack_top(istack)->val=='(')//栈顶元素为左括号
            {
                printf("有没有匹配到的'(',缺少')'\n");
                return -1;
            }
            char_put(seqstack_pop(istack)->val);//将栈中元素放入最终串
        }
    }
    else
    {
        printf("遍历没有完成！\n");
    }
    return 1;
 }






 //下方为计算后缀表达式需要的函数
 typedef struct node1//这里的栈是整型栈
{
    int val;//数据
    struct node1* next;//指针
}pnode1;
typedef struct seqstack1
{
    int size;//记录栈的大小
    pnode1* top;//指向栈顶元素
}phead1;
phead1*  initstack1()//创建栈
{
    phead1* istack=(phead1*)malloc(sizeof(phead1));//为头节点分配空间
    if(istack!=NULL)//健壮性判断
    {
        istack->top=NULL;
        istack->size=0;
    }
    return istack;
}
int isempty1(phead1* istack)//判断栈为空
{
    if(istack->top==NULL)
    {
        return 1;//栈为空
    }
    return 0;//栈不为空
}
int seqstack_top1(phead1* istack)//获取栈顶元素
{
    if(istack->size!=0)//栈不为空
    {
        return istack->top->val;//返回的是栈顶的数据
    }
    return 99999;
}
int seqstack_pop1(phead1* istack)//弹出栈顶元素
{
    if(isempty1(istack)==0)//栈不为空
    {
        int account=istack->top->val;//记录栈顶的数据节点
        istack->top=istack->top->next;//指向栈顶下一个元素
        istack->size--;//记录栈的大小
        return account;//返回弹出的数据节点
    }
    return 99999;
}
void seqstack_push1(phead1* istack,int x)//压栈(入栈)
{
   pnode1* temp;//进行压栈的数据节点
   temp=(pnode1*)malloc(sizeof(pnode1));
   temp->val=x;//填充数据域
   temp->next=istack->top;//连接栈顶的数据节点
   istack->top=temp;//充当栈顶
   istack->size++;//记录栈大小的变化
   return;
}
 int express(int left,int right,char op)//op为运算符,返回运算结果
 {
     switch (op)
     {
        case '+':
            return left+right;
        case '-':
            return left-right;
        case '*':
            return left*right;
        case '/':
            if(right==0)
            {
                return 999;
            }
            return left/right;
        default:
            break;
     }
     return -1;
 }
 int getsize(phead1* stack)
 {
     return stack->size;
 }
 int calculate(char str[])//计算后缀表达式
 {
     phead1* istack2=initstack1();//创建栈
     int i=0;
     while(str[i]!='\0')//遍历整个后缀表达式
    {
        char a[6]={0};
        int index=0;
        if(is_number(str[i])==1)
        {
            while(is_number(str[i])==1)
            {
                a[index]=str[i];
                index++;
                i++;
            }
            //成功读取数字
            seqstack_push1(istack2,atoi(a));//将该整数入栈
        }
        else if(is_operator(str[i])==1)
        {
            int right=seqstack_pop1(istack2);
            int left=seqstack_pop1(istack2);
            int ret=express(left,right,str[i]);
            if(ret==999)//被除数为0了
            {
                printf("ILLEGAL");
                return 999;
            }
            seqstack_push1(istack2,ret);//运算结果入栈
        }
        else if(str[i]==' ')
        {

        }
        else
        {
            printf("error\n");
            break;
        }
        i++;
    }
    if(str[i]=='\0'&&getsize(istack2))
    {
        return seqstack_top1(istack2);
    }
    return 0;
 }
int main()
{
    char str[1024]={0};//将数组每个元素赋值为'\0'
    printf("请输入四则运算表达式:\n");
    scanf("%s",str);
    int number=transform(str);
    if(number==-1)
    {
        printf("表达式转换错误:\n");
    }
    else if(number==1)
    {
        printf("转化后的表达式: %s\n",buffer);
    }
    else
    {
        return 0;
    }
    //成功换成后缀表达式


    //下方计算后缀表达式
    int num=calculate(buffer);
    if(num==999)
    {
        return 0;
    }
    printf("%d\n",num);
}

到这里我们终于完成了题目的要求，让我们随便写个中缀表达式运行一下，效果就是下面这样啦。

请输入四则运算表达式:
1+3*(2+5)
转化后的表达式: 1 3 2 5 +*+
22

大一学生数据结构学习中，如果有什么不对的地方或者更好的见解欢迎大家提出来，有什么疑问也欢迎私信，感谢阅读；   

                                                                                                                     ——Grande joie文章来源地址https://www.toymoban.com/news/detail-483809.html

到了这里，关于C语言数据结构篇——用栈实现四则运算的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！