C++利用栈实现中缀表达式转后缀表达式

本文实例为大家分享了C++实现中缀表达式转后缀表达式的具体代码，供大家参考，具体内容如下

题目：现有中缀表达式如：1+(2-3)*4+10/5

请用栈的特性编写一个程序，使得程序输出后缀表达式

分析如下：

STEP1：

1+(2-3)*4+10/5

首先遇到第一个输入是数字1，数字在后缀表达式中都是直接输出，接着是符号“+”，入栈：

STEP2：

1+(2-3)*4+10/5

第三个字符是“(”，依然是符号，入栈，接着是数字2，输出，然后是符号“-”，入栈：

STEP3：

1+(2-3)*4+10/5

接下来是数字3，输出，紧跟着是“)”，此时，我们需要去匹配栈里的“(”，然后再匹配前将栈顶数据依次出栈（这就好比括号里优先执行的道理）：

STEP4：

1+(2-3)*4+10/5

紧接着是符号“*”，直接入栈

STEP5：

1+(2-3)*4+10/5

遇到数字4，输出，之后是符号“+”，此时栈顶元素是符号“*”，按照先乘除后加减原理，此时栈顶的乘号优先级比即将入栈的加好要大，所以出栈。
栈中第二个元素是加号，按理来说大家平起平坐，但是按照先来后到的原则，栈里的加号呆得太久了，也要出栈透透气。（同理如果栈里还有其他操作符，也是出栈）

最后把刚刚的那个加号入栈，操作如下图：

STEP6：

1+(2-3)*4+10/5

紧接着数字10，输出，最后是符号“/”，进栈：

STEP7：

1+(2-3)*4+10/5

最后一个数字5，输出，所有的输入处理完毕，但是栈中仍然有数据，所以将栈中符号依次出栈。

总结规则：

从左到右遍历中缀表达式的每个数字和符号，若是数字则直接输出，若是符号，则判断其与栈顶符号的优先级，是右括号或者优先级低于栈顶符号，则栈顶元素依次出栈并输出，直到遇到左括号或栈空才将低优先级的那个符号入栈

代码实现如下：

1. #include <stdio.h>
2. #include <stdlib.h>
3.  
4. #define STACK_INIT_SIZE 20
5. #define STACKINCREMENT 10
6.  
7. typedef char ElemType;
8. typedef struct
9. {
10. ElemType *base;
11. ElemType *top;
12. int stackSize;
13. }sqStack;
14.  
15. InitStack(sqStack *s)
16. {
17. s->base = (ElemType *)malloc(STACK_INIT_SIZE * sizeof(ElemType));
18. if( !s->base )
19. exit(0);
20.  
21. s->top = s->base;
22. s->stackSize = STACK_INIT_SIZE;
23. }
24.  
25. Push(sqStack *s, ElemType e)
26. {
27. // 栈满，追加空间，鱼油必须懂！
28. if( s->top - s->base >= s->stackSize )
29. {
30. s->base = (ElemType *)realloc(s->base, (s->stackSize + STACKINCREMENT) * sizeof(ElemType));
31. if( !s->base )
32. exit(0);
33.  
34. s->top = s->base + s->stackSize;
35. s->stackSize = s->stackSize + STACKINCREMENT;
36. }
37.  
38. *(s->top) = e; // 存放数据
39. s->top++;
40. }
41.  
42. Pop(sqStack *s, ElemType *e)
43. {
44. if( s->top == s->base )
45. return;
46.  
47. *e = *--(s->top); // 将栈顶元素弹出并修改栈顶指针
48. }
49.  
50. int StackLen(sqStack s)
51. {
52. return (s.top - s.base);
53. }
54.  
55. int main()
56. {
57. sqStack s;
58. char c, e;
59.  
60. InitStack( &s );
61.  
62. printf("请输入中缀表达式，以#作为结束标志：");
63. scanf("%c", &c);
64.  
65. while( c != '#' )
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. Pop(&s, &e);
80. while( '(' != e )
81. {
82. printf("%c ", e);
83. Pop(&s, &e);
84. }
85. }
86. else if( '+'==c || '-'==c )
87. {
88. if( !StackLen(s) )
89. {
90. Push(&s, c);
91. }
92. else
93. {
94. do
95. {
96. Pop(&s, &e);
97. if( '(' == e )
98. {
99. Push(&s, e);
100. }
101. else
102. {
103. printf("%c ", e);
104. }
105. }while( StackLen(s) && '('!=e );
106. Push(&s, c);
107. }
108. }
109. else if( '*'==c || '/'==c || '('==c )
110. {
111. Push(&s, c);
112. }
113. else if( '#'== c )
114. {
115. break;
116. }
117. else
118. {
119. printf("\n出错：输入格式错误！\n");
120. return -1;
121. }
122.  
123. scanf("%c", &c);
124. }
125.  
126. while( StackLen(s) )
127. {
128. Pop(&s, &e);
129. printf("%c ", e);
130. }
131.  
132. return 0;
133. }

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

原文链接：https://blog.csdn.net/qq_41686130/article/details/82858997