算法训练day11 栈与队列 02 LeetCode20.1047.150
20.有效的括号：
题目：
题解：
-
class Solution { public: bool isValid(string s) { stack<char> str; if (s.size() % 2 == 1) return false; for (int i = 0; i < s.size(); i++) { if (s[i] == '(' || s[i] == '[' || s[i] == '{') { str.push(s[i]); } else if (s[i] == ')' || s[i] == ']' || s[i] == '}') { if (str.empty()) { return false; } if (s[i] == ')' && str.top() == '(') str.pop(); else if (s[i] == ']' && str.top() == '[') str.pop(); else if (s[i] == '}' && str.top() == '{') str.pop(); else return false; } } return str.empty(); } }; -
字符串长度是否奇数遇左括号进栈，遇右括号则判断栈顶是否为对应的左括号，不适则返回false，循环结束判断栈是否为空
-
卡哥解法：
-
class Solution { public: bool isValid(string s) { if (s.size() % 2 != 0) return false; stack<char> str; for (int i = 0; i < s.size(); i++) { if (s[i] == '(') str.push(')'); else if (s[i] == '{') str.push('}'); else if (s[i] == '[') str.push(']'); else if (str.empty() || str.top() != s[i]) return false; else str.pop(); } return str.empty(); } }; -
补充了栈中没有匹配的括号的情况。
1047.删除字符串中的所有相邻重复项
题目：
题解：
-
class Solution { public: string removeDuplicates(string s) { stack<char> st; for (char S : s) { if (st.empty() || st.top() != S) { st.push(S); } else st.pop(); } string result = ""; while (!st.empty()) { result += st.top(); st.pop(); } reverse(result.begin(), result.end()); return result; } };
150.逆波兰表达式求值
题目：
题解：
-
class Solution { public: int evalRPN(vector<string> &tokens) { stack<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; } };