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

20. 有效的括号

• 刷题https://leetcode.cn/problems/valid-parentheses/description/
• 文章讲解https://programmercarl.com/0020.%E6%9C%89%E6%95%88%E7%9A%84%E6%8B%AC%E5%8F%B7.html#%E7%AE%97%E6%B3%95%E5%85%AC%E5%BC%80%E8%AF%BE
• 视频讲解https://www.bilibili.com/video/BV1AF411w78g/?spm_id_from=333.788&vd_source=af4853e80f89e28094a5fe1e220d9062

• 题解：

  class Solution {    public boolean isValid(String s) {        Deque deque = new LinkedList();        char ch;        for(int i = 0; i  
   1047. 删除字符串中的所有相邻重复项
   

  • 刷题https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/description/
  • 文章讲解https://programmercarl.com/1047.%E5%88%A0%E9%99%A4%E5%AD%97%E7%AC%A6%E4%B8%B2%E4%B8%AD%E7%9A%84%E6%89%80%E6%9C%89%E7%9B%B8%E9%82%BB%E9%87%8D%E5%A4%8D%E9%A1%B9.html
  • 视频讲解https://www.bilibili.com/video/BV12a411P7mw/?vd_source=af4853e80f89e28094a5fe1e220d9062

  • 题解(直接用字符串作为栈结构使用)：

    class Solution {    public String removeDuplicates(String s) {        //直接用字符串作为栈结构使用，省去了栈转化为字符串的操作        //栈顶为字符串back，栈底为字符串front        StringBuffer result = new StringBuffer();        //top代表result长度        int top = -1;        for(int i = 0; i = 0 && result.charAt(top) == c){                result.deleteCharAt(top);                top--;            }else{                //其他情况（栈为空和栈中字符不相等），直接入栈，top++                result.append(c);                top++;            }        }        return result.toString();    }}

     150. 逆波兰表达式求值

    • 刷题https://leetcode.cn/problems/evaluate-reverse-polish-notation/description/
    • 文章讲解https://programmercarl.com/0150.%E9%80%86%E6%B3%A2%E5%85%B0%E8%A1%A8%E8%BE%BE%E5%BC%8F%E6%B1%82%E5%80%BC.html
    • 视频讲解https://www.bilibili.com/video/BV1kd4y1o7on/?vd_source=af4853e80f89e28094a5fe1e220d9062

    • 题解(逆波兰表达即树的后序遍历，应用于计算机内部的计算)：

      class Solution {    public int evalRPN(String[] tokens) {        //逆波兰表达即树的后序遍历，应用于计算机内部的计算        //无需分析括号优先级，直接从头往后运算即可，适宜应用于计算机        Deque stack = new LinkedList();        for(String s : tokens){            //若遇到符号则处理栈顶的两位数并将处理结果压栈            if("+".equals(s)){                stack.push(stack.pop() + stack.pop());            }else if("-".equals(s)){                //debug点：记得用第二个弹出的数(即第一个压入的数)先处理                stack.push(- stack.pop() + stack.pop());            }else if("*".equals(s)){                stack.push(stack.pop() * stack.pop());            }else if("/".equals(s)){                //debug点:                //第二个弹出的数除以第一个弹出的数                //(即：第一个压入的数除以第二个压入的数)                int temp1 = stack.pop();                int temp2 = stack.pop();                stack.push(temp2 / temp1);                // stack.push(stack.pop() / stack.pop());            }else{                //其他情况，即数字的情况，直接压入栈中                //(转换为整数类型的对象)                stack.push(Integer.valueOf(s));            }        }        //最后留在栈中的即为结果，出栈返回        return stack.pop();    }}