【献给过去的自己】栈实现计算器（C语言）

背景

        记得在刚学C语言时，写了一篇栈实现计算器-CSDN博客文章。偶然间看到了文章的阅读量以及评论，居然有1.7w的展现和多条博友的点评，反馈。

        现在回过头来看，的确有许多不严谨的地方，毕竟当时分享文章时，还未毕业。理论和思维还不够严谨。但是我还依稀记得，班级上当时写出这个程序的同学，稀疏可数。所以在当时，还是有骄傲的资本的。本着对技术精益求精的态度，再通过本篇文章希望能够帮助刚接触C语言的朋友，也是给过去的自己一个满意的答复~

规则

        对于一个表达式，我们应该如何去识别它呢？当时，老师和我们说，按照如下规则进行解析即可。

        当时我们并不懂这个规则的由来，只知道按照这个规则去编程即可。再后来的工作中，因为考《软件设计师》资格证，了解到上述的规则，其实就是后缀表达式。同理还有前缀表达式，中缀表达式。

中缀表达式

        中缀表达式就是我们常用的一种算数表示方式。它的特点是操作符以中缀的方式处于操作数中间。但是中缀表达比较适合人类计算，对于计算机而言过于复杂。前缀表达式和后缀表达式对于计算机而言，更加友好。

        因此，我们想用程序实现计算器功能，有两种方式：

中缀表达式--> 前缀表达式-->计算

中缀表达式--> 后缀表达式-->计算

前缀表达式

        前缀表达式的运算符位于两个操作数之前，又称为前缀记法或波兰式。比如表达式（中缀）5+4，前缀表达式+ 5 4。因此使用前缀表达式进行计算，需要两个步骤。

  1. 如何将中缀表达式转换为前缀表达式

  2. 计算机如何识别前缀表达式并计算

中缀表达式转换前缀表达式

        根据文中描述，中缀表达式转换为前缀表达式的规则如下：

  1. 初始化两个栈：运算符栈S1和存储中间结果的栈S2;

  2. 从右至左扫描中缀表达式；

  3. 遇到操作数时，将其压入S2;

  4. 遇到运算符时，比较其与S1栈顶运算符的优先级；

    1. 如果S1为空，或栈顶运算符为右括号)，则将此运算符入栈；

    2. 否则，若优先级比栈顶运算符的较高或相等，也将运算符压入S1;

    3. 否则，将S1栈顶的运算符弹出并压入到S2,再次转到4.1与S1中新的栈顶运算符相比较；

  5. 遇到括号时：

    1. 如果是右括号)，则直接压入S1;

    2. 如果是左括号(，则依次弹出S1栈顶的运算符，并压入S2,直到遇到右括号为止，此时将这一对括号丢弃；

  6. 重复步骤2至5,直到表达式的最左边；

  7. 将S1中剩余的运算符依次弹出并压入S2;

  8. 依次弹出S2中的元素并输出，结果即为中缀表达式对应的前缀表达式。

        虽然规则很复杂，但是编码难度并不是很大，大家可以按照自己的技术能力尝试一下。

分析思路

        我们以表达式1+(2+3)*4-5举例。

        1. 因为输入表达式是字符串，后续我们需要从右往左扫描表达式，因此首先需要将字符串表达式中的运算符和操作数进行区分，可以用整型数组如下图：

        2. 根据2至5规则，进行分析。

       

        3. 弹出S2中的数据元素：- + 1 * + 2 3 4 5;

代码示例

我的代码示例如下：

#include<stdlib.h>
#include<stdio.h>
#include<string.h>
#include<stdint.h>
#include<stdbool.h>

#define STACK_LEN 1024

/** 中缀表达式栈*/
static int32_t g_infix_expression[1024] = {0};

/** 前缀表达式栈*/
static int32_t g_prefix_expression[1024] = {0};

/** 后缀表达式栈*/
static int32_t g_suffix_expression[1024] = {0};

/**
 * @brief 将输入的字符串表达式转换为中缀表达式
 *
 * @param [in] expression 字符串表达式
 * @return int 0 成功 non-0 失败
 * */
int expression2infix(const char* expression)
{
    if(expression == NULL)
    {
        printf("input error\n");
        return -1;
    }
    
    int dataTmp = 0; //表达式中的操作数
    
    bool dataFlag = false; // 操作数标识,表示当前是否有数据需要入栈

    const char* ptr = expression;
    int32_t* infix_index = g_infix_expression;
    
    printf("expression = %s\n",expression);

    while(*ptr != '\0')
    {
        /** 字符为数字*/
        if('0' <= *ptr  && *ptr <= '9')
        {
            dataTmp = dataTmp*10 +(*ptr - '0');
            dataFlag = true;
        }
        /**字符为操作符或括号*/
        else if(*ptr == '+' || *ptr == '-' || *ptr == '*' || *ptr == '/' 
            || *ptr == '(' || *ptr == ')')
        {
            if(dataFlag == true)
            {
                *(infix_index++) = dataTmp;
                dataFlag = false;
                dataTmp = 0;
            }
            *(infix_index++) = *ptr;
        }
        else
        {
            printf("wrong exptrssion\n");
            return -1;
        }

        ptr++;
    }

    /**将最后一个操作数，入栈*/
    if(dataFlag == true)
    {
        *(infix_index++) = dataTmp;
        dataFlag = false;
        dataTmp = 0;
    }
    return 0;
}

/**
 * @brief 将中缀表达式转换为前缀表达式
 *
 * @return int 0 成功 non-0 失败
 * */
int infix2prefixExpression()
{
    /**初始化运算符栈和中间结果栈*/
    int32_t stack_s1[STACK_LEN] = {0};
    int32_t stack_s1_top = 0;

    int32_t stack_s2[STACK_LEN] = {0};
    int32_t stack_s2_top = 0; 

    int32_t * index = g_infix_expression;

    /**获取中缀表达式最右侧操作数*/

    while(*(index+1) != 0)
    {
        index++;
    }

    while(index != g_infix_expression)
    {
        /** 操作符*/
        if(*index == '+' || *index == '-' || *index == '*' || *index == '/')
        {
            while(true)
            {
                /**S1为空，或栈顶运算符为右括号)，则将此运算符入栈*/
                if(stack_s1_top == 0 || stack_s1[stack_s1_top-1] == ')' || stack_s1[stack_s1_top-1] == '-'
                    || stack_s1[stack_s1_top-1] == '+')
                {
                    stack_s1[stack_s1_top++] = *index;
                    break;
                }

                stack_s2[stack_s2_top++] = stack_s1[stack_s1_top-1];
                stack_s1[stack_s1_top-1] = 0;
                stack_s1_top = stack_s1_top -1;
            }
        }
        /**左括号
         * 则依次弹出S1栈顶的运算符，并压入S2,直到遇到右括号为止
        */
        else if(*index == '(')
        {
            while(true)
            {
                /**异常*/
                if(stack_s1_top == 0)
                {
                    printf("infix experssion worong\n");
                    return -1;
                }

                /**遇到右括号,丢弃括号*/
                if(stack_s1[stack_s1_top-1] == ')')
                {
                    stack_s1[stack_s1_top-1] = 0;
                    stack_s1_top = stack_s1_top -1;
                    break;
                }
                /**其它符号需要入栈S2*/
                else
                {
                    stack_s2[stack_s2_top++] = stack_s1[stack_s1_top-1];
                    stack_s1[stack_s1_top-1] = 0;
                    stack_s1_top--;
                }

            }

        }
        /**右括号
         * 直接入运算符栈s1
        */
        else if(*index == ')')
        {
            stack_s1[stack_s1_top++] = *index;
        }
        /** 操作数
         * 直接加入栈s2*/
        else
        {
            stack_s2[stack_s2_top++] = *index;
        }
        index--;
#if 0
        printf("==============\n");
        printf("stack_s1=");
        for(int i = 0 ; i < stack_s1_top; i++)
        {
            (stack_s1[i] > 9) ? (printf("%c ",stack_s1[i])):(printf("%d ",stack_s1[i]));
        }
        printf("\n");

        printf("stack_s2=");
        for(int i = 0 ; i < stack_s2_top; i++)
        {
            (stack_s2[i] > 9) ? (printf("%c ",stack_s2[i])):(printf("%d ",stack_s2[i]));
        }
        printf("\n");
#endif  
    }

    /**将最左侧操作数压入s2*/
    stack_s2[stack_s2_top++] = *index;
    
    /**将s1中的符号压入s2*/
    for(int i = stack_s1_top - 1; i >= 0; i-- )
    {
        stack_s2[stack_s2_top++] = stack_s1[i];
        stack_s1[i] = 0;    
    }

    /**将s2中的数据弹出，放入前缀表达式栈中*/
    for(int i = 0 ; stack_s2_top > 0; i++,stack_s2_top--)
    {
        g_prefix_expression[i] = stack_s2[stack_s2_top-1];
    }

    return 0;
}



int main(int argc,char* argv[])
{
    if(argc != 2)
    {
        printf("please input experssion\n");
        return -1;
    }

    int32_t iRet = 0;

    iRet = expression2infix(argv[1]);
    if(iRet == 0)
    {
        for(int i = 0 ; i < STACK_LEN && g_infix_expression[i] != 0; i++)
        {
            if(g_infix_expression[i] == '+' || g_infix_expression[i] == '-' || g_infix_expression[i] == '*' || g_infix_expression[i] == '/')
            {
                printf("%c ",g_infix_expression[i]);
            }
            else
            {
                printf("%d ",g_infix_expression[i]);
            }
        }
        printf("\n");
    }

    iRet = infix2prefixExpression();
    if(iRet == 0)
    {
        for(int i = 0 ; i < STACK_LEN && g_prefix_expression[i] != 0; i++)
        {
            if(g_infix_expression[i] == '+' || g_infix_expression[i] == '-' || g_infix_expression[i] == '*' || g_infix_expression[i] == '/')
            {
                printf("%c ",g_infix_expression[i]);
            }
            else
            {
                printf("%d ",g_infix_expression[i]);
            }
        }
        printf("\n");
    }

    prefixExpressionCaculate();
    return 0;
}

前缀表达式计算

前缀表达式的计算规则如下：

  1. 从右至左扫描表达式；

  2. 遇到数字，压入栈中；

  3. 遇到运算符，弹出栈顶的两个数，并用运算符对这两个数做相应的计算，并将结果入栈；

  4. 重复上述2,3步骤，直到表达式最左端，最后的值为表达式的结果。

分析思路

        以上述后缀表达式举例:- + 1 * + 2 3 4 5。

        得出结果为16。

代码示例

新增prefixExpressionCaculate接口。代码如下：

/**
 * @brief 将前缀表达式进行计算
 *
 * @return int 0 成功 non-0 失败
 * */
int prefixExpressionCaculate()
{
    /**结果栈*/
    int32_t stack[1024] = {0};
    int32_t stack_len = 0;

    /**临时结果*/
    int32_t tmpResult = 0;
    int32_t data1 = 0;
    int32_t data2 = 0;

    /**获取后缀表达式的最右侧操作数*/
    int32_t* index = g_prefix_expression;
    while(*(index+1) != 0)
    {
        index++;
    }

    while(index >= g_prefix_expression)
    {
        /**弹出栈顶的两个数，并用运算符对这两个数做相应的计算，并将结果入栈*/
        if(*index == '+' || *index == '-' || *index == '*' || *index == '/')
        {
            data1 = stack[stack_len-1];
            data2 = stack[stack_len-2];
            if(*index == '+')
            {
                tmpResult = data1 + data2;
            }
            else if(*index == '-')
            {
                tmpResult = data1 - data2;
            }
            else if(*index == '*')
            {
                tmpResult = data1 * data2;
            }
            else if(*index == '/')
            {
                tmpResult = data1 / data2;
            }
            else
            {
                printf("worng prefixExperssion\n");
                return -1;
            }

            stack[stack_len-1] = 0;
            stack[stack_len-2] = tmpResult;
            stack_len --;
        }
        /**遇到数字，压栈*/
        else
        {
            stack[stack_len] = *index;
            stack_len ++;
        }
        index --;

    }
    printf("result = %d\n",stack[0]);
    return 0;
}

演示

后缀表达式

        后缀表达式与前缀表达式类似，只是运算符位于两个相应操作数之后，后缀表达式也称为后缀记法或逆波兰式。同样，我们需要解决两个问题。

  1. 如何将中缀表达式转换为后缀表达式

  2. 后缀表达式的计算规则

中缀表达式转后缀表达式

根据文中描述，中缀表达式转换为后缀表达式的规则如下：

  1. 初始化两个栈：运算符栈S1和存储中间结果的栈S2;

  2. 从左至右扫描中缀表达式；

  3. 遇到操作数时，将其压入S2;

  4. 遇到运算符时，比较其与S1栈顶运算符的优先级；

    1. 如果S1为空，或栈顶运算符为左括号(，则将此运算符入栈；

    2. 否则，若优先级比栈顶运算符的高，也将运算符压入S1;(注意是必须为高，相同或低于都不行)

    3. 否则，将S1栈顶的运算符弹出并压入到S2,再次转到4.2与S1中新的栈顶运算符相比较；

  5. 遇到括号时：

    1. 如果是左括号(，则直接压入S1;

    2. 如果是右括号)，则依次弹出S1栈顶的运算符，并压入S2,直到遇到左括号为止，此时将这一对括号丢弃；

  6. 重复步骤2至5,直到表达式的最右边；

  7. 将S1中剩余的运算符依次弹出并压入S2;

  8. 依次弹出S2中的元素并输出，结果即为中缀表达式对应的后缀表达式。

后缀表达式计算规则

后缀表达式的计算规则如下：

  1. 从左至右扫描表达式；

  2. 遇到数字，压入栈中；

  3. 遇到运算符，弹出栈顶的两个数，并用运算符对这两个数做相应的计算，并将结果入栈；

  4. 重复上述2,3步骤，直到表达式最右端，最后的值为表达式的结果。

        后缀表达式的代码示例可以参考前缀表达式的分析思路和代码，大家可以尝试编写。

总结

        时间流逝，在竞争激烈的社会背景下，我们的身处IT行业，不断逼迫自己去学习，去成长。但是总会觉得自己做的还不够。为什么总是赶不上别人的脚步，陷入怀疑自我的处境。

        朋友们，偶尔回头看看来时路上的自己，你会发现，你一直在成长，你的努力一直是正向反馈着你，不要轻视自己的努力。感谢csdn给予记录成长的平台，也感谢一直努力的自己。共勉~

参考文档

前缀表达式、中缀表达式和后缀表达式 - 乘月归 - 博客园

数据结构和算法（六）：前缀、中缀、后缀表达式

栈实现计算器-CSDN博客

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/153480.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

SAP PI/PO中使用UDF解决按字节拆分字符串的需求

SAP PI/PO中使用UDF解决按字节拆分字符串的需求

需求背景&#xff1a; SAP需要将采购订单信息通过PI发送到SFTP服务器上&#xff0c;生成文件&#xff0c;一般对日项目上文件内容通常都是按照指定的字节数拆分的&#xff0c;而不是字符数&#xff0c;类似下面的格式。 问题点&#xff1a; 如果是使用FTP适配器&#xff0c;则…
阅读更多...
教你简单几步，轻松下载微信视频号里的视频

教你简单几步，轻松下载微信视频号里的视频

在如今社交媒体上&#xff0c;视频内容越来越受到人们的喜爱。微信视频号作为一个新兴平台&#xff0c;以其丰富的视频内容吸引着越来越多的用户。然而&#xff0c;许多人在观看完喜欢的视频后&#xff0c;都希望能够将其下载到本地进行保存或分享。那么&#xff0c;微信视频号…
阅读更多...
联想领像M102W激光打印机报错E0问题的描述

联想领像M102W激光打印机报错E0问题的描述

速印机（理想、荣大等）、复印机（夏普、东芝、理光、佳能、震旦等全系列）、打印机、扫描仪、传真机、多媒体教学一体机、交互式电子白板、报警器材、监控、竞业达监考设备及其它监考设备、听力考试设备、特种安防设备维护及维修。 联想领像M102W打印机是理光SP系列的衍生机器…
阅读更多...
gamingtcui.dll 丢失的全面解决方案指南，快速修复gamingtcui.dll文件

gamingtcui.dll 丢失的全面解决方案指南，快速修复gamingtcui.dll文件

在使用计算机进行工作或娱乐时&#xff0c;我们可能会遇到一些需要技术解决的问题。其中&#xff0c;"gamingtcui.dll找不到"是一种比较常见的DLL文件相关的问题&#xff0c;许多用户在面对它时会感到疑惑&#xff0c;首先&#xff0c;我们需要理解问题的本质 —— 什…
阅读更多...
《洛谷深入浅出进阶篇》P1995 程序自动分析——并查集，离散化

《洛谷深入浅出进阶篇》P1995 程序自动分析——并查集，离散化

上链接&#xff1a;P1955 [NOI2015] 程序自动分析 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)https://www.luogu.com.cn/problem/P1955 上题干&#xff1a; 首先给你一个整数t&#xff0c;代表t次操作。 每一次操作包含以下内容&#xff1a; 1.给你一个整数n&#xff0c;让…
阅读更多...
挖掘PostgreSQL事务的“中间态”----更加严谨的数据一致性？

挖掘PostgreSQL事务的“中间态”----更加严谨的数据一致性？

1.问题 今天在上班途中&#xff0c;中心的妹纸突然找我&#xff0c;非常温柔的找我帮忙看个数据库的报错。当然以我的性格&#xff0c;妹子找我的事情对我来说优先级肯定是最高的&#xff0c;所以立马放下手中的“小事”&#xff0c;转身向妹子走去。具体是一个什么样的问题呢…
阅读更多...
这才是 SpringBoot 统一登录鉴权、异常处理、数据格式的正确打开姿势

这才是 SpringBoot 统一登录鉴权、异常处理、数据格式的正确打开姿势

本篇将要学习 Spring Boot 统一功能处理模块&#xff0c;这也是 AOP 的实战环节 用户登录权限的校验实现接口 HandlerInterceptor WebMvcConfigurer 异常处理使用注解 RestControllerAdvice ExceptionHandler 数据格式返回使用注解 ControllerAdvice 并且实现接口 Response…
阅读更多...
阿尔法狗的算法解析-增强学习和蒙特卡洛树搜索算法

阿尔法狗的算法解析-增强学习和蒙特卡洛树搜索算法

阿尔法狗（AlphaGo）是谷歌旗下DeepMind开发的一个著名的增强学习算法，它在围棋领域取得了显著的成就。本文主要探讨其中两个重要的算法：增强学习算法和蒙特卡洛树搜索算法。 AlphaGo涉及的算法 AlphaGo是DeepMind团队开发的一个由多种算法和技术组合而成的系统，其包括以下…
阅读更多...
【Linux网络】典型NAS存储方式：NFS网络共享存储服务

【Linux网络】典型NAS存储方式：NFS网络共享存储服务

一、关于存储的分类 二、NFS的介绍 nfs的相关介绍&#xff1a; 1、原理 2、nfs的特点 3、nfs软件学习 4、共享配置文件的书写格式 关于权限&#xff0c;学习&#xff1a; 5、关于命令的学习&#xff1a; 三、实验操作 1、nfs默认共享权限&#xff08;服务端设置&#…
阅读更多...
大数据-之LibrA数据库系统告警处理（ALM-12049 网络读吞吐率超过阈值）

大数据-之LibrA数据库系统告警处理（ALM-12049 网络读吞吐率超过阈值）

告警解释 系统每30秒周期性检测网络读吞吐率&#xff0c;并把实际吞吐率和阈值&#xff08;系统默认阈值80%&#xff09;进行比较&#xff0c;当检测到网络读吞吐率连续多次&#xff08;默认值为5&#xff09;超过阈值时产生该告警。 用户可通过“系统设置 > 阈值配置 >…
阅读更多...
【数据结构】C语言实现栈

【数据结构】C语言实现栈

&#x1f388;个人主页&#xff1a;库库的里昂 &#x1f390;C/C领域新星创作者 &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏✨收录专栏&#xff1a;数据结构与算法&#x1f91d;希望作者的文章能对你有所帮助&#xff0c;有不足的地方请在评论区留言指正&#xff0c;大家…
阅读更多...
软件开发和软件测试，到底学哪个好呢？

软件开发和软件测试，到底学哪个好呢？

写在前面&#xff1a;买车没有最好&#xff0c;只有最适合。 类似这类“很难选择”的问题&#xff0c;在知乎上其实有很多。 比如&#xff1a;“该去年薪10w的国家电网&#xff0c;还是去年薪40w的互联网大厂”&#xff1b; 比如&#xff1a;“城里有房&#xff0c;剩下的100…
阅读更多...
Sentinel规则

Sentinel规则

一、服务熔断测试 例子: application.properties配置文件 server.port8083spring.application.nameorder#spring.cloud.nacos.discovery.server-addrhttp://192.168.44.64:80spring.cloud.nacos.discovery.server-addrlocalhost:8848spring.cloud.sentinel.transport.port999…
阅读更多...
C++之map和set模拟实现

C++之map和set模拟实现

前言 在map和set的使用文章中提到了CSTL中的map和set的底层其实就是用的红黑树来实现的,所以可以用红黑树来简单模拟实现一下STL中的map和set. STL源码中map和set的实现 map: 我们看到它的底层这个成员变量其实就是一棵红黑树, 之前说过map其实就对应搜索树的KV模型&#x…
阅读更多...
面向企业的人脸属性检测技术方案

面向企业的人脸属性检测技术方案

人脸识别技术已经成为企业提升服务质量、优化用户体验的重要工具。美摄科技&#xff0c;作为领先的人工智能技术提供商&#xff0c;我们致力于为企业提供最先进、最全面的人脸属性检测技术解决方案。 我们的AI人脸检测与属性分析技术&#xff0c;能够快速准确地检测人脸并返回…
阅读更多...
安全狗云安全体系为高校提升立体化纵深防御能力

安全狗云安全体系为高校提升立体化纵深防御能力

客户情况 某高校有服务器500台&#xff0c;对外站点200个&#xff0c;核心交换流量20G。 客户痛点 校园网系统分类较多&#xff0c;并且每类网站中安全级重要程度又各不相同&#xff0c;同时有多个网络出口(如&#xff1a;教育网、电信网、移动网等)&#xff0c;二级学院存在…
阅读更多...
物联网网关在工业行业的应用案例

物联网网关在工业行业的应用案例

物联网网关在工业行业的应用案例 随着物联网技术的不断发展&#xff0c;物联网网关在工业行业的应用越来越广泛。本文将介绍一个物联网网关在工业行业的应用案例&#xff0c;以期为相关领域的研究和实践提供借鉴和启示。 一、案例背景 某大型制造企业是一家全球知名的汽车制…
阅读更多...
vscode中git拉取、提交代码、解决冲突，以及合并代码的操作

vscode中git拉取、提交代码、解决冲突，以及合并代码的操作

vscode中git拉取、提交代码、解决冲突&#xff0c;以及合并代码的操作 场景&#xff1a;本地有修改代码&#xff0c;远程仓库没有更新&#xff0c;这时本地想要提交代码。 步骤&#xff1a;本地修改了testA文件内容->本地先暂存提交->拉取->推送&#xff1b; 本地修改…
阅读更多...
2023.11.14 hivesql的容器,数组与映射

2023.11.14 hivesql的容器,数组与映射

目录 https://blog.csdn.net/m0_49956154/article/details/134365327?spm1001.2014.3001.5501https://blog.csdn.net/m0_49956154/article/details/134365327?spm1001.2014.3001.5501 8.hive的复杂类型 9.array类型: 又叫数组类型,存储同类型的单数据的集合 10.struct类型…
阅读更多...
SpringNative遇到的问题

SpringNative遇到的问题

问题1 org.apache.catalina.LifecycleException: An invalid Lifecycle transition was attempted ([before_stop]) for component 用不了反射&#xff0c;所以需要这个文件去 package org.wxy.example.sqlite.config;import java.lang.reflect.Constructor; import java.lan…
阅读更多...
最新文章

Copyright @ 2022~2023