华师一附中OI组

标题: 中缀表达式转后缀 [打印本页]
作者: admin    时间: 2020-9-6 21:49
标题: 中缀表达式转后缀
输入一个常见的中缀表达式，把它转成后缀表达式，简单起见，表达式中只含有大写字母和运算符+ - *  / ^等
比如输入（A+B*C）/D
输出 ABC*+D/
作者: admin    时间: 2020-9-6 21:51
这是堆栈应用的一个典型题目，因为四则远算的优先度的问题，先算括号里面的，再算乘除，最后算加减，所以我们不能简单粗暴的直接读入表达式，将运算符放在字母的后面，必须考虑优先度。而这个优先度的比较一般的做法是使用堆栈：在字符串中读到运算符的时候（它还在堆栈外面）将它与栈内栈顶的运算符比较优先度，
若小于，按照运算规则，弹出栈内栈顶的运算符，
或者等于，按照从左到右的规则也应该是弹出栈内栈顶的运算符，(有些运算相同级别可不是自左向右的呢，比如乘方，但是我们这里先不考虑)
若小于，则进入堆栈等待。
当然还有很多的细节，比如括号的处理，表达式开始和结尾的处理等


基本做法是：
1、在运算符栈的顶部先放入符号@，当@被弹出的时候表示计算结束；
2、读入字符，若是字母，则压入到字母栈；（其实是没有必要的，直接输出也可以）
3、若是运算符，则比较它与运算符栈栈顶的运算符的优先度，若<=，则弹出字母栈的两个字母进行运算，若>，则进栈等待，
    这里要特殊处理左右括号，对于左括号，无条件入栈，但是假设他的优先度最低，任何后面进去的符号都比他高，要进栈去等待处理，右括号的话，则依次弹出字母栈和算符栈里面的，直到碰到左括号为止。所以堆栈里面是不会有右括号的。
4、字符串处理完毕，将所有栈里面的数据依次弹出。

技巧：
做一个运算符优先度表，假设@符号优先度低为0,左括号优先度为1，+-的优先度为2，*/为3，^为4。这里还有个隐患（^是右结合，所以可能还需要两个有限度表，栈内的和栈外的）




作者: admin    时间: 2021-3-8 20:38
完整的程序如下，使用了c++内置的stack

  1. ///中缀表达式转后缀表达式
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. string sm,sp;
  5. stack <char> ss;
  6. int i,top;
  7. char ch;
  8. int p(char ch)   ///运算符优先度
  9. {
  10.         int  i;
  11.         if (ch=='^') i=4;
  12.         else if ((ch=='*') || (ch=='/')) i=3;
  13.         else if ((ch=='+') || (ch=='-')) i=2;
  14.         else if (ch=='(')  i=1;
  15.         else if (ch=='@') i=1;
  16.         return i;
  17. }


  20. int main()
  21. {

  23.         ss.push('@');// 放一个@在里面做标记
  24.         sp="";
  25.         cin>>sm;
  26.         for (i=0; i<=sm.size()-1; i++)
  27.                 {
  28.                         ch=sm[i];
  29.                         if (ch>='A' && ch<='Z') sp=sp+ch;   ///不是运算符直接输出
  30.                         else if ((ch=='+')||(ch=='-')||(ch=='*')||(ch=='/')||(ch=='^'))
  31.                                 {
  32.                                         while (p(ch)<=p(ss.top()))  ///不高于栈顶运算符的优先度则栈顶元素弹出
  33.                                                 {
  34.                                                         sp=sp+ss.top();
  35.                                                         ss.pop();
  36.                                                 }
  37.                                         ss.push(ch);   ///否则入栈
  38.                                 }
  39.                         else if (ch=='(')   ///左括号无条件入栈
  40.                                 ss.push(ch);
  41.                         else if (ch=')')  ///右括号的处理
  42.                                 {
  43.                                         while (ss.top()!='(')
  44.                                                 {
  45.                                                         sp=sp+ss.top();
  46.                                                         ss.pop();
  47.                                                 }
  48.                                         ss.pop();/// 左括号也弹出去
  49.                                 }
  50.                 }
  51.         while (ss.top()!='@')  /// 最后的依次弹出
  52.                 {
  53.                         sp=sp+ss.top();
  54.                         ss.pop();
  55.                 }
  56.         cout<<sp;
  57. }
  58. /*
  59. A
  60. A+B
  61. A+B*C
  62. (A+B*C+D/(E-F))*(W+T+X)-(R+V*(I+(J-K)*L)-M)
  63. */
复制代码






欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2