【数据结构】利用栈 求解表达式

前端之家收集整理的这篇文章主要介绍了【数据结构】利用栈 求解表达式前端之家小编觉得挺不错的,现在分享给大家,也给大家做个参考。

表达式求值问题,其中运算符号只包含 加减乘除 取整数 详细请参见代码


  1. #include <stdio.h>
  2.  
  3. #define MAX_SIZE 100
  4.  
  5. typedef struct
  6. {
  7. int top;
  8. char data[MAX_SIZE];
  9. }NumStack;
  10.  
  11. typedef struct
  12. {
  13. int top;
  14. char opera[MAX_SIZE];
  15. }OperaStack;
  16.  
  17. const char perior[5][5] =
  18. {
  19. '>','>','<',};
  20.  
  21. void NumPush(NumStack* L,int elem);
  22. void OperaPush(OperaStack* L,char elem);
  23. int NumPop(NumStack* L);
  24. char OperaPop(OperaStack* L);
  25. char comp_perior(char a,char b);
  26. int compute(int a,int b,char c);
  27. int pe2int(char a);
  28.  
  29. void main()
  30. {
  31. int i = 0;
  32. int j = 0;
  33. int num = 0;
  34. char expression[20] = "14+13-2*9+24/3=";
  35.  
  36. NumStack Num_stack = {0,};
  37. OperaStack Opera_stack = {0,};
  38.  
  39. while (expression[i] != '\0')
  40. {
  41. switch (expression[i])
  42. {
  43. case '0':
  44. case '1':
  45. case '2':
  46. case '3':
  47. case '4':
  48. case '5':
  49. case '6':
  50. case '7':
  51. case '8':
  52. case '9':
  53. num = 10*num + (expression[i]-'0');
  54. break;
  55. case '=':
  56. if (expression[i+1] != '\0')
  57. return;
  58. case '+':
  59. case '-':
  60. case '*':
  61. case '/':
  62. NumPush(&Num_stack,num);
  63.  
  64. if (Opera_stack.top == 0 || comp_perior(Opera_stack.opera[Opera_stack.top-1],expression[i]) == '<')
  65. OperaPush(&Opera_stack,expression[i]); // 栈空时直接入栈
  66. else
  67. {
  68. do
  69. {
  70. int temp = compute(NumPop(&Num_stack),NumPop(&Num_stack),OperaPop(&Opera_stack));
  71. NumPush(&Num_stack,temp);
  72. }while (comp_perior(Opera_stack.opera[Opera_stack.top-1],expression[i]) == '>');
  73.  
  74. OperaPush(&Opera_stack,expression[i]);
  75. }
  76.  
  77. num = 0;
  78. break;
  79. }
  80. i++;
  81. }
  82.  
  83. printf("计算的结果 = %d\n",Num_stack.data[Num_stack.top-1]);
  84. }
  85.  
  86. void NumPush(NumStack* L,int elem)
  87. {
  88. if (L->top+1 < MAX_SIZE)
  89. L->data[L->top++] = elem;
  90. }
  91.  
  92.  
  93. void OperaPush(OperaStack* L,char elem)
  94. {
  95. if ((L->top+1) < MAX_SIZE)
  96. L->opera[L->top++] = elem;
  97. }
  98.  
  99.  
  100. int NumPop(NumStack* L)
  101. {
  102. if (L->top == 0)
  103. return -1;
  104.  
  105. return (L->data[--L->top]);
  106. }
  107.  
  108.  
  109. char OperaPop(OperaStack* L)
  110. {
  111. if (L->top == 0)
  112. return -1;
  113.  
  114. return (L->opera[--L->top]);
  115. }
  116.  
  117. char comp_perior(char a,char b)
  118. {
  119. return perior[pe2int(a)][pe2int(b)];
  120. }
  121.  
  122. int pe2int(char a)
  123. {
  124. switch (a)
  125. {
  126. case '+':
  127. return 0;
  128. case '-':
  129. return 1;
  130. case '*':
  131. return 2;
  132. case '/':
  133. return 3;
  134. case '=':
  135. return 4;
  136. default:
  137. return -1;
  138. }
  139. }
  140.  
  141. int compute(int a,char c)
  142. {
  143. switch(c)
  144. {
  145. case '+':
  146. return a+b;
  147. case '-':
  148. return a-b;
  149. case '*':
  150. return a*b;
  151. case '/':
  152. return a/b;
  153. }
  154. }

猜你在找的数据结构相关文章