20. 有效的括號

題目鏈接
解題思路：
有三種不匹配的情況：
第一種情況，字符串里左方向的括號多余了 。

第二種情況，括號沒有多余，但是 括號的類型沒有匹配上。

第三種情況，字符串里右方向的括號多余了，所以不匹配。

第一種情況：已經遍歷完了字符串，但是棧不為空，說明有相應的左括號沒有右括號來匹配，所以return false

第二種情況：遍歷字符串匹配的過程中，發現棧里沒有要匹配的字符。所以return false

第三種情況：遍歷字符串匹配的過程中，棧已經為空了，沒有匹配的字符了，說明右括號沒有找到對應的左括號return false

代碼如下：

class Solution {
public:bool isValid(string s) {if (s.size() % 2 != 0) return false; // 剪枝操作，如果s的長度為奇數，一定不符合要求stack<char> st;for (int i = 0; i < s.size(); i++) {if (s[i] == '(') st.push(')');else if (s[i] == '{') st.push('}');else if (s[i] == '[') st.push(']');// 第三種情況：遍歷字符串匹配的過程中，棧已經為空了，沒有匹配的字符了，說明右括號沒有找到對應的左括號 return false// 第二種情況：遍歷字符串匹配的過程中，發現棧里沒有我們要匹配的字符。所以return falseelse if (st.empty() || st.top() != s[i]) return false;else st.pop(); // st.top() 與 s[i]相等，棧彈出元素}// 第一種情況：此時我們已經遍歷完了字符串，但是棧不為空，說明有相應的左括號沒有右括號來匹配，所以return false，否則就return truereturn st.empty();  //判斷棧是否為空，如果不為空，也要return false；這里直接return st.empty()}
};

---

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

題目鏈接
解題思路：用字符串模擬棧
代碼如下：

class Solution {
public:string removeDuplicates(string S) {string result;for(char s : S) {if(result.empty() || result.back() != s) {result.push_back(s);}else {result.pop_back();}}return result;}
};

---

150. 逆波蘭表達式求值

題目鏈接
解題思路：其實逆波蘭表達式相當于是二叉樹中的后序遍歷
代碼如下：

class Solution {
public:int evalRPN(vector<string>& tokens) {// 力扣修改了后臺測試數據，需要用longlongstack<long long> st; for (int i = 0; i < tokens.size(); i++) {if (tokens[i] == "+" || tokens[i] == "-" || tokens[i] == "*" || tokens[i] == "/") {long long num1 = st.top();st.pop();long long num2 = st.top();st.pop();if (tokens[i] == "+") st.push(num2 + num1);if (tokens[i] == "-") st.push(num2 - num1);if (tokens[i] == "*") st.push(num2 * num1);if (tokens[i] == "/") st.push(num2 / num1);} else {st.push(stoll(tokens[i]));}}int result = st.top();st.pop(); // 把棧里最后一個元素彈出（其實不彈出也沒事）return result;}
};