C语言利用栈实现对后缀表达式的求解

时间:2022-09-13 10:19:12

本文实例为大家分享了C语言实现对后缀表达式(逆波兰表达式)的求解代码,供大家参考,具体内容如下

逆波兰表达式:

逆波兰表达式又叫后缀表达式。它是由相应的语法树的后序遍历的结果得到的。
例:5 - 8*(6 + 7) + 9 / 4:

其中缀表达式为:5 - 8 * 6 + 7 + 9 / 4

其语法树如下:

C语言利用栈实现对后缀表达式的求解

因此根据语法树可以得出他后序遍历(后缀表达式)为:
5 8 6 7 + * - 9 4 / +

这样就实现了中缀表达式到后缀表达式的转换。
同样的也可以得出他的前序遍历(前缀表达式也称波兰表达式):
 + - 5 * 8 + 6 7 / 9 4

逆波兰表达式计算实现原理:
1.首先当遇到运算操作数时将其进行push操作;

2.当遇到操作符是将此时的栈pop两次,先取出的栈顶为右操作数;

3.执行此方法到整个数组遍历完。

C语言利用栈实现对后缀表达式的求解

实现算法如下:

  1. void CalFunction(SqStack *S,char str[])
  2. {/*实现浮点型数据后缀表达式的加减乘除*/
  3. Elemtype number,e,d;
  4. char arr[MAXBUFFER];
  5. int i=0,j=0;
  6.  
  7. InitStack(S);
  8.  
  9. while(str[i]!='\0')
  10. {
  11. while(isdigit(str[i])||str[i]=='.') //过滤数字
  12. {
  13. arr[j++]=str[i++];
  14. arr[j]='\0';
  15.  
  16. if( j >= MAXBUFFER )
  17. {
  18. printf("输入单个数据过大!\n");
  19. return ;
  20. }
  21. if(str[i]==' ')
  22. {
  23. number=atof(arr); //利用atof函数将数字字符串转化为double型数据
  24. PushStack(S,number); //将转换的数进行压栈
  25. j=0; //这里不要忘记将j重新初始化进行下个数据的转化
  26. break;
  27. }
  28. }
  29. /*如果遇到操作运算符则,弹出两个数据进行运算,然后将得出的结果重新入栈*/
  30. switch(str[i])
  31. {
  32. case '+':
  33. PopStack(S,&e);
  34. PopStack(S,&d);
  35. PushStack(S,d+e);
  36. break;
  37. case '-':
  38. PopStack(S,&e);
  39. PopStack(S,&d);
  40. PushStack(S,d-e);
  41. break;
  42. case '*':
  43. PopStack(S,&e);
  44. PopStack(S,&d);
  45. PushStack(S,d*e);
  46. break;
  47. case '/':
  48. PopStack(S,&e);
  49. PopStack(S,&d);
  50. if(e == 0)
  51. {
  52. printf("输入出错,分母为零!\n");
  53. return ;
  54. }
  55. PushStack(S,d/e);
  56. break;
  57. }
  58. i++; //继续遍历直到遍历字符串结束
  59. }
  60.  
  61. PopStack(S,&e);
  62. printf("计算结果为:%lf",e);
  63. }

完整代码如下:

  1. #include<stdio.h>
  2. #include<stdlib.h>
  3. #include<assert.h>
  4. #include<ctype.h>
  5.  
  6. #define INITSIZE 20
  7. #define INCREMENT 10
  8. #define MAXBUFFER 10
  9. #define LEN sizeof(Elemtype)
  10.  
  11. /*栈的动态分配顺序存储结构*/
  12. typedef double Elemtype;
  13. typedef struct{
  14. Elemtype *base;
  15. Elemtype *top;
  16. int StackSize;
  17. }SqStack;
  18.  
  19. void InitStack(SqStack *S)
  20. {
  21. S->base=(Elemtype*)malloc(LEN*INITSIZE);
  22. assert(S->base != NULL);
  23. S->top=S->base;
  24. S->StackSize=INITSIZE;
  25. }
  26.  
  27. void PushStack(SqStack *S,Elemtype e)
  28. {
  29. if(S->top - S->base >= S->StackSize)
  30. {
  31. S->base=(Elemtype*)realloc(S->base,(S->StackSize+INCREMENT)*LEN);
  32. assert(S->base !=NULL);
  33. S->top=S->base+S->StackSize;
  34. S->StackSize+=INCREMENT;
  35. }
  36. *S->top =e;
  37. S->top++;
  38. }
  39.  
  40. void PopStack(SqStack *S,Elemtype *e)
  41. {
  42. *e=*--S->top;
  43. }
  44.  
  45. void CalFunction(SqStack *S,char str[])
  46. {
  47. Elemtype number,e,d;
  48. char arr[MAXBUFFER];
  49. int i=0,j=0;
  50.  
  51. InitStack(S);
  52.  
  53. while(str[i]!='\0')
  54. {
  55. while(isdigit(str[i])||str[i]=='.') //过滤数字
  56. {
  57. arr[j++]=str[i++];
  58. arr[j]='\0';
  59.  
  60. if( j >= MAXBUFFER )
  61. {
  62. printf("输入单个数据过大!\n");
  63. return ;
  64. }
  65. if(str[i]==' ')
  66. {
  67. number=atof(arr); //利用atof函数将数字字符转化为double型数据
  68. PushStack(S,number); //将转换的数进行压栈
  69. j=0;
  70. break;
  71. }
  72. }
  73.  
  74. switch(str[i])
  75. {
  76. case '+':
  77. PopStack(S,&e);
  78. PopStack(S,&d);
  79. PushStack(S,d+e);
  80. break;
  81. case '-':
  82. PopStack(S,&e);
  83. PopStack(S,&d);
  84. PushStack(S,d-e);
  85. break;
  86. case '*':
  87. PopStack(S,&e);
  88. PopStack(S,&d);
  89. PushStack(S,d*e);
  90. break;
  91. case '/':
  92. PopStack(S,&e);
  93. PopStack(S,&d);
  94. if(e == 0)
  95. {
  96. printf("输入出错,分母为零!\n");
  97. return ;
  98. }
  99. PushStack(S,d/e);
  100. break;
  101. }
  102. i++;
  103. }
  104.  
  105. PopStack(S,&e);
  106. printf("计算结果为:%lf",e);
  107. }
  108.  
  109. int main()
  110. {
  111. char str[100];
  112. SqStack S;
  113. printf("请按逆波兰表达式输入数据,每个数据之间用空格隔开:");
  114. gets(str);
  115. CalFunction(&S,str);
  116. return 0;
  117. }
  118.  
  119. // 检测用例 5 - (6 + 7) * 8 + 9 / 4
  120.  
  121. // 输入:5 8 6 7 + * - 9 4 / + #
  122.  
  123. // 输出: - 96.750000

运行效果截图如下:

C语言利用栈实现对后缀表达式的求解

以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持我们。

原文链接:https://blog.csdn.net/qq_42552533/article/details/86562791