前言
题目: 150. 逆波兰表达式求值
文档: 代码随想录——逆波兰表达式求值
编程语言: C++
解题状态: 成功解答!
思路
还是利用栈的思想,遍历到数字时,加入栈,遍历到运算符时,取出两个数进行运算,并将结果加入到栈中。
代码
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
int item1;
int item2;
for (int i = 0; i < tokens.size(); i++) {
if (tokens[i] != "+" && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/") {
st.push(stoll(tokens[i]));
} else {
item1 = st.top();
st.pop();
item2 = st.top();
st.pop();
if (tokens[i] == "+") {
st.push(item1 + item2);
} else if (tokens[i] == "-") {
st.push(item2 - item1);
} else if (tokens[i] == "*") {
st.push(item2 * item1);
} else {
st.push(item2 / item1);
}
}
}
int res = st.top();
return res;
}
};
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( n ) O(n) O(n)