【数据结构】栈的应用——中缀表达式求值(c++)

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

文件


  1. #pragma once
  2.  
  3. #include <iostream>
  4. #include <assert.h>
  5. #include <string>
  6. using namespace std;
  7.  
  8. template<class Type>
  9. class SeqStack
  10. {
  11. public:
  12. SeqStack(size_t sz = INIT_SZ);
  13. ~SeqStack();
  14. public:
  15. bool empty()const;
  16. bool full()const;
  17. void show()const;
  18. bool push(const Type &x);
  19. bool pop();
  20. void gettop(Type &x);
  21. int length()const;
  22. void clear();
  23. void destory();
  24. void quit_system(Type &x);
  25. private:
  26. enum{ INIT_SZ = 64 };
  27. Type *base;
  28. int capacity;
  29. int top;
  30. };
  31.  
  32. template<class Type>
  33. SeqStack<Type>::SeqStack(size_t sz = INIT_SZ)
  34. {
  35. capacity = sz > INIT_SZ ? sz : INIT_SZ;
  36. base = new Type[capacity];
  37. assert(base != NULL);
  38. top = 0;
  39. }
  40.  
  41. template<class Type>
  42. SeqStack<Type>::~SeqStack()
  43. {
  44. destory();
  45. }
  46.  
  47. // 判断栈是否满了
  48. template<class Type>
  49. bool SeqStack<Type>::full()const
  50. {
  51. return (top >= capacity);
  52. }
  53.  
  54. // 判断是否为空栈
  55. template<class Type>
  56. bool SeqStack<Type>::empty()const
  57. {
  58. return (top == 0);
  59. }
  60.  
  61. // 显示
  62. template<class Type>
  63. void SeqStack<Type>::show()const
  64. {
  65. if (top == 0)
  66. {
  67. cout << "the stack is empty!" << endl;
  68. return;
  69. }
  70. for (int i = top - 1; i >= 0; --i)
  71. {
  72. cout << base[i] << endl;
  73. }
  74. }
  75.  
  76. // 入栈
  77. template<class Type>
  78. bool SeqStack<Type>::push(const Type &x)
  79. {
  80. if (full())
  81. {
  82. cout << "the stack is full,can not enter!" << endl;
  83. return false;
  84. }
  85. else
  86. {
  87. base[top] = x;
  88. top++;
  89. return true;
  90. }
  91. }
  92.  
  93. // 出栈
  94. template<class Type>
  95. bool SeqStack<Type>::pop()
  96. {
  97. if (empty())
  98. {
  99. cout << "the stack is empty,can not pop!" << endl;
  100. return false;
  101. }
  102. else
  103. {
  104. top--;
  105. return true;
  106. }
  107. }
  108.  
  109. // 获得栈顶元素
  110. template<class Type>
  111. void SeqStack<Type>::gettop(Type &x)
  112. {
  113. x = base[top - 1];
  114. }
  115.  
  116. // 求栈长度
  117. template<class Type>
  118. int SeqStack<Type>::length()const
  119. {
  120. return top;
  121. }
  122.  
  123. // 清空栈
  124. template<class Type>
  125. void SeqStack<Type>::clear()
  126. {
  127. top = 0;
  128. }
  129.  
  130. // 摧毁栈
  131. template<class Type>
  132. void SeqStack<Type>::destory()
  133. {
  134. delete[]base;
  135. base = NULL;
  136. capacity = top = 0;
  137. }
  138.  
  139. // 退出系统
  140. template<class Type>
  141. void SeqStack<Type>::quit_system(Type &x)
  142. {
  143. x = 0;
  144. }


函数


  1. #include "exp.h"
  2.  
  3. #include "exp.h"
  4.  
  5. //检查符号之间的优先级,1表示>,0表示=,-1表示<,c1栈内的运算,c2栈外的运算
  6. int check(char c1,char c2)
  7. {
  8. int a1,a2;
  9. if (c1 == '+' || c1 == '-')
  10. a1 = 3;
  11. if (c1 == '*' || c1 == '/')
  12. a1 = 5;
  13. if (c1 == '(')
  14. a1 = 1;
  15. if (c1 == ')')
  16. a1 = 7;
  17. if (c1 == '#')
  18. a1 = 0;
  19.  
  20. if (c2 == '+' || c2 == '-')
  21. a2 = 2;
  22. if (c2 == '*' || c2 == '/')
  23. a2 = 4;
  24. if (c2 == '(')
  25. a2 = 6;
  26. if (c2 == ')')
  27. a1 = 1;
  28. if (c2 == '#')
  29. a2 = 0;
  30.  
  31. if (a1 > a2)
  32. return 1;
  33. if (a1 == a2)
  34. return 0;
  35. if (a1 < a2)
  36. return -1;
  37. }
  38.  
  39. //符号运算函数
  40. double sum(char c,double d1,double d2)
  41. {
  42. switch (c)
  43. {
  44. case '+':
  45. return d1 + d2;
  46. break;
  47. case '-':
  48. return d1 - d2;
  49. break;
  50. case '*':
  51. return d1 * d2;
  52. break;
  53. case '/':
  54. return d1 / d2;
  55. break;
  56. default:
  57. break;
  58. }
  59. }
  60.  
  61. int main()
  62. {
  63. char *op = "+-*/()#";
  64. string str;
  65. cin >> str;
  66. //给表达式字符串str添加‘#’结束标志符
  67. str.append(1,'#');
  68. SeqStack<char> OPTR;//运算符栈
  69. SeqStack<double> OPND;//操作数栈
  70. int a = -1;
  71. //先将'#'入栈
  72. OPTR.push('#');
  73. while (true)
  74. {
  75. int b = a + 1;
  76. a = str.find_first_of(op,a + 1);
  77. if (a == string::npos)
  78. break;
  79. if (a != b)
  80. {
  81. string ss(str,b,a - b);
  82. double d = atof(ss.c_str());
  83. //数据先入栈
  84. OPND.push(d);
  85. }
  86. //运算符优先级比较
  87. char val;
  88. OPTR.gettop(val);
  89. int che = check(val,str[a]);
  90. if (-1 == che)//栈外优先级大直接入栈
  91. {
  92. OPTR.push(str[a]);
  93. }
  94. if (0 == che)//栈内外优先级相等则出栈
  95. {
  96. OPTR.pop();
  97. }
  98. if (1 == che)//栈内优先级大,出栈进行运算
  99. {
  100. char val;
  101. OPTR.gettop(val);
  102. double d1;
  103. OPND.gettop(d1);
  104. OPND.pop();
  105. double d2;
  106. OPND.gettop(d2);
  107. OPND.pop();
  108. d1 = sum(val,d2,d1);
  109. //运算结果入栈
  110. OPND.push(d1);
  111. OPTR.pop();
  112. a--;
  113. }
  114. }
  115. double s;
  116. OPND.gettop(s);
  117. cout << s << endl;
  118. return 0;
  119. }
  120.  


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