1.线性表

有效的括号

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

分析:

class Solution {
      public static HashMap<Character,Character>map = new HashMap<Character,Character>(){{
        put('{','}'); put('[',']'); put('(',')'); put('?','?');
    }};

    public  boolean isValid(String s) {
        Stack<Character> stack=new Stack<Character>(){{add('?');}};
        if(s.length()>0&&!map.containsKey(s.charAt(0)))return  false;
        for(int i=0;i<s.length();i++){
            char ch=s.charAt(i);
            if(map.containsKey(ch))stack.add(ch);
            else if(map.get(stack.pop())!=ch)return  false;
        }
        return stack.size()==1;
    }


}

删除最外层的括号

有效括号字符串为空 ("")、"(" + A + “)” 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""，"()"，"(())()" 和 “(()(()))” 都是有效的括号字符串。
如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。
给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + … + P_k，其中 P_i 是有效括号字符串原语。
对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。

分析:

class Solution {
    public  String removeOuterParentheses(String S) {
        Stack<Character> stack=new Stack<Character>();
        String result="";
        int start=0,end=0;
        boolean flag=false;
        for(int i=0;i< S.length();i++){
            char ch=S.charAt(i);
            if(ch=='('){
                stack.add(ch);
                if(flag==false){
                    start=i;
                    flag=true;
                }
            }else{
                char c=stack.pop();
                if(stack.isEmpty()){
                    flag=false;
                    result+=S.substring(start+1,i);
                }

            }

        }
        return  result;
    }
}