题1：
指路：LeetCode20 有效的括号
思路与代码：
对于字符匹配这一类的对称匹配类的问题，处于栈的经典解决的舒适区。对于这个题我们可以定义一个栈用来盛放与左方向字符匹配的右方向字符，遇到右方向字符时判断与栈顶字符是否相等，相等则弹出栈顶元素，不相等则说明该字符串不匹配，属于无效字符。对于栈中元素，如果遍历完字符串之后栈内元素不为空则证明左方向字符数量多于右方向字符，属于无效字符；如果还没遍历完字符串栈已经为空则证明没有足够多的左方向字符与右方向字符相匹配，属于无效字符。开始遍历前，我们可以进行剪枝操作：如果该字符串的长度为奇数则一定没有相等数量的左右方向字符匹配，直接返回false即可。代码如下：
class Solution {
public:
bool isValid(string s) {
stack<char> st; // 定义一个栈
if (s.size() % 2 != 0) return false; // 剪枝：长度为奇数注定不匹配
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('}');
// 如果字符串还没遍历完栈已经为空就证明没有足够多的左方向字符能够与已经有的右方向字符匹配
// 或者如果栈顶元素不等于s[i]说明字符串内符号不匹配
else if (st.empty() || st.top() != s[i]) return false;
else st.pop(); // 左右方向符号相等弹出(相消)
}
return st.empty(); // 全弹出则说明相匹配
}
};题2：
指路：LeetCode1047 删除字符串中的所有相邻重复项
思路与代码：
同样是用栈解决的问题。我们定义一个栈，用来盛放已经遍历过的字符，当下一个遍历的字符与栈顶元素相等时(意味着这是相邻重复项)弹出栈顶元素直到字符串遍历结束。最后将栈顶元素出栈赋值给新字符串，反转实现正序。代码如下：
class Solution {
public:
stack<char> st;
string removeDuplicates(string s) {
for (int i = 0; i< s.size(); i++) {
if (st.empty() || s[i] != st.top()) { // 当栈为空或元素和栈顶元素不相等时
st.push(s[i]); // 元素入栈
}
else st.pop(); // 否则弹出栈顶元素
}
string result = "";
while (!st.empty()) { // 当栈内元素不为空时
result += st.top(); // 栈顶元素赋值给结果值
st.pop(); // 弹出栈顶元素
}
reverse (result.begin(), result.end());
return result;
}
};题2：
指路：LeetCode150 逆波兰表达式求值
思路与代码：
对于这个题我们定义一个栈，然后遍历字符串。当遇到数值的时候将数值压入栈，当遇到符号的时候取出两个栈顶元素进行运算直至运算成最后一个数再取出。代码如下：
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 res = st.top();
st.pop();
return res;
}
};