[关闭]
@coder-pig 2019-05-31T14:27:41.000000Z 字数 4954 阅读 1759

小猪的数据结构辅助教程——3.3 栈的应用实例：逆波兰式(RPN)

数据结构

1.逆波兰式的概述

1）逆波兰式的引入：

在开始讲解逆波兰式之前，我们先来了解下我们平时数学里是如何写表达式的，比如：
8 * (1 + 2) / (2 + 4)，好的，瞄一眼，我们就能得出结果是4，我们是根据运算符
的优先级来计算的，括号 > 乘除 > 加减，是吧！我们很简单就能得出结果，但是，假如
这上面的这段表达式丢给计算机呢？计算机需要进行多次if判断才能够决定先算哪一部分！
有没有什么好的解决方法呢？答案肯定是有的：比如本节要讲的逆波兰式~

2）逆波兰式的介绍：

逆波兰式，你也可以叫做：逆波兰表达式，可以理解成后缀表达式，我们平时数学写的
那种表达式叫中缀表达式，中缀后缀，其实就是运算符在表达式中的位置，比如上面的：
中缀表达式：8 * (1 + 2) / (2 + 4)
后缀表达式(逆波兰式)：8 1 2 + 2 4 + / *
可能你对上面的后缀表达式不是很了解，没事，下面来看下如何利用栈，将中缀表示式
转换为后缀逆波兰式！

3）如何将中缀表达式转换为逆波兰式

我们以上面的：8 * (1 + 2) / (2 + 4)为例，我们用两个栈，一个用来存放中缀表达式的
每个元素，一个用来来存放转换过程中的操作符号！每次从栈中取出一个元素，做如下判断：
①数字，直接打印
②运算符(+-*/)，和操作符栈中的栈顶元素进行运算优先级的比较：
如果大于等于栈顶，将这个运算符入栈
否则弹出栈顶的运算符，打印，然后将新运算符压入栈中
③左括号，直接入栈
④右括号，弹出栈中的元素，直到遇到左括号！

好的，规则有了，下面我们来演示下这个过程：

  • 8是数字，打印，此时打印的内容：8
  • 是运算符，压入栈中，此时栈{};
  • (，直接压入栈中，此时栈{*,(};
  • 1是数字，打印，此时打印的内容：8 1
  • +是运算符，压入栈中，此时栈{*,),+}
  • 2是数字，打印，此时打印的内容：8 1 2
  • )，弹出栈中的元素，直到遇到(，此时栈{*}，此时打印的内容：8 1 2 +
  • /是运算符，优先级和一样，压入栈中，此时栈{,/}
  • (，直接压入栈中，此时栈{*,/,(}
  • 2是数字，打印，此时打印的内容：8 1 2 + 2
  • +是运算符，压入栈中，此时栈{*,/,(,+}
  • 4是数字，打印，此时打印的内容：8 1 2 + 2 4
  • )，弹出栈中的元素，直到遇到(，此时栈{*,/}，此时打印的内容：8 1 2 + 2 4 +
  • 将栈中剩余的元素弹出，此时打印的内容：8 1 2 + 2 4 + / *

好的，演示到这里，相信你对逆波兰式应该基本了解了，下面该准备动手写代码了，本节
我们来写两个程序，中缀表达式转成逆波兰式和逆波兰式的结果计算！

2.中缀表达式转成逆波兰式的代码实现：

运行截图：

代码实现：

  1. #include <stdio.h>
  3. #define STACK_INIT_SIZE 10 //存储空间的初始分配量
  4. #define STACK_INCREMENT 2 //分配增量 
  6. #define OK 1
  7. #define ERROR 0
  8. #define TRUE 1
  9. #define FALSE 0
  11. typedef char SElemType;
  12. typedef int Status;
  13. typedef struct SqStack
  14. {
  15.     SElemType *base;  //栈底指针变量 
  16.     SElemType *top;  //栈顶指针变量 
  17.     int stacksize;  //当前可试用的最大容量 
  18. }SqStack;
  20. //初始化栈
  21. void InitStack(SqStack *S)
  22. {
  23.     S->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
  24.     if( !S->base)exit(0);
  25.     S->top = S->base;
  26.     S->stacksize = STACK_INIT_SIZE;
  27. } 
  29. //入栈
  30. void PushStack(SqStack *S, SElemType e)
  31. {
  32.     if(S->top - S->base >= S->stacksize )
  33.     {
  34.         S->base = (SElemType *)realloc(S->base, (S->stacksize + STACK_INCREMENT) * sizeof(SElemType));
  35.         if( !S->base )exit(0);
  36.         S->top = S->base + S->stacksize;
  37.         S->stacksize = S->stacksize + STACK_INCREMENT;
  38.     }
  39.     *(S->top) = e;
  40.     S->top++;
  41. }
  43. //出栈 
  44. void PopStack(SqStack *S, SElemType *e)
  45. {
  46.     if(S->top == S->base )return;
  47.     *e = *--(S->top);
  48. }
  50. //获取栈的当前长度
  51. int StackLength(SqStack S)
  52. {
  53.     return (S.top - S.base);
  54. } 
  56. int main()
  57. {
  58.     SqStack s;
  59.     char c,e;
  60.     InitStack(&s);
  61.     printf("请输入中缀表达式，以#作为结束标记：\n");
  62.     scanf("%c",&c);
  63.     printf("输出转换后的逆波兰式：\n");
  64.     while(c != '#')
  65.     {   
  66.         //这里需要考虑数字会是多位的情况
  67.         while(c >= '0' && c <= '9')
  68.         {
  69.             printf("%c", c);
  70.             scanf("%c", &c);
  71.             if( c<'0' || c>'9' )
  72.             {
  73.                 printf(" ");
  74.             }
  75.         } 
  76.         //假如是右括号，弹出栈中的字符，直到遇到左括号 
  77.         if( ')' == c )
  78.         {
  79.             PopStack(&s, &e);
  80.             while( '(' != e )
  81.             {
  82.                 printf("%c ", e);
  83.                 PopStack(&s, &e);
  84.             }
  85.         }
  86.         //假如是加减号 ，如果栈里没元素，直接压栈，有要做下判断
  87.         else if( '+'==c || '-'==c )
  88.         {
  89.             if( !StackLength(s) )
  90.             {
  91.                 PushStack(&s, c);
  92.             }
  93.             else
  94.             {
  95.                 do
  96.                 {
  97.                     PopStack(&s, &e);
  98.                     if( '(' == e )
  99.                     {
  100.                         PushStack(&s, e);
  101.                     }
  102.                     else
  103.                     {
  104.                         printf("%c ", e);
  105.                     }
  106.                 }while( StackLength(s) && '('!=e );
  107.                 PushStack(&s, c);
  108.             }
  109.         } 
  110.         //假如是乘除或左括号，直接压栈 
  111.         else if( '*'==c || '/'==c || '('==c )
  112.         {
  113.             PushStack(&s, c);
  114.         }
  115.         //是#，则代表表达式输入完毕
  116.         else if( '#'== c )
  117.         {
  118.             break;
  119.         }
  120.         //如果是其他字符，打印字符不合法
  121.         else
  122.         {
  123.             printf("\n出错：输入错误！\n");
  124.             return -1;
  125.         } 
  126.         scanf("%c", &c);     
  127.     }
  129.     //遍历栈中的剩余运算符
  130.     while( StackLength(s))
  131.     {
  132.         PopStack(&s, &e);
  133.         printf("%c ", e);
  134.     } 
  135.     printf("\n\n");
  136.     return 0;
  137. }

代码直接看main部分的就可以了，写了很详细的注释，应该能看懂，逻辑
很简单，无非是判断，然后入栈出栈打印而已，另外，吐槽下，不习惯C写{}的风格..

3.逆波兰式的结果计算

这里用到两个个函数：

  • int isdigit(char c)：
    ctype.h库为我们提供的用于检查参数c是否为阿拉伯数字0到9的函数！
  • double atof(const char *nptr);
    stdlib.h库给我们提供的把字符串转换成浮点数的函数

运行截图：

代码实现：

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <ctype.h>
  5. #define STACK_INIT_SIZE 10 //存储空间的初始分配量
  6. #define STACK_INCREMENT 2 //分配增量 
  7. #define MAX_BUFFER_SIZE 10
  9. #define OK 1
  10. #define ERROR 0
  11. #define TRUE 1
  12. #define FALSE 0
  14. typedef double SElemType;
  15. typedef int Status;
  16. typedef struct SqStack
  17. {
  18.     SElemType *base;  //栈底指针变量 
  19.     SElemType *top;  //栈顶指针变量 
  20.     int stacksize;  //当前可试用的最大容量 
  21. }SqStack;
  23. //初始化栈
  24. void InitStack(SqStack *S)
  25. {
  26.     S->base = (SElemType *)malloc(STACK_INIT_SIZE * sizeof(SElemType));
  27.     if( !S->base)exit(0);
  28.     S->top = S->base;
  29.     S->stacksize = STACK_INIT_SIZE;
  30. } 
  32. //入栈
  33. void PushStack(SqStack *S, SElemType e)
  34. {
  35.     if(S->top - S->base >= S->stacksize )
  36.     {
  37.         S->base = (SElemType *)realloc(S->base, (S->stacksize + STACK_INCREMENT) * sizeof(SElemType));
  38.         if( !S->base )exit(0);
  39.         S->top = S->base + S->stacksize;
  40.         S->stacksize = S->stacksize + STACK_INCREMENT;
  41.     }
  42.     *(S->top) = e;
  43.     S->top++;
  44. }
  46. //出栈 
  47. void PopStack(SqStack *S, SElemType *e)
  48. {
  49.     if(S->top == S->base )return;
  50.     *e = *--(S->top);
  51. }
  53. //获取栈的当前长度
  54. int StackLength(SqStack S)
  55. {
  56.     return (S.top - S.base);
  57. } 
  59. //判断是否为空栈
  60. Status StackEmpty(SqStack S)
  61. {
  62.     return S.top == S.base?TRUE:FALSE;
  63. } 
  65. int main()
  66. {
  67.     char c;
  68.     double d,e;
  69.     int i = 0;
  70.     char buffer[MAX_BUFFER_SIZE];
  71.     SqStack s;
  72.     InitStack(&s);
  73.     printf("请输入所要计算表达式的逆波兰表达式，数字(包括小数)之间用空格分开，以#表示结束！\n");
  74.     scanf("%c",&c);
  75.     while(c!='#')
  76.     {
  77.         //判断字符是否为数字或小数点 
  78.         while(isdigit(c)||c=='.')
  79.         {
  80.             buffer[i++]=c;
  81.             buffer[i]='\0'; 
  82.              if(i>=10){
  83.                 printf("\n出错！超过最大缓冲区大小！\n");
  84.                 return -1;
  85.             }
  86.             scanf("%c",&c);
  87.             //判断是否为空格，是的话将缓冲区里的字符串转换为double类型的数据，压入栈中 
  88.             if(c == ' ')
  89.             {
  90.                 d = atof(buffer);
  91.                 PushStack(&s,d);
  92.                 i=0;
  93.                 break;
  94.             } 
  95.         }
  96.         //如果是运算符则，弹出栈中的两个元素，作为参数进行运算，将结果压入栈中 
  97.         //另外，要注意：除法除数不能为0 
  98.         switch(c)
  99.         {
  100.             case '+':
  101.                 PopStack(&s,&d);
  102.                 PopStack(&s,&e);
  103.                 PushStack(&s,d+e);
  104.                 break;
  105.             case '-':
  106.                 PopStack(&s,&d);
  107.                 PopStack(&s,&e);
  108.                 PushStack(&s,e-d);
  109.                 break;
  110.             case '*':
  111.                 PopStack(&s,&d);
  112.                 PopStack(&s,&e);
  113.                 PushStack(&s,d*e);
  114.                 break;
  115.             case '/':
  116.                 PopStack(&s,&d);
  117.                 PopStack(&s,&e);
  118.                 if(e!=0)PushStack(&s,e/d);
  119.                 else{
  120.                     printf("\n出错，除数不能为0！");
  121.                     return -1;
  122.                 }
  123.                 break;      
  124.         }
  125.         scanf("%c",&c);
  126.     }
  127.     PopStack(&s,&d);
  128.     printf("\n最终结果为：%f\n",d);
  129.     return 0;
  130. }

和上面一样，写了很详细的注释，代码应该都能看懂~
上述两个程序参考自——小甲鱼的《数据结构与算法教学》系列！

4.本节示例代码下载：

https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/Stack/Stack4.c
https://github.com/coder-pig/Data-structure-auxiliary-tutorial/blob/master/Stack/Stack5.c

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注