• 【献给过去的自己】栈实现计算器（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;

    代码示例

    我的代码示例如下：

    1. #include
    2. #include
    3. #include
    4. #include
    5. #include
    6.  
    7. #define STACK_LEN 1024
    8.  
    9. /** 中缀表达式栈*/
    10. static int32_t g_infix_expression[1024] = {0};
    11.  
    12. /** 前缀表达式栈*/
    13. static int32_t g_prefix_expression[1024] = {0};
    14.  
    15. /** 后缀表达式栈*/
    16. static int32_t g_suffix_expression[1024] = {0};
    17.  
    18. /**
    19.  * @brief 将输入的字符串表达式转换为中缀表达式
    20.  *
    21.  * @param [in] expression 字符串表达式
    22.  * @return int 0 成功 non-0 失败
    23.  * */
    24. int expression2infix(const char* expression)
    25. {
    26.     if(expression == NULL)
    27.     {
    28.         printf("input error\n");
    29.         return -1;
    30.     }
    31.     
    32.     int dataTmp = 0; //表达式中的操作数
    33.     
    34.     bool dataFlag = false; // 操作数标识,表示当前是否有数据需要入栈
    35.  
    36.     const char* ptr = expression;
    37.     int32_t* infix_index = g_infix_expression;
    38.     
    39.     printf("expression = %s\n",expression);
    40.  
    41.     while(*ptr != '\0')
    42.     {
    43.         /** 字符为数字*/
    44.         if('0' <= *ptr  && *ptr <= '9')
    45.         {
    46.             dataTmp = dataTmp*10 +(*ptr - '0');
    47.             dataFlag = true;
    48.         }
    49.         /**字符为操作符或括号*/
    50.         else if(*ptr == '+' || *ptr == '-' || *ptr == '*' || *ptr == '/' 
    51.             || *ptr == '(' || *ptr == ')')
    52.         {
    53.             if(dataFlag == true)
    54.             {
    55.                 *(infix_index++) = dataTmp;
    56.                 dataFlag = false;
    57.                 dataTmp = 0;
    58.             }
    59.             *(infix_index++) = *ptr;
    60.         }
    61.         else
    62.         {
    63.             printf("wrong exptrssion\n");
    64.             return -1;
    65.         }
    66.  
    67.         ptr++;
    68.     }
    69.  
    70.     /**将最后一个操作数，入栈*/
    71.     if(dataFlag == true)
    72.     {
    73.         *(infix_index++) = dataTmp;
    74.         dataFlag = false;
    75.         dataTmp = 0;
    76.     }
    77.     return 0;
    78. }
    79.  
    80. /**
    81.  * @brief 将中缀表达式转换为前缀表达式
    82.  *
    83.  * @return int 0 成功 non-0 失败
    84.  * */
    85. int infix2prefixExpression()
    86. {
    87.     /**初始化运算符栈和中间结果栈*/
    88.     int32_t stack_s1[STACK_LEN] = {0};
    89.     int32_t stack_s1_top = 0;
    90.  
    91.     int32_t stack_s2[STACK_LEN] = {0};
    92.     int32_t stack_s2_top = 0; 
    93.  
    94.     int32_t * index = g_infix_expression;
    95.  
    96.     /**获取中缀表达式最右侧操作数*/
    97.  
    98.     while(*(index+1) != 0)
    99.     {
    100.         index++;
    101.     }
    102.  
    103.     while(index != g_infix_expression)
    104.     {
    105.         /** 操作符*/
    106.         if(*index == '+' || *index == '-' || *index == '*' || *index == '/')
    107.         {
    108.             while(true)
    109.             {
    110.                 /**S1为空，或栈顶运算符为右括号)，则将此运算符入栈*/
    111.                 if(stack_s1_top == 0 || stack_s1[stack_s1_top-1] == ')' || stack_s1[stack_s1_top-1] == '-'
    112.                     || stack_s1[stack_s1_top-1] == '+')
    113.                 {
    114.                     stack_s1[stack_s1_top++] = *index;
    115.                     break;
    116.                 }
    117.  
    118.                 stack_s2[stack_s2_top++] = stack_s1[stack_s1_top-1];
    119.                 stack_s1[stack_s1_top-1] = 0;
    120.                 stack_s1_top = stack_s1_top -1;
    121.             }
    122.         }
    123.         /**左括号
    124.          * 则依次弹出S1栈顶的运算符，并压入S2,直到遇到右括号为止
    125.         */
    126.         else if(*index == '(')
    127.         {
    128.             while(true)
    129.             {
    130.                 /**异常*/
    131.                 if(stack_s1_top == 0)
    132.                 {
    133.                     printf("infix experssion worong\n");
    134.                     return -1;
    135.                 }
    136.  
    137.                 /**遇到右括号,丢弃括号*/
    138.                 if(stack_s1[stack_s1_top-1] == ')')
    139.                 {
    140.                     stack_s1[stack_s1_top-1] = 0;
    141.                     stack_s1_top = stack_s1_top -1;
    142.                     break;
    143.                 }
    144.                 /**其它符号需要入栈S2*/
    145.                 else
    146.                 {
    147.                     stack_s2[stack_s2_top++] = stack_s1[stack_s1_top-1];
    148.                     stack_s1[stack_s1_top-1] = 0;
    149.                     stack_s1_top--;
    150.                 }
    151.  
    152.             }
    153.  
    154.         }
    155.         /**右括号
    156.          * 直接入运算符栈s1
    157.         */
    158.         else if(*index == ')')
    159.         {
    160.             stack_s1[stack_s1_top++] = *index;
    161.         }
    162.         /** 操作数
    163.          * 直接加入栈s2*/
    164.         else
    165.         {
    166.             stack_s2[stack_s2_top++] = *index;
    167.         }
    168.         index--;
    169. #if 0
    170.         printf("==============\n");
    171.         printf("stack_s1=");
    172.         for(int i = 0 ; i < stack_s1_top; i++)
    173.         {
    174.             (stack_s1[i] > 9) ? (printf("%c ",stack_s1[i])):(printf("%d ",stack_s1[i]));
    175.         }
    176.         printf("\n");
    177.  
    178.         printf("stack_s2=");
    179.         for(int i = 0 ; i < stack_s2_top; i++)
    180.         {
    181.             (stack_s2[i] > 9) ? (printf("%c ",stack_s2[i])):(printf("%d ",stack_s2[i]));
    182.         }
    183.         printf("\n");
    184. #endif  
    185.     }
    186.  
    187.     /**将最左侧操作数压入s2*/
    188.     stack_s2[stack_s2_top++] = *index;
    189.     
    190.     /**将s1中的符号压入s2*/
    191.     for(int i = stack_s1_top - 1; i >= 0; i-- )
    192.     {
    193.         stack_s2[stack_s2_top++] = stack_s1[i];
    194.         stack_s1[i] = 0;    
    195.     }
    196.  
    197.     /**将s2中的数据弹出，放入前缀表达式栈中*/
    198.     for(int i = 0 ; stack_s2_top > 0; i++,stack_s2_top--)
    199.     {
    200.         g_prefix_expression[i] = stack_s2[stack_s2_top-1];
    201.     }
    202.  
    203.     return 0;
    204. }
    205.  
    206.  
    207.  
    208. int main(int argc,char* argv[])
    209. {
    210.     if(argc != 2)
    211.     {
    212.         printf("please input experssion\n");
    213.         return -1;
    214.     }
    215.  
    216.     int32_t iRet = 0;
    217.  
    218.     iRet = expression2infix(argv[1]);
    219.     if(iRet == 0)
    220.     {
    221.         for(int i = 0 ; i < STACK_LEN && g_infix_expression[i] != 0; i++)
    222.         {
    223.             if(g_infix_expression[i] == '+' || g_infix_expression[i] == '-' || g_infix_expression[i] == '*' || g_infix_expression[i] == '/')
    224.             {
    225.                 printf("%c ",g_infix_expression[i]);
    226.             }
    227.             else
    228.             {
    229.                 printf("%d ",g_infix_expression[i]);
    230.             }
    231.         }
    232.         printf("\n");
    233.     }
    234.  
    235.     iRet = infix2prefixExpression();
    236.     if(iRet == 0)
    237.     {
    238.         for(int i = 0 ; i < STACK_LEN && g_prefix_expression[i] != 0; i++)
    239.         {
    240.             if(g_infix_expression[i] == '+' || g_infix_expression[i] == '-' || g_infix_expression[i] == '*' || g_infix_expression[i] == '/')
    241.             {
    242.                 printf("%c ",g_infix_expression[i]);
    243.             }
    244.             else
    245.             {
    246.                 printf("%d ",g_infix_expression[i]);
    247.             }
    248.         }
    249.         printf("\n");
    250.     }
    251.  
    252.     prefixExpressionCaculate();
    253.     return 0;
    254. }

    前缀表达式计算

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

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

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

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

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

    分析思路

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

            得出结果为16。

    代码示例

    新增prefixExpressionCaculate接口。代码如下：

    1. /**
    2.  * @brief 将前缀表达式进行计算
    3.  *
    4.  * @return int 0 成功 non-0 失败
    5.  * */
    6. int prefixExpressionCaculate()
    7. {
    8.     /**结果栈*/
    9.     int32_t stack[1024] = {0};
    10.     int32_t stack_len = 0;
    11.  
    12.     /**临时结果*/
    13.     int32_t tmpResult = 0;
    14.     int32_t data1 = 0;
    15.     int32_t data2 = 0;
    16.  
    17.     /**获取后缀表达式的最右侧操作数*/
    18.     int32_t* index = g_prefix_expression;
    19.     while(*(index+1) != 0)
    20.     {
    21.         index++;
    22.     }
    23.  
    24.     while(index >= g_prefix_expression)
    25.     {
    26.         /**弹出栈顶的两个数，并用运算符对这两个数做相应的计算，并将结果入栈*/
    27.         if(*index == '+' || *index == '-' || *index == '*' || *index == '/')
    28.         {
    29.             data1 = stack[stack_len-1];
    30.             data2 = stack[stack_len-2];
    31.             if(*index == '+')
    32.             {
    33.                 tmpResult = data1 + data2;
    34.             }
    35.             else if(*index == '-')
    36.             {
    37.                 tmpResult = data1 - data2;
    38.             }
    39.             else if(*index == '*')
    40.             {
    41.                 tmpResult = data1 * data2;
    42.             }
    43.             else if(*index == '/')
    44.             {
    45.                 tmpResult = data1 / data2;
    46.             }
    47.             else
    48.             {
    49.                 printf("worng prefixExperssion\n");
    50.                 return -1;
    51.             }
    52.  
    53.             stack[stack_len-1] = 0;
    54.             stack[stack_len-2] = tmpResult;
    55.             stack_len --;
    56.         }
    57.         /**遇到数字，压栈*/
    58.         else
    59.         {
    60.             stack[stack_len] = *index;
    61.             stack_len ++;
    62.         }
    63.         index --;
    64.  
    65.     }
    66.     printf("result = %d\n",stack[0]);
    67.     return 0;
    68. }

    演示

    后缀表达式

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

    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博客

  • 相关阅读:
    基于springboot高校学生健康打卡系统毕业设计源码021009
    三、部署kafka
    机器学习_个人笔记_周志华(停更中......)
    2 JavaScript in HTML
    基于Java+SpringBoot+Vue前后端分离多媒体素材库设计和实现
    146.LRU缓存
    osqp的原理ADMM（交替方向乘子法）理解
    R语言ggplot2包绘制网络地图
    【R语言】概率密度图
    C++用锁实现线程安全的stack容器
  • 原文地址：https://blog.csdn.net/xieyihua1994/article/details/134448197