代码随想录算法训练营第十一天｜20-1047-150

今天的主要内容是栈的应用:

LeetCode 20.有效的括号

这道题算是栈的经典应用了，栈这种数据结构的核心在一它能够提供前序元素的信息

给定一串字符串包含’(‘, ‘)’, ‘[‘, ‘]’, ‘{‘, ‘}’, 判断其括号是否匹配，整体是否有效

一个易见的思路是使用栈，将所有左侧符号都存起来，在遇到右侧符号时将目前栈顶的元素弹出，如果能匹配上则继续，如果匹配不上则返回false；如果遍历完整个字符串栈为空，则说明为有效的括号。

class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < s.length(); i++) {
            char c1 = s.charAt(i);
            // if this char is left side, push it into stack
            if (c1 == '(' || c1 == '[' || c1 == '{') {
                stack.push(c1);
            }else {

                // if stack is empty and a right side char comes
                // return false
                if (stack.isEmpty()) {
                    return false;
                }

                // else let's check if there is a pair
                char c2 = stack.pop();
                if ( c1 == ')' && c2 == '(' ||
                     c1 == ']' && c2 == '[' ||
                     c1 == '}' && c2 == '{') {
                        continue;
                     }else {
                        return false;
                     }
            }
        }
        
        // if after checking, there is no chars left in the stack
        // it means that they are all pairs
        return stack.isEmpty();

    }
}

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

class Solution {
    public String removeDuplicates(String s) {

        char[] chars = s.toCharArray();
        Stack<Character> stack = new Stack<>();
        
      	// full scan the whole string
        for (char c : chars) {
          	// if stack is not empty, pop the top element
          	// compare if it is the same with the pointed one
          	// if not push them back
            if (!stack.empty()) {
                char c2 = stack.pop();
                if (c2 != c){
                    stack.push(c2);
                    stack.push(c);
                }
            }else {
                stack.push(c);
            }
        }
				
      	// pop the left elements
        if (!stack.isEmpty()){
            int size = stack.size();
            char[] ans = new char[size];
            while (size > 0) {
                ans[--size] = stack.pop();
            }

            return String.valueOf(ans);
        }else {
            return "";
        }
    }
}

LeetCode 150.逆波兰表达式

class Solution {
    public int evalRPN(String[] tokens) {

        Stack<String> stack = new Stack<>();
        String s1, s2;
        int temp = 0;;

        for (String s : tokens) {

            switch (s) {
                case "+" :
                    s1 = stack.pop();
                    s2 = stack.pop();
                    temp = Integer.valueOf(s2) + Integer.valueOf(s1);
                    stack.push(String.valueOf(temp));
                    break;
                case "-" :
                    s1 = stack.pop();
                    s2 = stack.pop();
                    temp = Integer.valueOf(s2) - Integer.valueOf(s1);
                    stack.push(String.valueOf(temp));
                    break;
                case "*" :
                    s1 = stack.pop();
                    s2 = stack.pop();
                    temp = Integer.valueOf(s2) * Integer.valueOf(s1);
                    stack.push(String.valueOf(temp));
                    break;
                case "/" :
                    s1 = stack.pop();
                    s2 = stack.pop();
                    temp = Integer.valueOf(s2) / Integer.valueOf(s1);
                    stack.push(String.valueOf(temp));
                    break;
                default:
                stack.push(s);
            }

        }

        return Integer.valueOf(stack.pop());
    }
}

了解了后缀表达式的规则后就会发现，这是一种很适合使用栈来进行计算的表达式，从左到右遍历字符串，遇到数字就压入栈，遇到操作符就弹出两个数字计算，然后将结果压入栈，最后留在栈中的数字即为计算结果。