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

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

逆波兰表达式：

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

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

其语法树如下：

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

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

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

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

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

实现算法如下：

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

运行效果截图如下：

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

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