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

有效的括号(力扣20.)

• 括号匹配时使用栈解决的经典问题

• 题意其实就像我们在写代码的过程中，要求括号的顺序是一样的

• 有左括号，那么在对应位置则必须有右括号

• 第一种情况：已经遍历完了字符串，但是栈不为空，说明有相应的左括号没有右括号来匹配，所以return false

  第二种情况：遍历字符串匹配的过程中，发现栈里没有要匹配的字符。所以return false

  第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号return false

class Solution {
    public boolean isValid(String s) {
        //如果长度不能被2整除，则返回false
        if(s.length() % 2 != 0){
            return false;
        }
        Deque<Character> deque = new LinkedList();
        char temp;
        for(int i = 0;i < s.length();i++){
            temp = s.charAt(i);
            if(temp == '('){
                deque.push(')');
            }else if(temp=='['){
                deque.push(']');
            }else if(temp=='{'){
                deque.push('}');
            }else if(deque.isEmpty()||deque.peek()!=temp){
                return false;
            }else{
                deque.pop();
            }
        }
        return deque.isEmpty();
    }
}

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

• 栈可以用来实现相邻匹配问题
• while(!deque.isEmpty())

class Solution {
    public String removeDuplicates(String s) {
        Deque<Character> deque = new LinkedList();
        char temp;
        for(int i = 0; i < s.length();i++){
            temp = s.charAt(i);
            if(deque.isEmpty()||deque.peek()!=temp){
                deque.push(temp);
                continue;
            }else{
                deque.pop();
                continue;
            }
        }
        StringBuilder result = new StringBuilder();
        if(deque.size() == 0){
            return "";
        }
       while(!deque.isEmpty()){
            result.append(deque.pop());
        }
        return result.reverse().toString();
    }
}

逆波兰表达式求值(力扣150.)

• 后缀表达式，检测是否为符号或数字并进行运算和push

class Solution {
    public int evalRPN(String[] tokens) {
        Deque<Integer> stack = new LinkedList();
        for(String s:tokens){
            if("+".equals(s)){
                stack.push(stack.pop()+stack.pop());
            }else if("-".equals(s)){
                stack.push(-stack.pop()+stack.pop());
            }else if("*".equals(s)){
                stack.push(stack.pop()*stack.pop());
            }else if("/".equals(s)){
                int temp = stack.pop();
                int temp2 = stack.pop();
                stack.push(temp2/temp);
            }else{
                stack.push(Integer.valueOf(s));
            }
        }
        return stack.pop();
    }
}