力扣 [20、1047、150]

20. 有效的括号

原题链接：

解题思路：

先找出所有需要处理的不同种类的情况：

然后尝试自己的思考，然后采用一种思路处理以上的三种情况。

1. 建立一个栈，然后遍历字符串s；
2. 每次遍历到一个字符，进行一次判断，如果当前字符是 左括号，则将其压入栈中。
3. 如果当前字符是右括号，则弹出栈顶元素，看当前栈顶元素是否与其配对。为什么要弹出栈顶的元素与当前的右括号配对呢？因为观察上述的3种情况，无论是嵌套的括号（第三种），还是并行配对的括号（第一种情况），与当前右括号配对的肯定是离当前右括号最近的那个左括号。然而栈顶元素的栈顶，一定是最后进来的元素，最后进来 = 离右括号最近的左括号。因为只有左括号进栈嘛，说明当前这个栈顶元素的左括号，是目前为止的遍历到的最后一个左括号，肯定是离当前的右括号最近的。

实现代码：

class Solution {
public:
    bool isValid(string s) {
        
        if (s.size() % 2 != 0) {
            return false;
        }

        //首先定义一个字符栈
        stack <char> stk;

        //然后遍历字符串s
        int n = s.size();
        for (int i=0; i < n; i   )
        {
            //如果为左括号就入栈！
            if (s[i] == '(' || s[i] == '[' || s[i] == '{')
            {
                stk.push(s[i]);
            }
            else //否则就是右括号，如果是右括号的话，就弹出栈顶元素然后出栈,两者相互匹配!
            {
                //先判断是否栈空，如果栈空，说明没有与当前右括号匹配的左括号！
                if (stk.empty()) {
                    return false;
                }

                //否则说明还存在左括号，取出来之后做判断：
                char ch = stk.top();
                if (ch == '(' && s[i] == ')' || ch == '['&&s[i] == ']' || ch=='{'&&s[i]=='}') {
                    stk.pop();
                }
                else return false;
            }
        }
        if (!stk.empty()) return false;
        else  return true;
    }
};

题目总结：

栈可以用来解决两两匹配的问题。
本题是用来匹配左右括号元素。

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

原题链接：

解题思路：

1. 创建一个栈。
2. 遍历字符串 s。
3. 当初始的时候栈空，则无脑入栈第一个元素。
4. 然后遍历第二个元素，如果下一个元素与当前栈顶元素一致，则将当前栈顶元素进行弹出。然后进行下一轮的遍历！
5. 直到元素遍历完为止。最后栈中所保留的元素一定是无重复的元素。
6. 只不过返回字符串的时候，需要先将栈中的元素依次弹出，利用一个string字符串进行接收，最后翻转string字符串，返回答案。

实现代码：

class Solution {
public:
    string removeDuplicates(string s) {
        int n = s.size();
        stack<char> st;

        for (int i=0; i < n; i   ) {
            if (st.empty()) {
                st.push(s[i]);
            }
            else {
                char tmp = st.top();
                if (tmp == s[i]) {
                    st.pop();
                }
                else {
                    st.push (s[i]);
                }
            }
        }

        string res;
        while ( !st.empty() ) {
            char tmp = st.top();
            res  = tmp;
            st.pop();
        }
        reverse(res.begin(), res.end());
        return res;
    }
};

题目总结

栈可以用来解决相邻元素的匹配问题。
可以用栈来存放遍历过的元素。
那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素。

150. 逆波兰表达式求值

原题链接：

解题思路：

了解逆波兰式的特点，本质是一个后缀表达式。

1. 处理的对象有：操作数，运算符。
2. 根据后缀表达式的特点可知：如果当前是操作数的话，则直接压入栈中。
3. 如果是运算符：则弹出栈顶的两个元素，然后进行运算，运算完毕后将答案返回栈中。
4. 遍历完后，栈中只剩一个元素，即为答案。
5. 所以存在一个特性，就是我们的栈中只会保留操作数，不会有字符运算符的存在。可以利用这个突破口，思考我们的栈是存放string类型的字符串元素还是存放数值类型的元素。

实现代码：

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        //定义一个栈stk：
        stack<int> stk;

        //然后开始遍历字符串数组
        //如果是数字字符就转化为int数字，压入栈中。
        int n = tokens.size();
        
        for (int i=0; i < n; i   )
        {
            //说明是数字字符，就压入栈中：
            if (tokens[i] != " " && tokens[i] != "-" && tokens[i] != "*" && tokens[i] != "/") {
                int t = stoi(tokens[i]);
                stk.push (t);
            }
            else    //否则就是运算符！
            {
                //从栈顶取出两个元素：
                int t1 = stk.top ();
                stk.pop ();
                int t2 = stk.top ();
                stk.pop ();

                if (tokens[i] == " ") {
                    stk.push (t1   t2);
                }
                else if (tokens[i] == "-") {
                    stk.push (t2 - t1);
                }
                else if (tokens[i] == "*") {
                    stk.push (t2 * t1);
                }
                else stk.push(t2 / t1);
            }
        }

        //返回栈顶元素：
        return stk.top();
    }
};

题目总结：

栈还可以用来解决表达式求值的问题。！！！

这篇好文章是转载于：学新通技术网