首页 > 代码库 > PAT-《数据结构学习与实验指导》实验项目集-3-07（MOOC2-3）求前缀表达式的值
PAT-《数据结构学习与实验指导》实验项目集-3-07（MOOC2-3）求前缀表达式的值
首先粘一下题目：
算术表达式有前缀表示法、中缀表示法和后缀表示法等形式。前缀表达式指二元运算符位于两个运算数之前，例如2+3*(7-4)+8/4的前缀表达式是：+ + 2 * 3 - 7 4 / 8 4。请设计程序计算前缀表达式的结果值。
输入格式说明：
输入在一行内给出不超过30个字符的前缀表达式，只包含+、-、*、\以及运算数，不同对象（运算数、运算符号）之间以空格分隔。
输出格式说明：
输出前缀表达式的运算结果，精确到小数点后1位，或错误信息“ERROR”。
样例输入与输出：
| 序号 | 输入 | 输出 |
| 1 | + + 2 * 3 - 7 4 / 8 4 | 13.0 |
| 2 | / -25 + * - 2 3 4 / 8 4 | 12.5 |
| 3 | / 5 + * - 2 3 4 / 8 2 | ERROR |
| 4 | +10.23 | 10.2 |
这里就不按照惯例给出建议的测试用例了，直接用题目中给的4个就可以了。
先说一下我的解题思路吧。
1. 首先要处理输入的数据，这里用到的数据结构有string data和stack<double>myStack，stack<int>intStack。string data要用getline()函数读入一整行字符串，如果直接用cin的话遇到空格读入会停止的。myStack用来存放中间结果，intStack用来存放读入“数字”字符。len是输入字符串的长度，dotPos记录了小数点的位置。
1 string data;2 stack<double> myStack;3 stack<int> intStack;4 int len = data.size();5 int dotPos = 0;6 getline(cin, data);
2. 接下来要用到for循环，从后向前的处理每一个字符。
1 for (int i=len-1; i!=-1; i--)2 {
3. 第一个if语句，用来判断是不是小数点，并且更新小数点位置dotPos。
1 if(data[i]==‘.‘)2 {3 dotPos = intStack.size();4 continue;5 }
4. 第二个if语句，用来判断是不是+ - * /，并且如果要是+ -还要考虑他们是一元运算符（表示正负），还是二元运算符（表示加减）。
1 if(data[i]==‘+‘ || data[i]==‘-‘ || data[i]==‘*‘ || data[i]==‘/‘)2 {
4.1 如果是一元运算符-（表示负），首先要从intStack中弹出全部的数字，把它们“拼接”成一个完整的整数（见while循环）。同时还要考虑这个数是整数，还是小数，那么之前的dotPos就用到了（见if语句）。只需要判断dotPos是不是0就可以了：如果是0，说明它是一个整数。如果不是0，说明它是一个浮点数。将小数点向前移动dotPos位，也就是除以10的dotPos次方。同时把这个数字乘以-1，压入myStack栈中。具体的代码如下：
1 if(data[i]==‘-‘ && intStack.size()!=0) 2 { 3 int icount = 0; 4 double itemp = 0; 5 int ilen = intStack.size(); 6 while(intStack.size() != 0) 7 { 8 int inttemp = intStack.top(); 9 intStack.pop();10 itemp += pow(10, ilen - 1 - icount) * inttemp;11 icount ++;12 }13 itemp *= -1;14 if(dotPos == 0)15 myStack.push(itemp);16 else17 {18 myStack.push(itemp / pow(10, dotPos));19 dotPos = 0;20 }21 continue;22 }
4.2 判断是一元运算符+（表示正），方法和上面几乎完全相同，只不过是少乘以一个-1就可以了，代码如下：
1 else if(data[i]==‘+‘ && intStack.size()!=0) 2 { 3 int icount = 0; 4 double itemp = 0; 5 int ilen = intStack.size(); 6 while(intStack.size() != 0) 7 { 8 int inttemp = intStack.top(); 9 intStack.pop();10 itemp += pow(10, ilen - 1 - icount) * inttemp;11 icount ++;12 }13 if(dotPos == 0)14 myStack.push(itemp);15 else16 {17 myStack.push(itemp / pow(10, dotPos));18 dotPos = 0;19 }20 continue;21 }
Tips：这里鼓励大家，尝试把两段代码捏在一起，这样能节约代码的行数。不妨试试看。
4.3 接下来就是判断二元运算符了，因为二元运算符必须要两个操作数，因此如果myStack栈中的数字少于两个，那么肯定就是ERROR了。同样，如果除法运算的除数是0，那肯定也是ERROR。进行+ - * /之后，不要忘记把结果压入myStack栈中。这部分比较简单，代码如下：
1 else if(myStack.size() < 2) 2 { 3 cout << "ERROR" << endl; 4 return 0; 5 } 6 double a = myStack.top(); 7 myStack.pop(); 8 double b = myStack.top(); 9 myStack.pop();10 double r = 0;11 switch(data[i])12 {13 case ‘+‘:14 r = a + b;15 break;16 case ‘-‘:17 r = a - b;18 break;19 case ‘*‘:20 r = a * b;21 break;22 case ‘/‘:23 r = a / b;24 {25 if (b != 0)26 r = a / b;27 else28 {29 cout << "ERROR" << endl;30 return 0;31 }32 }33 break;34 }35 myStack.push(r);36 continue;37 }
5. 第3个if语句，用来判断是不是空格，即‘ ‘，如果是空格的话，之前intStack栈中的数字，要全部弹出，组成一个新的数字，压入myStack栈中。方法其实上面已经有了。可以自己尝试写一下。代码如下：
1 if(data[i]==‘ ‘) 2 { 3 int icount = 0; 4 double itemp = 0; 5 int ilen = intStack.size(); 6 while(intStack.size() != 0) 7 { 8 int inttemp = intStack.top(); 9 intStack.pop();10 itemp += pow(10, ilen - 1 - icount) * inttemp;11 icount ++;12 }13 if(ilen != 0)14 {15 if(dotPos == 0)16 myStack.push(itemp);17 else18 {19 myStack.push(itemp / pow(10, dotPos));20 dotPos = 0;21 }22 }23 continue;24 }
6. 第4个if语句，用来判断是不是‘0‘到‘9‘，如果是的话，压入intStack栈中。注意压栈的时候要减掉‘0‘哦。因为data[i]可是字符。
1 if(data[i]>=‘0‘ && data[i]<=‘9‘)2 {3 intStack.push(data[i]-‘0‘);4 continue;5 }6 }
7. 输出结果，就是myStack栈中的那一个元素了。
1 printf("%.1lf", myStack.top());2 return 0;3 }
8. 完整代码如下：
1 #include <cstdio> 2 #include <cstdlib> 3 #include <iostream> 4 #include <iomanip> 5 #include <stack> 6 #include <cmath> 7 8 using namespace std; 9 int main() 10 { 11 string data; 12 stack<double> myStack; 13 stack<int> intStack; 14 int len = data.size(); 15 int dotPos = 0; 16 getline(cin, data); 17 for (int i=len-1; i!=-1; i--) 18 { 19 if(data[i]==‘.‘) 20 { 21 dotPos = intStack.size(); 22 continue; 23 } 24 if(data[i]==‘+‘ || data[i]==‘-‘ || data[i]==‘*‘ || data[i]==‘/‘) 25 { 26 if(data[i]==‘-‘ && intStack.size()!=0) 27 { 28 int icount = 0; 29 double itemp = 0; 30 int ilen = intStack.size(); 31 while(intStack.size() != 0) 32 { 33 int inttemp = intStack.top(); 34 intStack.pop(); 35 itemp += pow(10, ilen - 1 - icount) * inttemp; 36 icount ++; 37 } 38 itemp *= -1; 39 if(dotPos == 0) 40 myStack.push(itemp); 41 else 42 { 43 myStack.push(itemp / pow(10, dotPos)); 44 dotPos = 0; 45 } 46 continue; 47 } 48 else if(data[i]==‘+‘ && intStack.size()!=0) 49 { 50 int icount = 0; 51 double itemp = 0; 52 int ilen = intStack.size(); 53 while(intStack.size() != 0) 54 { 55 int inttemp = intStack.top(); 56 intStack.pop(); 57 itemp += pow(10, ilen - 1 - icount) * inttemp; 58 icount ++; 59 } 60 if(dotPos == 0) 61 myStack.push(itemp); 62 else 63 { 64 myStack.push(itemp / pow(10, dotPos)); 65 dotPos = 0; 66 } 67 continue; 68 } 69 else if(myStack.size() < 2) 70 { 71 cout << "ERROR" << endl; 72 return 0; 73 } 74 double a = myStack.top(); 75 myStack.pop(); 76 double b = myStack.top(); 77 myStack.pop(); 78 double r = 0; 79 switch(data[i]) 80 { 81 case ‘+‘: 82 r = a + b; 83 break; 84 case ‘-‘: 85 r = a - b; 86 break; 87 case ‘*‘: 88 r = a * b; 89 break; 90 case ‘/‘: 91 r = a / b; 92 { 93 if (b != 0) 94 r = a / b; 95 else 96 { 97 cout << "ERROR" << endl; 98 return 0; 99 }100 }101 break;102 }103 myStack.push(r);104 continue;105 }106 if(data[i]==‘ ‘)107 {108 int icount = 0;109 double itemp = 0;110 int ilen = intStack.size();111 while(intStack.size() != 0)112 {113 int inttemp = intStack.top();114 intStack.pop();115 itemp += pow(10, ilen - 1 - icount) * inttemp;116 icount ++;117 }118 if(ilen != 0)119 {120 if(dotPos == 0)121 myStack.push(itemp);122 else123 {124 myStack.push(itemp / pow(10, dotPos));125 dotPos = 0;126 }127 }128 continue;129 }130 if(data[i]>=‘0‘ && data[i]<=‘9‘)131 {132 intStack.push(data[i]-‘0‘);133 continue;134 }135 }136 printf("%.1lf", myStack.top());137 return 0;138 }
个人感觉：
按照老师的说法，这是一道可以尝试挑战一下自己的题。测试用例还是比较简单的，基本上给的4个都能过的话，肯定能AC。毕竟限制了30个字符的大小，不像PAT1074（即MOOC作业2-1）数据量那么大。
最后粘一下AC的结果：
PAT-《数据结构学习与实验指导》实验项目集-3-07（MOOC2-3）求前缀表达式的值