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

时间:2022-11-07 18:58:39

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

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

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

分析如下:

STEP1:

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

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

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

STEP2:

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

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

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

STEP3:

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

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

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

STEP4:

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

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

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

STEP5:

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

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

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

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

STEP6:

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

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

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

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