代码随想录第11天 || 有效的括号 删除字符串中的所有相邻重复项 逆波兰表达式求值

有效的括号

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

分析: 遇到左括号就offer(对应的右括号), 遇到右括号与栈顶元素进行比较 如果相等则pollLast(). 不相等或栈为空 return FALSE;

class Solution {
    public boolean isValid(String s) {
        Deque<Character> deque= new LinkedList<>();
        char temp;
        for(int i=0;i<s.length();i++){
            temp = s.charAt(i);
            if(temp=='['){
                deque.offer(']');
            }else if(temp=='{'){
                deque.offer('}');
            }else if(temp=='('){
                deque.offer(')');
            }else if(deque.isEmpty()||deque.peekLast()!=temp){
                return false;
            }else {
                deque.pollLast();
            }
        }
        return deque.isEmpty();
    }
}

删除字符串中的所有相邻重复项

题目: 给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。

在 S 上反复执行重复项删除操作，直到无法继续删除。

在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。

分析: 用栈接收character, 每次接收时, 与peekLast()比较一下, 如果相等则pollLast(), 如果不相等就offer进. 最终用StringBuilder接收 return sb.toString()

class Solution {
    public String removeDuplicates(String s) {
        Deque<Character> queue =  new LinkedList<>();

        for(int i=0;i<s.length();i++){
            if(queue.size()==0||queue.peekLast()!=s.charAt(i)){
            queue.offerLast(s.charAt(i));
            }

            else if (queue.peekLast()==s.charAt(i)){
                queue.pollLast();
            }
        }
        StringBuilder res=new StringBuilder();
        
        while(queue.size()!=0){
            res.append(queue.pollFirst());
        }
        return res.toString();
    }
}

逆波兰表达式求值

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

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

分析: 如果是操作运算符, 从栈中取两个数进行操作, 如果不是操作运算符 就deque.offer(Integer.valueOf(s)); return deque.pop();

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