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

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

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

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


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

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