【LC】有效的括号,逆波兰表达式,栈的压入弹出序列,最小栈

我会带着你远行 2023-09-26 11:09 27阅读 0赞

![在这里插入图片描述][078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]✨**博客主页:**[ **XIN-XIANG荣**][_XIN-XIANG]  
✨**系列专栏:**[**【LeetCode/牛客刷题】**][LeetCode]  
✨**一句短话:** **难在坚持,贵在坚持,成在坚持!**

#### 文章目录 ####

*  1. 有效的括号(lc20)
 *   *  题目描述:
     *  解题思路：
     *  代码实现：
     *  提交结果：
 *  2. 逆波兰表达式(lc150)
 *   *  题目描述:
     *  解题思路：
     *  代码实现：
     *  提交结果：
 *  3. 栈的压入、弹出序列(牛客JZ31)
 *   *  题目描述:
     *  解题思路：
     *  代码实现：
     *  提交结果：
 *  4.最小栈(lc155)
 *   *  题目描述:
     *  解题思路：
     *  代码实现：
     *  提交结果：

## 1. 有效的括号(lc20) ##

### 题目描述: ###

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

左括号必须以正确的顺序闭合。

每个右括号都有一个对应的相同类型的左括号。

**示例 1**：

输入：s = “()”

输出：true

**示例 2**：

输入：s = “()\[\]\{\}”

输出：true

**示例 3**：

输入：s = “(\]”

输出：false

**提示**：

1 <= s.length <= 104

s 仅由括号 ‘()\[\]\{\}’ 组成

**来源**：力扣（LeetCode）

**链接**：[https://leetcode.cn/problems/valid-parentheses][https_leetcode.cn_problems_valid-parentheses]

### 解题思路： ###

可以使用一个栈来解决问题, 去遍历字符串s **, 碰到左括号**就将左括号字符就将字符**入栈** , **碰到右括号**字符此时再**去看栈顶元素和右括号是否匹配**, 遍历过程中可能会有以下情况出现,:

1.  **碰到右括号但栈中没有元素了**(字符串还没遍历完栈中就没有元素了), 表明此时的右括号没有匹配的左括号;
2.  碰到右括号, 栈顶是左括号但是和右括号**种类不匹配**,
3.  碰到右括号, 栈顶是左括号且和和右括号**种类匹配**, 此时继续往后面遍历字符串;
4.  **字符串遍历完了但栈中还有元素,** 此时栈中的左括号没有匹配的右括号

![img][]

### 代码实现： ###

class Solution {
        
        public boolean isValid(String s) {
        
            Stack<Character> stack = new Stack();
            for(int i = 0; i < s.length(); i++) {
        
                char ch1 = s.charAt(i);
                if(ch1=='(' || ch1=='[' || ch1=='{') {
        
                    stack.push(ch1);
                }else{
        
                    //碰到右括号,但栈是空的没有匹配到左括号
                    if(stack.empty()) {
        
                        return false;
                    }
                    
                    char ch2 = stack.peek();
                    if(ch2=='(' && ch1==')' || 
                       ch2=='[' && ch1==']'|| ch2=='{' && ch1 == '}') {
        
                        stack.pop();
                    }else {
        //碰到右边括号,但左括号不匹配
                       return false; 
                    }
                }
            }
            //判断字符串遍历完了,但栈没空
            return stack.empty();
        }
    }

### 提交结果： ###

![img][img 1]

## 2. 逆波兰表达式(lc150) ##

### 题目描述: ###

根据 逆波兰表示法，求表达式的值。

有效的算符包括 +、-、\*、/ 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。

注意 两个整数之间的除法只保留整数部分。

可以保证给定的逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。

**示例 1**：

输入：tokens = \[“2”,“1”,“+”,“3”,“\*”\]

输出：9

解释：该算式转化为常见的中缀算术表达式为：((2 + 1) \* 3) = 9

**示例 2**：

输入：tokens = \[“4”,“13”,“5”,“/”,“+”\]

输出：6

解释：该算式转化为常见的中缀算术表达式为：(4 + (13 / 5)) = 6

**示例 3**：

输入：tokens = \[“10”,“6”,“9”,“3”,“+”,“-11”,“*“,”/“,”*”,“17”,“+”,“5”,“+”\]

输出：22

解释：该算式转化为常见的中缀算术表达式为：

((10 \* (6 / ((9 + 3) \* -11))) + 17) + 5

= ((10 \* (6 / (12 \* -11))) + 17) + 5

= ((10 \* (6 / -132)) + 17) + 5

= ((10 \* 0) + 17) + 5

= (0 + 17) + 5

= 17 + 5

= 22

**提示**：

1 <= tokens.length <= 104

tokens\[i\] 是一个算符（“+”、“-”、“\*” 或 “/”），或是在范围 \[-200, 200\] 内的一个整数

**逆波兰表达式**：

逆波兰表达式是一种后缀表达式，所谓后缀就是指算符写在后面。

*  平常使用的算式则是一种中缀表达式，如 ( 1 + 2 ) \* ( 3 + 4 ) 。
 *  该算式的逆波兰表达式写法为 ( ( 1 2 + ) ( 3 4 + ) \* ) 。

逆波兰表达式主要有以下两个优点：

*  去掉括号后表达式无歧义，上式即便写成 1 2 + 3 4 + \* 也可以依据次序计算出正确结果。
 *  适合用栈操作运算：遇到数字则入栈；遇到算符则取出栈顶两个数字进行计算，并将结果压入栈中

**来源**：力扣（LeetCode）

**链接**：[https://leetcode.cn/problems/evaluate-reverse-polish-notation][https_leetcode.cn_problems_evaluate-reverse-polish-notation]

### 解题思路： ###

在做这道题之前需要先明白逆波兰表达式是什么, 逆波兰表达式其实就是后缀表达式, 与这个相关的还有前缀和中缀表达式, 至于中缀如何转前缀和后缀这里就不介绍了, 如果需要的话在下面链接中的博客有介绍: [链接][Link 1]

![img][img 2]

明白中缀和后缀表达式之间的转化后, 这道题其实也不难想, 只需要利用一个栈去实现, 我们可以去创建一个栈, 然后去遍历字符串, 去实现**碰到数字就入栈**, **碰到是操作符就将栈中两个数字出栈**, 然后, **第一个出栈的数字作为右操作数, 第二个出栈的元素作为左操作数**, 然后**再将计算结果入栈**, 循环上述过程, 直至将字符串遍历完, 最终栈中只剩一个元素便是最终的计算结果;

**要注意的是是字符串中的数字是数字字符, 再入栈前需要先将数字字符转化为对应的数字再进行入栈.**

### 代码实现： ###

class Solution {
        
        public int evalRPN(String[] tokens) {
        
            Stack<Integer> stack = new Stack();
            //遍历token数组,判断类类型
            for(String s:tokens) {
        
                //是数字就压栈
                if(!isOperations(s)) {
        
                    stack.push(Integer.parseInt(s));
                }else {
        
                    //碰到操作符从栈中弹出两个数字
                    //运算后将结果再压栈
                    int num2 = stack.pop();
                    int num1 = stack.pop();
                    switch(s) {
        
                        case "+":
                            stack.push(num1+num2);
                            break;
                        case "-":
                            stack.push(num1-num2);
                            break;
                        case "*":
                            stack.push(num1*num2);
                            break;
                        case "/":
                            stack.push(num1/num2);
                            break;  
                    } 
                }
            }
            return stack.peek();
        }
        public boolean isOperations(String s) {
        
            if(s.equals("+") || s.equals("-") || s.equals("*") || s.equals("/")) {
        
                return true;
            }
            return false;
        }
    }

### 提交结果： ###

![img][img 3]

## 3. 栈的压入、弹出序列(牛客JZ31) ##

### 题目描述: ###

**描述**  
输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。

1.  0<=pushV.length == popV.length <=1000
2.  \-1000<=pushV\[i\]<=1000
3.  pushV 的所有数字均不相同

**示例1**  
输入：\[1,2,3,4,5\],\[4,5,3,2,1\]  
返回值：true  
说明：可以通过push(1)=>push(2)=>push(3)=>push(4)=>pop()=>push(5)=>pop()=>pop()=>pop()=>pop()这样的顺序得到\[4,5,3,2,1\]这个序列，返回true  
**示例2**  
输入：\[1,2,3,4,5\],\[4,3,5,1,2\]  
返回值：false  
说明：由于是\[1,2,3,4,5\]的压入顺序，\[4,3,5,1,2\]的弹出顺序，要求4，3，5必须在1，2前压入，且1，2不能弹出，但是这样压入的顺序，1又不能在2之前弹出，所以无法形成的，返回false

**链接**：[点这里][Link 2]  
**来源**：牛客网

### 解题思路： ###

既然这里给出了入栈和出栈的序列, 那么们就可以去模拟这个过程, 我们可以创建一个辅助栈, 然后去对入栈序列进行遍历, 每次遍历将里面的元素入栈, 再去按顺序将出栈序列数组中的元素与栈顶元素比较, 如果相等就出栈, 并比较下一个出栈数组元素与下一次栈顶元素是否相等，相等就出栈, 以此类推直到不相等再进行下一次入栈序列的遍历; 最终遍历结束后, 如果最终栈为空栈，则出栈序列是可能的, 否则就是不可能的。

举例：

入栈1,2,3,4,5

出栈4,5,3,2,1

首先1入辅助栈，此时栈顶1≠4，继续入栈2

此时栈顶2≠4，继续入栈3

此时栈顶3≠4，继续入栈4

此时栈顶4＝4，出栈4，出栈序列向后一位，此时为5，,辅助栈里面是1,2,3

此时栈顶3≠5，继续入栈5

此时栈顶5=5，出栈5,出栈序列向后一位，此时为3，,辅助栈里面是1,2,3

此时栈顶3=3, 出栈3,出栈序列向后一位，此时为2，,辅助栈里面是1,2

此时栈顶2=2, 出栈2,出栈序列向后一位，此时为1，,辅助栈里面是1

此时栈顶1=1, 出栈1,出栈序列向后一位, 此时出栈序列遍历结束, 辅助栈为空栈

### 代码实现： ###

import java.util.*;
    
    public class Solution {
        
        public boolean IsPopOrder(int [] pushA,int [] popA) {
        
          Stack<Integer> stack = new Stack();
          int j = 0;//用来遍历popA数组
          for(int i = 0; i < pushA.length; i++) {
        
              stack.push(pushA[i]);
              while(j<popA.length && !stack.empty() && stack.peek().equals(popA[j])) {
        
                  stack.pop();
                  j++;
              }
          }
          return stack.empty();
        }
    }

### 提交结果： ###

![img][img 4]

## 4.最小栈(lc155) ##

### 题目描述: ###

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

*  MinStack() 初始化堆栈对象。
 *  void push(int val) 将元素val推入堆栈。
 *  void pop() 删除堆栈顶部的元素。
 *  int top() 获取堆栈顶部的元素。
 *  int getMin() 获取堆栈中的最小元素。

**示例 1**:

输入：

\[“MinStack”,“push”,“push”,“push”,“getMin”,“pop”,“top”,“getMin”\]

\[\[\],\[-2\],\[0\],\[-3\],\[\],\[\],\[\],\[\]\]

输出：

\[null,null,null,null,-3,null,0,-2\]

解释：

MinStack minStack = new MinStack();

minStack.push(-2);

minStack.push(0);

minStack.push(-3);

minStack.getMin(); --> 返回 -3.

minStack.pop();

minStack.top(); --> 返回 0.

minStack.getMin(); --> 返回 -2.

**提示**：

\-231 <= val <= 231 - 1

pop、top 和 getMin 操作总是在 非空栈 上调用

push, pop, top, and getMin最多被调用 3 \* 104 次

**来源**：力扣（LeetCode）

**链接**：[https://leetcode.cn/problems/min-stack][https_leetcode.cn_problems_min-stack]

### 解题思路： ###

这道题的意思是让我们实现一个栈, 要求在时间复杂度为O(1)的情况下获取到最小值;

这里我们可以使用两个栈来实现, 创建一个主站和一个辅助栈, 每次入栈将都将元素入到主栈中, 辅助栈中存放实时的最小值, 那么如何实现在辅助栈中存放实时的最小值? 很简单, 如果是第一次入栈, 那么此时的辅助栈是空栈, 直接将第一个元素在两个栈都入栈, 之后的每次的入栈, 如果待入栈元素的值小于或等于辅助栈的栈顶元素, 那么两个栈都入栈, 否则只入主栈(主栈不论什么情况，均入栈);

代码演示主栈为stack，辅助栈为minStack;

### 代码实现： ###

class MinStack {
        
        Stack<Integer> stack;
        Stack<Integer> minStack;
    
        public MinStack() {
        
            stack = new Stack<>();
            minStack = new Stack<>();
        }
        
        public void push(int val) {
        
            stack.push(val);
            if(minStack.empty()) {
        
                minStack.push(val);
            }else {
        
                if(val <= minStack.peek()) {
        
                    minStack.push(val);
                }
            }
        }
        
        public void pop() {
        
            if(!stack.empty()) {
        
                int x = stack.pop();
                if(x == minStack.peek()) {
        
                    minStack.pop();
                }
            }
        }
        
        public int top() {
        
            if(stack.empty()) {
        
                return -1;
            }
            return stack.peek();
        }
        
        public int getMin() {
        
            if(minStack.empty()) {
        
                return -1;
            }
            return minStack.peek();
        }
    }

### 提交结果： ###

![img][img 5]

[078b66f87e3c4e309d7f34d79c5776c4.gif_pic_center]: https://img-blog.csdnimg.cn/078b66f87e3c4e309d7f34d79c5776c4.gif#pic_center
[_XIN-XIANG]: https://blog.csdn.net/Trong_?spm=1000.2115.3001.5343
[LeetCode]: https://blog.csdn.net/trong_/category_11990219.html?spm=1001.2014.3001.5482
[https_leetcode.cn_problems_valid-parentheses]: https://leetcode.cn/problems/valid-parentheses
[img]: https://img-blog.csdnimg.cn/img_convert/48c69ba1c87470fe6cea14740c9dd209.png
[img 1]: https://img-blog.csdnimg.cn/img_convert/bd24a467495456d46bee665c420cfb00.png
[https_leetcode.cn_problems_evaluate-reverse-polish-notation]: https://leetcode.cn/problems/evaluate-reverse-polish-notation
[Link 1]: https://blog.csdn.net/Trong_/article/details/127186362?spm=1001.2014.3001.5502
[img 2]: https://img-blog.csdnimg.cn/img_convert/9a18f166af173b3126b691eae84daffa.png
[img 3]: https://img-blog.csdnimg.cn/img_convert/3a1008a12fc9de2ebe2368019f3b96bb.png
[Link 2]: https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking
[img 4]: https://img-blog.csdnimg.cn/img_convert/62db7138043ddfa6caaa293d6dec4667.png
[https_leetcode.cn_problems_min-stack]: https://leetcode.cn/problems/min-stack
[img 5]: https://img-blog.csdnimg.cn/img_convert/fe345c707afb6eeff5170e9f6da81b64.png