# PAT 解题报告 (数据结构学习与实验指导) 3-07. 求前缀表达式的值

### 3-07. 求前缀表达式的值算法分析：

```#include <iostream>
#include <string>
#include <stack>
#include <vector>

int getType(const std::string &strToken)
{
int iLen = strToken.size();

if(iLen > 1)
return TYPE_OPERAND;
if(iLen == 1) {
switch (strToken[0])
{
case '+':
case '-':
case '*':
case '/':
return TYPE_OPERATOR;
default:
if(strToken[0] >= '0' && strToken[0] <= '9')
return TYPE_OPERAND;
return TYPE_INVALID;
}
}
return TYPE_INVALID;
}

double calc(double value1, double value2, char op)
{
if('+' == op)
return value1 + value2;
if('-' == op)
return value1 - value2;
if('*' == op)
return value1 * value2;
if('/' == op) {
if(0 == value2)
throw ERROR_ARITHMETIC;
return value1 / value2;
}
throw ERROR_UNDEFINED;
}

double calcPrefixValue2(const std::vector<std::string> &vecTokens)
{
std::stack<double> stk;
int iLen = vecTokens.size();
for(int i = iLen - 1; i >= 0; --i) {
int iType = getType(vecTokens[i]);
if(TYPE_OPERAND == iType) {
stk.push(atof(vecTokens[i].c_str()));
}
if(TYPE_OPERATOR == iType) {
if(stk.size() <= 1)
throw ERROR_INVALID_OPERATION;
double op1 = stk.top(); stk.pop();
double op2 = stk.top(); stk.pop();
stk.push(calc(op1, op2, vecTokens[i][0]));
}
if(TYPE_INVALID == iType) {
throw ERROR_INVALID_OPERATION;
}
}
if(stk.size() != 1)
throw ERROR_STK_WRONG_SIZE;
return stk.top();
}

int main()
{
std::string strInput;
std::vector<std::string> vecTokens;

while(std::cin >> strInput)
vecTokens.push_back(strInput);
try {
double dRet = calcPrefixValue2(vecTokens);
printf("%.1lf\n", dRet);
}
catch(int iException) {
printf("ERROR\n");
}
return 0;
}
```

### 3-07. 求前缀表达式的值注意点(发散知识点)：

（全文完，原创文章，转载时请注明作者和出处）

（转载本站文章请注明作者和出处 烟客旅人 sigmainfy — http://www.sigmainfy.com，请勿用于任何商业用途）

Written on April 20, 2014