栈问题我们可以将其简单抽象为：什么时候进栈，什么时候出栈。虽然听起来有点像把大象装进冰箱分成几步这种垃圾问题，但是的确是我们在求解栈问题时候最先应当考虑的问题。

题目1（有效的括号 leetcode-20）

给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

示例

1
2
输入：s = "()"
输出：true

解题思路

这个题，是一道非常经典经典经典的题，从大一做matrix的时候就已经接触到他了，我们按照出入栈的条件思路来考虑他：当匹配到左括号的时候入栈，如果栈顶的左括号和要匹配的右括号是匹配的，那我们就把栈顶的元素弹出来，如果不是，那我们就直接return false了，因为显然(])这一看就无法匹配，而且([)]这显然也不是有效的括号排列。所以就直接获得代码：

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    bool isValid(string s) {
        stack<char>st;
        for(auto i:s){
            if(i=='('||i=='['||i=='{'){
                st.push(i);
                continue;
            }
            if(st.empty()){
                return false;
            }
            if((st.top()=='(' && i==')')
            ||(st.top()=='[' && i==']')
            ||(st.top()=='{'&& i=='}')){
                st.pop();
            }else{
                return false;
            }
        }
        if(st.empty()){
            return true;
        }
        return false;
    }
};

题目2（简化路径 leetcode-71）

给你一个字符串 path ，表示指向某一文件或目录的 Unix 风格 绝对路径 （以 ‘/‘ 开头），请你将其转化为 更加简洁的规范路径。

在 Unix 风格的文件系统中规则如下：

一个点 ‘.’ 表示当前目录本身。
此外，两个点 ‘..’ 表示将目录切换到上一级（指向父目录）。
任意多个连续的斜杠（即，’//‘ 或 ‘///‘）都被视为单个斜杠 ‘/‘。
任何其他格式的点（例如，’…’ 或 ‘….’）均被视为有效的文件/目录名称。
返回的 简化路径 必须遵循下述格式：

始终以斜杠 ‘/‘ 开头。
两个目录名之间必须只有一个斜杠 ‘/‘ 。
最后一个目录名（如果存在）不能 以 ‘/‘ 结尾。
此外，路径仅包含从根目录到目标文件或目录的路径上的目录（即，不含 ‘.’ 或 ‘..’）。
返回简化后得到的 规范路径 。

示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
示例 1：

输入：path = "/home/"

输出："/home"

解释：

应删除尾随斜杠。

示例 2：

输入：path = "/home//foo/"

输出："/home/foo"

解释：

多个连续的斜杠被单个斜杠替换。

示例 3：

输入：path = "/home/user/Documents/../Pictures"

输出："/home/user/Pictures"

解释：

两个点 ".." 表示上一级目录（父目录）。

示例 4：

输入：path = "/../"

输出："/"

解释：

不可能从根目录上升一级目录。

示例 5：

输入：path = "/.../a/../b/c/../d/./"

输出："/.../b/d"

解释：

"..." 在这个问题中是一个合法的目录名。

解题思路

这里放这么多的示例，不是因为我善意大发，是因为这b题有点难读懂，所以多放几个示例来简单理解一下，这个题目总而言之，就是让你遇到..就返回上一级，去掉重复的/，那显然，出入栈的条件就已经获得了，而我们这里要注意一点，如果我们是以字符char而不是以字符串string来做的话，就会非常的麻烦，所以我就直接先用一个vector<string>先把这些字符串单独拿出来，然后再通过简单的出入栈的条件判断，遇到..直接弹出，只压入string的方式，直接接解出这道题了，然后再把栈里的元素填进一个vector就ok，具体见代码：

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
class Solution {
public:
    string simplifyPath(string path) {
        stack<string>st;
        vector<string>arr;
        string temp="";
        for(int i=0;i<path.size();i++){
            if(path[i]!='/'){
                temp=temp+path[i];
            }
            if(path[i]=='/'){
                if(temp!=""){
                    arr.push_back(temp);
                }
                
                temp="";
            }
        }
        if(temp!=""&&temp!="/"){
            arr.push_back(temp);
        }
        for(int i=0;i<arr.size();i++){
            if(arr[i]!=".."&&arr[i]!="."){
                st.push(arr[i]);
            }
            if(arr[i]==".."&&!st.empty()){
                st.pop();
            }
        }
        string ans="/";
        vector<string>re_arr;
        for(int i=0;!st.empty();i++){
            re_arr.push_back(st.top());
            st.pop();
        }
        for(int i=re_arr.size()-1;i>=0;i--){
            if(i>=1){
                ans+=re_arr[i]+"/";
            }else{
                ans+=re_arr[i];
            }
        }
        return ans;
    }
};

题目3（最小栈 leetcode-155）

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。
实现 MinStack 类:
MinStack() 初始化堆栈对象。
void push(int value) 将元素 value 推入堆栈。
void pop() 删除堆栈顶部的元素。
int top() 获取堆栈顶部的元素。
int getMin() 获取堆栈中的最小元素。

解题思路

这道题我示例都懒得放，就是另外单独维护一个最小栈就ok了，这里就当回忆语法了

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class MinStack {
private:
    stack<int>st;
    stack<int>mins;
public:
    MinStack() {
        
    }
    
    void push(int value) {
        st.push(value);
        if(mins.empty()){
            mins.push(value);
        }else{
            if(value<=mins.top()){
                mins.push(value);
            }
        }
    }
    
    void pop() {
        if(st.top()==mins.top()){
            mins.pop();
        }
        if(!st.empty()){
            st.pop();
        }
        
    }
    
    int top() {
        return st.top();
    }
    
    int getMin() {
        return mins.top();
    }
};

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack* obj = new MinStack();
 * obj->push(value);
 * obj->pop();
 * int param_3 = obj->top();
 * int param_4 = obj->getMin();
 */

题目4（逆波兰表达式求值 leetcode-150）

给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。

请你计算该表达式。返回一个表示表达式值的整数。

注意：

有效的算符为 ‘+’、’-‘、’*’ 和 ‘/‘ 。
每个操作数（运算对象）都可以是一个整数或者另一个表达式。
两个整数之间的除法总是 向零截断 。
表达式中不含除零运算。
输入是一个根据逆波兰表示法表示的算术表达式。
答案及所有中间计算结果可以用 32 位 整数表示。

示例

1
2
3
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9

解题思路

我承认，这道题一开始我想复杂了，这道题其实还是很简单的，因为他没有括号去改变计算顺序，只有加减乘除，而且加减乘除还都仅仅局限在前后两位，所以出入栈的条件就显而易见了：看到数字就进栈，看到符号就把那俩数字拿出来计算，计算完之后把原来的两数字拿出来，把结果压入栈，用结果和后面的继续算就可以了，具体见代码：

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int>st;
        for(int i=0;i<tokens.size();i++){
            if(tokens[i]!="+"&&tokens[i]!="-"&&tokens[i]!="*"&&tokens[i]!="/"){
                int temp=stoi(tokens[i]);
                st.push(temp);
            }
            if(tokens[i]=="+"){
                int a,b;
                if(!st.empty()){
                    a=st.top();
                    st.pop();
                    if(!st.empty()){
                        b=st.top();
                        st.pop();
                    }
                }
                st.push(a+b);
            }
            if(tokens[i]=="-"){
                int a,b;
                if(!st.empty()){
                    a=st.top();
                    st.pop();
                    if(!st.empty()){
                        b=st.top();
                        st.pop();
                    }
                }
                st.push(b-a);
            }
            if(tokens[i]=="*"){
                int a,b;
                if(!st.empty()){
                    a=st.top();
                    st.pop();
                    if(!st.empty()){
                        b=st.top();
                        st.pop();
                    }
                }
                st.push(a*b);
            }
            if(tokens[i]=="/"){
                int a;
                int b;
                if(!st.empty()){
                    a=st.top();
                    st.pop();
                    if(!st.empty()){
                        b=st.top();
                        st.pop();
                        
                    }
                }
                st.push(b/a);
            }
        }
        return st.top();
    }
};

题目5（基本计算器 leetcode-224）

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例

1
2
输入：s = "(1+(4+5+2)-3)+(6+8)"
输出：23

解题思路

我们可以使用两个栈 nums 和 ops 。

nums ： 存放所有的数字
ops ：存放所有的数字以外的操作，+/- 也看做是一种操作
然后从前往后做，对遍历到的字符做分情况讨论：

空格 : 跳过
( : 直接加入 ops 中，等待与之匹配的 )
) : 使用现有的 nums 和 ops 进行计算，直到遇到左边最近的一个左括号为止，计算结果放到 nums
数字 : 从当前位置开始继续往后取，将整一个连续数字整体取出，加入 nums
+/- : 需要将操作放入 ops 中。在放入之前先把栈内可以算的都算掉，使用现有的 nums 和 ops 进行计算，直到没有操作或者遇到左括号，计算结果放到 nums
一些细节：

由于第一个数可能是负数，为了减少边界判断。一个小技巧是先往 nums 添加一个 0
为防止 () 内出现的首个字符为运算符，将所有的空格去掉，并将 (- 替换为 (0-，(+ 替换为 (0+（当然也可以不进行这样的预处理，将这个处理逻辑放到循环里去做）

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
class Solution {
public:
    void replace(string& s){
        int pos = s.find(" ");
        while (pos != -1) {
            s.replace(pos, 1, "");
            pos = s.find(" ");
        }
    }
    int calculate(string s) {
        // 存放所有的数字
        stack<int> nums;
        // 为了防止第一个数为负数，先往 nums 加个 0
        nums.push(0);
        // 将所有的空格去掉
        replace(s);
        // 存放所有的操作，包括 +/-
        stack<char> ops;
        int n = s.size();
        for(int i = 0; i < n; i++) {
            char c = s[i];
            if(c == '(')
                ops.push(c);
            else if(c == ')') {
                // 计算到最近一个左括号为止
                while(!ops.empty()) {
                    char op = ops.top();
                    if(op != '(')
                        calc(nums, ops);
                    else {
                        ops.pop();
                        break;
                    }
                }
            }
            else {
                if(isdigit(c)) {
                    int cur_num = 0;
                    int j = i;
                    // 将从 i 位置开始后面的连续数字整体取出，加入 nums
                    while(j <n && isdigit(s[j]))
                        cur_num = cur_num*10 + (s[j++] - '0');
                    // 注意上面的计算一定要有括号，否则有可能会溢出
                    nums.push(cur_num);
                    i = j-1;
                }
                else {
                    if (i > 0 && (s[i - 1] == '(' || s[i - 1] == '+' || s[i - 1] == '-')) {
                        nums.push(0);
                    }
                    // 有一个新操作要入栈时，先把栈内可以算的都算了
                    while(!ops.empty() && ops.top() != '(')
                        calc(nums, ops);
                    ops.push(c);
                }
            }
        }
        while(!ops.empty())
            calc(nums, ops);
        return nums.top();
    }
    void calc(stack<int> &nums, stack<char> &ops) {
        if(nums.size() < 2 || ops.empty())
            return;
        int b = nums.top(); nums.pop();
        int a = nums.top(); nums.pop();
        char op = ops.top(); ops.pop();
        nums.push(op == '+' ? a+b : a-b);
    }
};

易错点

总而言之，这个栈问题，就是要先把出入栈的条件想清楚，其实很多东西看起来很困难，但是真正上手去做，还是很简单的，最后一题除外，我也还要好好看看。