Leetcode 20 Valid Parentheses

思路：没思路，压根没想到用stack做，看了解答突然想到上学期上数据结构讲到过这个valid expression的问题，好嘛，直接给忘了。直接上代码：

class Solution {
            
    // Hash table that takes care of the mappings.
    private Map<Character,Character> mappings; //declare
    
    // Initialize hash map with mappings. This simply makes the code easier to read.
    public Solution(){ //构造函数
        this.mappings = new HashMap(); //initialize
        this.mappings.put(')','('); // key. value
        this.mappings.put(']','[');
        this.mappings.put('}','{');
    }
    
    public boolean isValid(String s) {
        
        // Initialize a stack to be used in the algorithm.
        Stack<Character> stack = new Stack<>();
        
        int len = s.length();
        for(int i = 0; i < len; i++){
            char c = s.charAt(i);
            // If the current character is a closing bracket.
            if(this.mappings.containsKey(c)){
                
                // Get the top element of the stack. If the stack is empty, set a dummy value of '#'
                char topElement = stack.empty() ? '#' : stack.pop();
                
                // If the mapping for this bracket doesn't match the stack's top element, return false.
                if(topElement != this.mappings.get(c)){return false;}
            }else{
                // If it was an opening bracket, push to the stack.
                stack.push(c);
            }
        }
        // If the stack still contains elements, then it is an invalid expression.
        return stack.isEmpty();
    }
}

这边一个比较关键的的是，要用到map这个数据结构，将正反括号要配对起来，以便为后面判断是否配对而服务。我不太熟悉hashmap这个数据结构，也花了很多时间去了解。

这边还要提一下的是如果一个expression全是一个type的情况，比如只有’(‘和 ‘)’。这种情况就很好做了，只要设置一个counter，遇到’(’，counter++，遇到’)’，counter–。最后如果counter = 0，那么就是valid expression，否则不是。

总结：

1. how to create a stack: Stack stack = new Stack();
2. Character 是char的包装类
3. hashmap.containValue() & hashmap.containKey()
4. HashMap<String, Object> map = new HashMap<String, Object>();
   Map<String, Object> map = new HashMap<String, Object>();在创建map对象时，尽量用第二种方式。这样可以提高代码的重用性，并且在需求发生变化的时候可以避免过多的代码修改。其实我还没有理解地很透彻，在java继承，多肽这块我理解地很不到位，有时间要彻底的搞一遍。关于这两者区别我在*上收藏了一个相关问题，要是哪天突然又不明白了，可以去上面看看。
5. stack中empty和isempty的区别：在使用上是没有任何区别的。但是要清楚的是，empty是stack类中的，isempty是stack继承自vector类的，而vector类中的isempty又是继承自abstractcollection这个实现类的，这个类实现了list interface，而且这个类是抽象类，它只实现了一部分，还有很多抽象方法，为了给继承它的子类们自己去实现自己想要的实现。