-
Notifications
You must be signed in to change notification settings - Fork 0
/
Convert Expression to Reverse Polish Notation.cpp
59 lines (55 loc) · 1.81 KB
/
Convert Expression to Reverse Polish Notation.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
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
stack<string> symbols;
vector<string> res;
for(string str : expression) {
if(str == "(") {
symbols.push(str);
} else if(str == "+" || str == "-") {
if(symbols.empty() || symbols.top() == "(") {
symbols.push(str);
} else {
while(!symbols.empty() && symbols.top() != "(") {
res.push_back(symbols.top());
symbols.pop();
}
symbols.push(str);
}
} else if(str == "*" || str == "/") {
if(symbols.empty()) {
symbols.push(str);
} else {
string tmp = symbols.top();
if(tmp == "+" || tmp == "-" || tmp == "(") {
symbols.push(str);
continue;
} else {
res.push_back(tmp);
symbols.pop();
symbols.push(str);
}
}
} else if(str == ")") {
while(symbols.top() != "(") {
res.push_back(symbols.top());
symbols.pop();
}
symbols.pop();
} else {
res.push_back(str);
}
}
while(!symbols.empty()) {
string temp = symbols.top();
symbols.pop();
res.push_back(temp);
}
return res;
}
};