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

STM32F4 CAN

作者名:Demo不是emo 

有始有终

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

cloud alibaba

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

虚拟环境

STM32 FMC

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

音乐网系统

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

andorid原生插件

npm

目录

MySQL架构

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

dump文件

1,中缀表达式转后缀表达式遵循的原则

Windows 7 无法共享

2,中缀表达式转后缀表达式的图文举例(超详细)

交换机

3,编程实现中缀表达式转后缀表达式 

最小二乘法

1,引入链栈

自动化

2,封装中缀转后缀需要的相关函数

敏捷流程

3,完整代码

面试经验

二,后缀表达式的计算 

资料

1,后缀表达式的计算原则 

Linux网络基础

2,后缀表达式计算的图文举例: 

PaaS

3,编程实现后缀表达式的计算 

金融

引入链栈(整型)

Jemeter

计算后缀表达式涉及的函数 

服务注册

三,用栈实现四则运算的完整代码(先把中缀表达式换成后缀表达式,再计算后缀表达式) 

分页


通信

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

1,中缀表达式转后缀表达式遵循的原则

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

●对于数字,直接输出

测试工程师

●对于符号

core dump

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

hex下载程序

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

网络传输

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

DOM

                        若新符号优先级高(默认左括号优先级最低),则直接入栈;

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

                右括号:不断将栈顶符号弹出并输出,直到栈顶符号与右括号匹配(即栈顶符号                              是左括号),再讲栈顶的左括号弹出即可(只需要弹出,不需要输出)

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

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

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,编程实现后缀表达式的计算 

引入链栈(整型)

因为计算过程中我们数据存在栈中,所以我们也要引入链栈,但是这里因为要计算压栈,以及把运算结果压栈等操作,这里链栈的数据节点的数据域为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;
}

计算后缀表达式涉及的函数 

 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

发表回复

您的电子邮箱地址不会被公开。 必填项已用 * 标注