C++逆波兰式转化成中缀表达式，并输出最终计算结果

时间：2021-08-16 14:47:01 阅读：22 评论：0 收藏：0 [点我收藏+]

大学时学数据结构的时候就有练过中缀表达式转化成逆波兰式，现在反过来写个将逆波兰式转化成中缀表达式的程序，并输出最终结果。

1.算法核心思路：

（1）考虑到需要转化成中缀表达式，还要计算最终结果，所以设计一个结构体，包含两个成员变量（操作数、该操作数对应的表达式）；

（2）从逆波兰式第一个字符开始，遇到数字时将该数字字符压入数据栈（结构体类型），遇到四则运算符压入运算符栈（字符型），遇到其它字符时抛出异常；

（3）当运算符栈不为空时，从运算符栈弹出一个运算符，从数据栈中弹出两个数据，将两个数据的操作数和运算符进行运算，得到新的数据的操作数，将两个数据的表达式和运算符组合（运算符为‘*’、‘/’时，需在表达式两端加上一对小括号），得到新的数据的表达式，将新数据压入数据栈；

（4）最后只剩下数据栈中只有一个数据，该数据的表达式即最终的中缀表达式，该数据的操作数即最终的计算结果。

2.举例：

（1）如：逆波兰式：ab+cd+e*-

　　 ab+cd+e*- ——> (a+b)cd+e*- ——> (a+b)(c+d)e*- ——> (a+b)(c+d)*e- ——> (a+b)-(c+d)*e

　　中缀表达式：(a+b)-(c+d)*e

（2）如：逆波兰式：12+34+5*-

　　 12+34+5*- ——> (1+2)34+5*- ——> (1+2)(3+4)5*- ——> (1+2)(3+4)*5- ——> (1+2)-(3+4)*5

　　中缀表达式：(1+2)-(3+4)*5

　　最终计算结果：-32

　　输出：(1+2)-(3+4)*5=-32

（3）如：逆波兰式：12+2/34*+

　　 12+2/34*+ ——> (1+2)2/34*+ ——> (1+2)/234*+ ——> (1+2)/23*4+ ——> (1+2)/2+3*4

　　中缀表达式：(1+2)/2+3*4

　　最终计算结果：13.5

　　输出：(1+2)/2+3*4=13.5

3.代码实现：

  1 #include<iostream>
  2 #include<string>
  3 #include<stack>
  4 using namespace std;
  5 
  6 struct DataNum {
  7     float num;    //存放操作数
  8     string str;    //存放操作数对应的式子
  9     DataNum(float n, string s) :num(n), str(s) {}
 10 };
 11 
 12 //执行运算，返回运算结果
 13 float FuncOperate(float a, float b, char ch)
 14 {
 15     float result = 0;
 16 
 17     switch (ch)
 18     {
 19     case ‘+‘: result = a + b; break;
 20     case ‘-‘: result = a - b; break;
 21     case ‘*‘: result = a * b; break;
 22     case ‘/‘: result = a / b; break;
 23     }
 24 
 25     return result;
 26 }
 27 
 28 //逆波兰式转换成中缀表达式
 29 void FuncRPNtoEquation(string strRPN)
 30 {
 31     stack<char> stCh;
 32     stack<DataNum> stDa;
 33     unsigned int i = 0;
 34     float num1 = 0, num2 = 0;
 35     char ch = ‘ ‘;
 36     DataNum da(0, "");
 37 
 38     for (i = 0; i < strRPN.length(); i++)
 39     {
 40         if ((strRPN[i] >= ‘0‘) && (strRPN[i] <= ‘9‘))
 41         {
 42             da.num = (float)(strRPN[i] - ‘0‘);
 43             da.str = "" + to_string((int)da.num);
 44             stDa.push(da);
 45         }
 46         else if ((strRPN[i] == ‘+‘) || (strRPN[i] == ‘-‘) || (strRPN[i] == ‘*‘) || (strRPN[i] == ‘/‘))
 47         {
 48             stCh.push(strRPN[i]);
 49         }
 50         else
 51         {
 52             throw strRPN[i];
 53         }
 54 
 55         //判断执行算术运算
 56         if ((stDa.size() >= 2) && (!stCh.empty()))
 57         {
 58             ch = stCh.top();
 59             da.str = ch;
 60             stCh.pop();
 61 
 62             num2 = stDa.top().num;
 63             da.str = da.str + stDa.top().str;
 64             stDa.pop();
 65 
 66             num1 = stDa.top().num;
 67             da.str = stDa.top().str + da.str;
 68             stDa.pop();
 69 
 70             if ((i != strRPN.size() - 1) && (ch != ‘*‘) && (ch != ‘/‘))
 71             {
 72                 da.str = "(" + da.str + ")";
 73             }
 74 
 75             da.num = FuncOperate(num1, num2, ch);
 76             stDa.push(da);
 77         }
 78     }
 79 
 80     cout << stDa.top().str << "=" << stDa.top().num << endl;
 81 }
 82 
 83 int main()
 84 {
 85     string str;
 86     while (getline(cin, str, ‘\n‘))
 87     {
 88         if ((str[0] < ‘0‘) || (str[0] > ‘9‘))
 89         {
 90             cout << "Input Error!" << endl;
 91         }
 92         else
 93         {
 94             try 
 95             {
 96                 FuncRPNtoEquation(str);
 97             }
 98             catch (char ch)
 99             {
100                 cout << "‘" << ch << "‘ is illegal!" << endl;
101             }
102             catch (...)
103             {
104                 cout << "Error!" << endl;
105             }
106         }
107     }
108 
109     return 0;
110 }