Given an expression string array, return the Reverse Polish notation of this expression. (remove the parentheses)
Have you met this question in a real interview?
Yes
Example
For the expression[3 - 4 + 5](which denote by ["3", "-", "4", "+", "5"]), return[3 4 - 5 +](which denote by ["3", "4", "-", "5", "+"])
class Solution {
public:
/\*\*
\* @param expression: A string array
\* @return: The Reverse Polish notation of this expression
\*/
vector<string> convertToRPN\(vector<string> &expression\) {
// write your code here
vector<string> res;
stack<string> s1, s2;
for \(string& s : expression\) {
if \(s == "\)"\) {
while \(s2.top\(\) != "\("\) {
s1.push\(s2.top\(\)\);
s2.pop\(\);
}
s2.pop\(\);
} else if \(s == "\("\) {
s2.push\(s\);
} else {
if \(IsNum\(s\)\) {
s1.push\(s\);
} else {
while \(!s2.empty\(\) && Precedence\(s\) <= Precedence\(s2.top\(\)\)\) {
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\(\);
}
reverse\(res.begin\(\), res.end\(\)\);
return res;
}
bool IsNum\(string& s\) {
for \(char c : s\) {
if \(!isdigit\(c\)\)
return false;
}
return true;
}
int Precedence\(string op\) {
if \(op == "-" \|\| op == "+"\) {
return 1;
}
if \(op == "\*" \|\| op == "/"\) {
return 2;
}
return 0;
}
};