【LeetCode热题100】栈

这道题一共记录了关于栈的5道题目：删除字符串中所有相邻重复项、比较含退格的字符串、基本计算器II、字符串解码、验证栈序列。

class Solution {
public:
    string removeDuplicates(string s) 
    {
        string ret;
        for(auto c : s)
        {
            if(ret.size() == 0 || c != ret.back()) ret += c;
            else ret.pop_back();
        }
        return ret;
    }
};

题目分析：这道题我们使用数组模拟栈，遍历字符串，把字符依次放到栈里，如果这个字符和栈顶字符一样，那么就出栈，否则入栈。

class Solution {
public:
    bool backspaceCompare(string s, string t) 
    {
        return ChangeStr(s) == ChangeStr(t);   
    }
    string ChangeStr(string s)
    {
        string ret; //用数组模拟栈结构
        for(auto c : s)
        {
            if(c != '#') ret += c;
            else if(ret.size() > 0) ret.pop_back();
        }
        return ret;
    }
};

题目分析：这道题也是用数组模拟栈，依次将两个字符串调整，比较调整完的字符串是否相等即可。

class Solution {
public:
    int calculate(string s) 
    {
        char op = '+';
        vector<int> st;
        int i = 0, n = s.size();
        while(i < n)
        {
            if(s[i] == ' ') i++;
            else if(s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while(i < n && s[i] >= '0' && s[i] <= '9')
                    tmp = tmp * 10 + (s[i++] - '0');
                if(op == '+') st.push_back(tmp);
                else if(op == '-') st.push_back(-tmp);
                else if(op == '*') st.back() *= tmp;
                else if(op == '/') st.back() /= tmp;
            }
            else
            {
                op = s[i++];
            }
        }
        int ret = 0;
        for(auto e : st)
        {
            ret += e;
        }
        return ret;
    }
};

题目分析：这道题我们使用栈来模拟计算过程，在遍历字符串的写一个字符时，需要分情况讨论：

遇到操作符，更新操作符op
遇到数字：

1）先把数字提取出来，记为tmp

2）根据op的不同，分情况讨论：

op == “+” ，tmp直接入栈

op == “-”，-tmp入栈

op == “*”，直接乘到栈顶元素上

op == “/”，直接除到栈顶元素上

class Solution {
public:
    string decodeString(string s) 
    {
        stack<string> st;
        st.push("");
        stack<int> num;
        int i = 0, n = s.size();
        while(i < n)
        {
            if(s[i] >= '0' && s[i] <= '9')
            {
                int tmp = 0;
                while(s[i] >= '0' && s[i] <= '9')
                {
                    tmp = tmp * 10 + s[i++] - '0';
                }
                num.push(tmp);
            }
            else if(s[i] == '[')
            {
                i++;
                string tmp;
                while(s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i++];
                }
                st.push(tmp);
            }
            else if(s[i] == ']')
            {
                string tmp = st.top();
                st.pop();
                int n = num.top();
                num.pop();
                while(n--)
                {
                    st.top() += tmp;
                }
                i++;
            }
            else
            {
                while(i < n && s[i] >= 'a' && s[i] <= 'z')
                {
                    st.top() += s[i++];
                }
            }
        }
        return st.top();
    }
};

题目分析：这道题需要借助建立两个栈来解决，其中一个栈用来存放次数，一个栈用来存放字符串，依次遍历这个字符串，分情况讨论：

1）遇到数字：提取出来这个数，放入“数字栈”。

2）遇到‘[’：把后面的字符串提取出来，放入“字符串栈”中。

3）遇到‘]’：解析，然后放到“字符串栈”栈顶的字符串后面。这里有一个细节需要注意，为了保证操作的一致性，需要在最开始把字符串栈初始化为""。

4）遇到单独的字符：提取出来这个字符串，直接放在“字符串栈”栈顶的字符串后面。

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) 
    {
        stack<int> st;
        int i = 0;
        for(auto e : pushed)
        {
            st.push(e);
            while(!st.empty() && st.top() == popped[i])
            {
                st.pop();
                i++;
            }
        }
        return st.empty();
    }
};