# PAT 解题报告 (数据结构学习与实验指导) 3-06. 表达式转换

### 3-06. 表达式转换算法分析：

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

void doPrint(const std::vector<std::string> &vecTokens) {
int iLen = vecTokens.size();
for(int i = 0; i < iLen; ++i) {
if(i) std::cout << ' ' << vecTokens[i];
else std::cout << vecTokens[i];
}
std::cout << std::endl;
return ;
}

bool isOperator(char c) {
switch(c) {
case '+':
case '-':
case '*':
case '/':
case '(':
case ')':
return true;
}
return false;
}

std::string eatFirstOperand(int *pPositon, const std::string &strInput) {
int iStart = *pPositon;
if('+' == strInput[iStart]) {
++iStart;
++*pPositon;
}
if('-' == strInput[iStart]) {
++*pPositon;
}
while(*pPositon < strInput.size() && !isOperator(strInput[*pPositon]))
++(*pPositon);
return strInput.substr(iStart, *pPositon - iStart);
}

void gao(const std::string &strInput) {
std::vector<std::string> vecResult;
int iLen = strInput.size();
std::stack<char> stkOperators;
int iPos = 0;
while(iPos < iLen) {
if(isOperator(strInput[iPos])) {
switch (strInput[iPos])
{
case '+':
case '-':
if(0 == iPos || '(' == strInput[iPos - 1]) {
vecResult.push_back(eatFirstOperand(&iPos, strInput));
continue;
}
while(!stkOperators.empty() && stkOperators.top() != '(') {
std::string strOperator("");
strOperator.push_back(stkOperators.top());
stkOperators.pop();
vecResult.push_back(strOperator);
}
stkOperators.push(strInput[iPos]);
break;
case ')':
while(stkOperators.top() != '(') {
std::string strOperator("");
strOperator.push_back(stkOperators.top());
stkOperators.pop();
vecResult.push_back(strOperator);
}
stkOperators.pop();
break;
case '*':
case '/':
case '(':
stkOperators.push(strInput[iPos]);
break;
default:
break;
}
++iPos;
}
else {
vecResult.push_back(eatFirstOperand(&iPos, strInput));
}
}
while(!stkOperators.empty()) {
std::string strOperator("");
strOperator.push_back(stkOperators.top());
stkOperators.pop();
vecResult.push_back(strOperator);
}
doPrint(vecResult);
return ;
}

int main() {
std::string strInput;
std::cin >> strInput;
gao(strInput);
return 0;
}
```

### 3-06. 表达式转换注意点：

Written on April 19, 2014