您的位置: 首页  >  文章  >  中缀表达式转后缀表达式C++代码

中缀表达式转后缀表达式C++代码

分类: 文章 • 2025-02-09 10:30:59
[cpp] view plaincopy
  1. //MyStack.h
  3. #include<iostream>
  4. usingnamespacestd;
  6. template<classElemType>classMyStack
  7. {
  8. public:
  9. conststaticintMAXSIZE=100;
  10. ElemTypedata[MAXSIZE];
  11. inttop;
  13. public:
  14. voidinit();//初始化栈
  15. boolempty();//判断栈是否为空
  16. ElemTypegettop();//读取栈顶元素(不出栈)
  17. voidpush(ElemTypex);//进栈
  18. ElemTypepop();//出栈
  19. };
  22. template<classT>voidMyStack<T>::init()
  23. {
  24. this->top=0;
  25. }
  27. template<classT>boolMyStack<T>::empty()
  28. {
  29. returnthis->top==0?true:false;
  30. }
  32. template<classT>TMyStack<T>::gettop()
  33. {
  34. if(empty())
  35. {
  36. cout<<"栈为空！\n";
  37. exit(1);
  38. }
  39. returnthis->data[this->top-1];
  40. }
  42. template<classT>voidMyStack<T>::push(Tx)
  43. {
  44. if(this->top==MAXSIZE)
  45. {
  46. cout<<"栈已满！\n";
  47. exit(1);
  48. }
  49. this->data[this->top]=x;
  50. this->top++;
  51. }
  53. template<classT>TMyStack<T>::pop()
  54. {
  55. if(this->empty())
  56. {
  57. cout<<"栈为空!\n";
  58. exit(1);
  59. }
  61. Te=this->data[this->top-1];
  62. this->top--;
  63. returne;
  64. }


[cpp] view plaincopy
  1. //PrefixToPostfix.h
  3. #include<vector>
  4. usingnamespacestd;
  6. boolisoperator(charop);//判断是否为运算符
  7. intpriority(charop);//求运算符优先级
  8. voidpostfix(charpre[],charpost[],int&n);//把中缀表达式转换为后缀表达式
  9. doubleread_number(charstr[],int*i);//将数字字符串转变成相应的数字
  10. doublepostfix_value(charpost[]);//由后缀表达式字符串计算相应的中值表达式的值

[cpp] view plaincopy
  1. //PrefixToPostfix.cpp
  3. #include"MyStack.h"
  4. #include"PrefixToPostfix.h"
  6. #include<iostream>
  7. usingnamespacestd;
  9. voidmain()
  10. {
  11. MyStack<int>stack;
  12. stack.init();
  14. //charpre[]="22/(5*2+1)#";
  15. charexp[100];
  16. cout<<"输入表达式(中缀，以#结束)：";
  17. cin>>exp;
  19. charpost[100];
  20. //cout<<"中缀表达式为："<<pre<<endl;
  22. intn=0;//返回后缀表达式的长度
  23. postfix(exp,post,n);
  24. cout<<"后缀表达式为：";
  25. for(inti=0;i<n;i++)
  26. cout<<post[i];
  28. cout<<"\n由后缀表达式计算出的数值结果:";
  29. cout<<postfix_value(post)<<endl;
  31. system("pause");
  32. }
  34. boolisoperator(charop)
  35. {
  36. switch(op)
  37. {
  38. case'+':
  39. case'-':
  40. case'*':
  41. case'/':
  42. return1;
  43. default:
  44. return0;
  45. }
  46. }
  49. intpriority(charop)
  50. {
  51. switch(op)
  52. {
  53. case'#':
  54. return-1;
  55. case'(':
  56. return0;
  57. case'+':
  58. case'-':
  59. return1;
  60. case'*':
  61. case'/':
  62. return2;
  63. default:
  64. return-1;
  65. }
  66. }
  68. //把中缀表达式转换为后缀表达式，返回后缀表达式的长度（包括空格）
  69. voidpostfix(charpre[],charpost[],int&n)
  70. {
  71. inti=0,j=0;
  72. MyStack<char>stack;
  73. stack.init();//初始化存储操作符的栈
  75. stack.push('#');//首先把结束标志‘#’放入栈底
  77. while(pre[i]!='#')
  78. {
  79. if((pre[i]>='0'&&pre[i]<='9')||pre[i]=='.')//遇到数字和小数点直接写入后缀表达式
  80. {
  81. post[j++]=pre[i];
  82. n++;
  83. }
  84. elseif(pre[i]=='(')//遇到“（”不用比较直接入栈
  85. stack.push(pre[i]);
  86. elseif(pre[i]==')')//遇到右括号将其对应左括号后的操作符（操作符栈中的）全部写入后缀表达式
  87. {
  88. while(stack.gettop()!='(')
  89. {
  90. post[j++]=stack.pop();
  91. n++;
  92. }
  93. stack.pop();//将“（”出栈，后缀表达式中不含小括号
  94. }
  95. elseif(isoperator(pre[i]))
  96. {
  97. post[j++]='';//用空格分开操作数(
  98. n++;
  99. while(priority(pre[i])<=priority(stack.gettop()))
  100. {
  101. //当前的操作符小于等于栈顶操作符的优先级时，将栈顶操作符写入到后缀表达式，重复此过程
  102. post[j++]=stack.pop();
  103. n++;
  104. }
  106. stack.push(pre[i]);//当前操作符优先级大于栈顶操作符的优先级，将该操作符入栈
  107. }
  109. i++;
  110. }
  111. while(stack.top)//将所有的操作符加入后缀表达式
  112. {
  113. post[j++]=stack.pop();
  114. n++;
  115. }
  116. }
  118. doubleread_number(charstr[],int*i)
  119. {
  120. doublex=0.0;
  121. intk=0;
  122. while(str[*i]>='0'&&str[*i]<='9')//处理整数部分
  123. {
  124. x=x*10+(str[*i]-'0');
  125. (*i)++;
  126. }
  128. if(str[*i]=='.')//处理小数部分
  129. {
  130. (*i)++;
  131. while(str[*i]>='0'&&str[*i]<='9')
  132. {
  133. x=x*10+(str[*i]-'0');
  134. (*i)++;
  135. k++;
  136. }
  137. }
  138. while(k!=0)
  139. {
  140. x/=10.0;
  141. k--;
  142. }
  144. returnx;
  145. }
  147. doublepostfix_value(charpost[])
  148. {
  149. MyStack<double>stack;//操作数栈
  150. stack.init();
  152. inti=0;
  153. doublex1,x2;
  155. while(post[i]!='#')
  156. {
  157. if(post[i]>='0'&&post[i]<='9')
  158. stack.push(read_number(post,&i));
  159. elseif(post[i]=='')
  160. i++;
  161. elseif(post[i]=='+')
  162. {
  163. x2=stack.pop();
  164. x1=stack.pop();
  165. stack.push(x1+x2);
  166. i++;
  167. }
  168. elseif(post[i]=='-')
  169. {
  170. x2=stack.pop();
  171. x1=stack.pop();
  172. stack.push(x1-x2);
  173. i++;
  174. }
  175. elseif(post[i]=='*')
  176. {
  177. x2=stack.pop();
  178. x1=stack.pop();
  179. stack.push(x1*x2);
  180. i++;
  181. }
  182. elseif(post[i]=='/')
  183. {
  184. x2=stack.pop();
  185. x1=stack.pop();
  186. stack.push(x1/x2);
  187. i++;
  188. }
  189. }
  190. returnstack.gettop();
  191. }


运行结果：

中缀表达式转后缀表达式C++代码


相关推荐