数据结构 栈的应用 逆波兰表达式

举报
悦来客栈的老板 发表于 2020/12/29 23:11:28 2020/12/29
【摘要】 #include <stdio.h>#include <stdlib.h> #define STACT_INIT_SIZE 100#define STACTINCREMENT 10#define OK 1#define ERROR 0#define OVERFLOW -2 typedef char SElemType; typedef struc...

  
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #define STACT_INIT_SIZE 100
  4. #define STACTINCREMENT 10
  5. #define OK 1
  6. #define ERROR 0
  7. #define OVERFLOW -2
  8. typedef char SElemType;
  9. typedef struct
  10. {
  11. SElemType *base;
  12. SElemType *top;
  13. int stacksize;
  14. }SqStack;
  15. int InitStack(SqStack &S)
  16. {
  17. S.base = (SElemType *)malloc(STACT_INIT_SIZE * sizeof(SElemType));
  18. if (!S.base)
  19. {
  20. exit(OVERFLOW);
  21. }
  22. S.top = S.base ;
  23. S.stacksize = STACT_INIT_SIZE;
  24. return OK;
  25. }
  26. int Push(SqStack &S, SElemType e)
  27. {
  28. if (S.top - S.base >= S.stacksize)
  29. {
  30. S.base = (SElemType*)realloc(S.base , (S.stacksize + STACTINCREMENT) * sizeof(SElemType));
  31. if (!S.base)
  32. {
  33. exit(OVERFLOW);
  34. }
  35. S.top = S.base + S.stacksize ;
  36. S.stacksize += STACTINCREMENT;
  37. }
  38. *S.top++ = e;
  39. return OK;
  40. }
  41. int Pop(SqStack &S, SElemType &e)
  42. {
  43. if (S.base == S.top)
  44. {
  45. return ERROR;
  46. }
  47. e = *--S.top;
  48. return OK;
  49. }
  50. int GetTop(SqStack S)
  51. {
  52. if (S.base == S.top)
  53. {
  54. return ERROR;
  55. }
  56. return *(S.top-1);
  57. }
  58. int StackEmpty(SqStack S)
  59. {
  60. if (S.top == S.base )
  61. {
  62. return 1;
  63. }
  64. return 0;
  65. }
  66. int DestroyStack(SqStack &S)
  67. {
  68. free(S.base);
  69. S.base = NULL;
  70. S.top = NULL;
  71. S.stacksize = 0;
  72. return OK;
  73. }
  74. char *RPExpression(char *e)
  75. {/*设置两个栈,s1用来存储操作符,s2用来存储数值和从s1弹出来的操作符,即逆波兰表达式*/
  76. SqStack s1,s2;
  77. InitStack(s1);
  78. InitStack(s2);
  79. Push(s1, '#');/*假设字符'#'是运算级别最低的运算符,并压入栈s1中*/
  80. char *p = e, ch;
  81. int length = 0;
  82. for (; *p != '\0'; p++)
  83. {
  84. switch (*p)
  85. {
  86. case '('://遇'('则直接入栈s1
  87. Push(s1,*p);
  88. break;
  89. case ')':
  90. //遇')'则将距离栈s1栈顶的最近的'('之间的运算符,逐个出栈,依次送入栈s2,此时抛弃'('
  91. while (GetTop(s1) != '(')
  92. {
  93. Pop(s1,ch);
  94. Push(s2,ch);
  95. }
  96. Pop(s1,ch);//将s1里面的(抛弃
  97. break;
  98. //遇下列运算符,则分情况讨论:
  99. //1.若当前栈s1的栈顶元素是'(',则当前运算符直接压入栈s1;
  100. //2.否则,将当前运算符与栈s1的栈顶元素比较,若优先级较栈顶元素大,则直接压入栈s1中,
  101. // 否则将s1栈顶元素弹出,并压入栈s2中,直到栈顶运算符的优先级别低于当前运算符,然后再将当前运算符压入栈s1中
  102. case '+':
  103. case '-':
  104. for (ch = GetTop(s1); ch != '#'; ch = GetTop(s1))
  105. {
  106. if (ch == '(')
  107. {
  108. break;
  109. }
  110. else
  111. {
  112. Pop(s1,ch);
  113. Push(s2,ch);
  114. }
  115. }
  116. Push(s1,*p);
  117. length++;
  118. break;
  119. case '*':
  120. case '/':
  121. for (ch = GetTop(s1); ch != '#'&&ch != '+' && ch != '-'; ch = GetTop(s1))
  122. {
  123. if (ch == '(')
  124. {
  125. break;
  126. }
  127. else
  128. {
  129. Pop(s1,ch);
  130. Push(s2,ch);
  131. }
  132. }
  133. Push(s1,*p);
  134. length++;
  135. break;
  136. //遇操作数则直接压入栈s2中
  137. default:
  138. Push(s2,*p);
  139. length++;
  140. }
  141. }
  142. //若栈s1非空,则将栈中元素依次弹出并压入栈s2中
  143. while (!StackEmpty(s1) && GetTop(s1) != '#')
  144. {
  145. Pop(s1,ch);
  146. Push(s2,ch);
  147. }
  148. //最后将栈s2输出,逆序排列成字符串;
  149. char *result;
  150. result = (char *)malloc(sizeof(char)*(length+1));
  151. result += length;
  152. *result = '\0';
  153. result--;
  154. for (;!StackEmpty(s2); result--)
  155. {
  156. Pop(s2,ch);
  157. *result = ch;
  158. }
  159. ++result;
  160. DestroyStack(s1);
  161. DestroyStack(s2);
  162. return result;
  163. }
  164. int main()
  165. {
  166. char str[10000];
  167. scanf("%s",str);
  168. printf("%s\n",RPExpression(str));
  169. return 0;
  170. }

文章来源: blog.csdn.net,作者:悦来客栈的老板,版权归原作者所有,如需转载,请联系作者。

原文链接:blog.csdn.net/qq523176585/article/details/17249133

【版权声明】本文为华为云社区用户转载文章,如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容,举报邮箱: cloudbbs@huaweicloud.com
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。