代碼隨想錄算法訓練營第37期 第十一天 | LeetCode20. 有效的括號、1047. 刪除字符串中的所有相鄰重復項、150. 逆波蘭表達式求值

---

一、20. 有效的括號

解題代碼C++：

class Solution {
public:bool isValid(string s) {stack<char> stk;for(int i = 0; s[i]; i ++){if(s[i] == '(') stk.push(')');else if(s[i] == '[') stk.push(']');else if(s[i] == '{') stk.push('}');else if(stk.empty() || stk.top() != s[i]) return false;else stk.pop();}return stk.empty();}
};

題目鏈接/文章講解/視頻講解：
https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html

---

---

二、1047. 刪除字符串中的所有相鄰重復項

解題代碼C++：

class Solution {
public:string removeDuplicates(string s) {stack<char> stk;for(int i = 0; s[i]; i ++){if(!stk.empty() && s[i] == stk.top()){stk.pop();}else stk.push(s[i]);}string str = "";while(!stk.empty()){str += stk.top();stk.pop();}reverse(str.begin(), str.end());return str;}
};

題目鏈接/文章講解/視頻講解：
https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html

---

---

三、150. 逆波蘭表達式求值

解題代碼C++：

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<long long> stk;for(int i = 0; i < tokens.size(); i ++){if(tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/"){long long num1 = stk.top();stk.pop();long long num2 = stk.top();stk.pop();if (tokens[i] == "+") stk.push(num2 + num1);if (tokens[i] == "-") stk.push(num2 - num1);if (tokens[i] == "*") stk.push(num2 * num1);if (tokens[i] == "/") stk.push(num2 / num1);}else stk.push(stoll(tokens[i]));}int res = stk.top();stk.pop();return res;}
};

題目鏈接/文章講解/視頻講解：
https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html