Have you met this question in a real interview?
Yes
Clarification
Definition ofPolish Notation:
Example
For the expression[(5 − 6) * 7](which represented by["(", "5", "−", "6", ")", "*", "7"]), the corresponding polish notation is[* - 5 6 7](which the return value should be["*", "−", "5", "6", "7"]).
class Solution {
public:
/
**
* @param expression: A string array
* @return: The Polish notation of this expression
*/
vector<string> convertToPN(vector<string> &expression) {
// write your code here
vector<string> res;
stack<string> s1, s2;
for (int i = expression.size() - 1; i >= 0; --i) {
string s = expression[i];
if (s == ")") {
s2.push(s);
} else if (s == "(") {
while (!s2.empty() && s2.top() != ")") {
s1.push(s2.top());
s2.pop();
}
s2.pop();
} else {
if (!IsOperator(s)) {
s1.push(s);
} else {
while (!s2.empty() && Precedence(s2.top()) > Precedence(s)) {
s1.push(s2.top());
s2.pop();
}
s2.push(s);
}
}
}
while (!s2.empty()) {
s1.push(s2.top());
s2.pop();
}
while (!s1.empty()) {
res.push\_back(s1.top());
s1.pop();
}
return res;
}
int Precedence(string& op) {
if (op == "+" || op == "-") {
return 1;
}
if (op == "*" || op == "/") {
return 2;
}
return 0;
}
bool IsOperator(string& s) {
return s == "+" || s == "-" || s == "*" || s == "/";
}
};