算法训练营第十一天 | 20. 有效的括号、 1047. 删除字符串中的所有相邻重复项、150. 逆波兰表达式求值

目录：

1.  力扣  20. 有效的括号
2. 力扣  1047. 删除字符串中的所有相邻重复项
3. 力扣  150. 逆波兰表达式求值

---

问题一、 20. 有效的括号

题目链接：20. 有效的括号 - 力扣（LeetCode）
思路分析：

      很多朋友刚开始接触这一类题的时候 , 可能会没有思路

       1、使用栈来解决。

       2、遍历字符串，遇到左括号（  " { " 、" [ "、" ( " ）,我们将右括号压入栈中。

       3、当我们遇到右括号时，则和栈顶元素进行匹配，如果不相等则说明没有有效的括号。如果         相等，则匹配成功，将其出栈。

       4、循环结束之后，如果栈为空，则说明括号是有效的。

文章讲解/视频讲解（代码随想录）:  代码随想录

问题解答：

bool isValid(string s) {stack< char >st;   //定义一个栈//要括号都匹配,说明传入的字符串一定是偶数if( s.length() %2!=0)  return false;for(int i = 0 ;i < s.length() ; i++){if( s[i]=='('){st.push( ')' );continue;}else if( s[i] == '{'){st.push( '}' );continue;}else if( s[i]== '['){st.push( ']' );continue;}//开始匹配else if( st.empty()!=true && s[i]==st.top()){st.pop();continue;} else {return false;}}if(st.empty()){return true;}return false;
}

---

问题二、1047. 删除字符串中的所有相邻重复项

题目链接：1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）
思路分析：

1. 利用栈的特性 ，用来记录字符串中已经遍历的数据
2. for 循环遍历字符串 , 如果我们的当前字符和栈顶元素相同,则出栈,不同则将其压入栈
3. 最后我们需要元素就是栈中的元素,但是我们需要注意的是 , 栈中元素和我们想要的顺序是相反的。
4. 提示我们使用字符串来模拟栈的操作

文章讲解/视频讲解 （代码随想录） :  代码随想录

问题解答：

tring removeDuplicates(string s) {string ret;    //用来记录我们遍历过的数据(用字符串来模拟栈的结构)for(int i=0 ; i<s.length() ; i++ ){//每遍历一个元素都要和栈中的元素进行比较if(ret.empty() || ret.back()!=s[i]){    //不相等的情况ret.push_back(s[i]);}else {ret.erase(ret.end()-1);}}return ret;
}

---

问题三、150. 逆波兰表达式求值

问题链接：150. 逆波兰表达式求值 - 力扣（LeetCode）
思路分析：

1. 还是利用栈的特性( 可以记录当前元素的前一个数据 )。

2. 遍历字符串,将整数依次放入栈中,如果遇到有效运算符,这从栈中取出两个数据进行计算

3. 将计算的结果再次放入栈中。

4. 最后栈中剩余的元素，就是我们表达式的值。

5. 这里我们想要主要的是 ，从栈中取出的两个元素  ，在进行运算的时候，是后一个元素放在前面，比如取出的数据是  a,b   。操作时应该是 b-a  |   b*a。

6. 补充:  C++ 中  std::stoi（string to integer）将字符串转换为整数类型。

文章 | 视频讲解（代码随想录）：代码随想录

---

问题解答：

我这里给出的过程比较冗余,大家可以改进优化一下.

class Solution {
public:void getAB(int &a,int &b){a=st.top();st.pop();b=st.top();st.pop();
}
int evalRPN(vector<string>& tokens) {//2. 遍历字符串,将整数依次放入栈中,如果遇到有效运算符,这从栈中取出两个数据进行计算//3. 将计算的结果再次放入栈中 int a=0 , b=0, temp=0;for(int i=0 ; i < tokens.size() ; i++){if( tokens[i]=="*" ){getAB(a,b);temp = a*b;st.push(temp);continue;}else if( tokens[i]=="/" ){getAB(a,b);temp=b/a;st.push(temp);continue;}else if( tokens[i]=="+" ){getAB(a,b);temp=a+b;st.push(temp);continue;}else if( tokens[i]=="-" ){getAB(a,b);temp=b-a;st.push(temp);continue;}else{st.push(std::stoi(tokens[i]) );}}return st.top();
}
private://1. 定义一个栈stack< int >st;
};

总结:

栈的应用场景

合适做一些类似于爱消除的操作,因为栈帮助我们记录了 遍历数组当前元素时候，前一个元素是什么。