题目

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。

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

示例

示例 1:

输入: "()"

输出: true示例 2:

输入: "([]){}"

输出: true示例 3:

输入: "(]"

输出: false示例 4:

输入: "([)]"

输出: false示例 5:

输入: "{[]}"

输出: true

第一想法

这段代码是根据示例5想到的，没考虑太多东西，由于是对称的那么我可以将这个字符串拆分为前后两部分，那么就只需要花费N/2的时间进行比较，由中间向两边遍历，定义map作为映射，当遇到两个值不同时判断失败。

当然这么写是不对的，问题就在于，当不为对称时，比较失败，比如示例2.ok,那我们接下来看第二想法

public static boolean validParentheses(String str){    Boolean res = true;    HashMap
    
      map = new HashMap<>(3);    map.put("{","}");    map.put("[","]");    map.put("(",")");    int len = str.length()/2;    int left = len-1;    int right = len;    String[] strings = str.split("");    while (left>-1){        if (!Objects.equals(map.get(strings[left]), strings[right])){            res = false;            break;        }        left--;        right++;    }    return res;}
    

第二想法

对于括号是否合法的问题，想到了大学时学到的编译原理这个课程。那么问题是如何解决第一想法中当不对称时如何匹配符号，并且验证是否为有效括号。

这里与第一想法不同的是，我选择将未成功匹配的符号开始符号（[{(）有顺序的存储起来，直到遇到第一个不是开始符号时，将存储的符号取出，同时要保证先进后出这个问题,这时我们能想到一种数据结构天生就是用做这个的，那就是栈，技能保证顺序同时还能先进后出。

//升级版    public static boolean validParentheses01(String str){        //定义映射        HashMap
    
      map = new HashMap<>(3);        map.put("{","}");        map.put("[","]");        map.put("(",")");        //将括号字符分解为数组        String[] strings = str.split("");        int index = 0;        //构造存储开始符号的栈        Stack
     
       stack = new Stack<>();        String sta;        while (index
     
    

参考优化

该版代码是产考了网上一下代码后进行的优化，这里没有将String进行转化数组，而是使用了String的charAt方法

//最终版    public static boolean validParentheses02(String str){        HashMap
    
      map = new HashMap<>(3);        map.put('{','}');        map.put('[',']');        map.put('(',')');        int index = 0;        Stack
     
       stack = new Stack<>();        Character sta;        while (index
     
    

数据结构

在表示问题的递归结构时，栈数据结构可以派上用场。我们无法真正地从内到外处理这个问题，因为我们对整体结构一无所知。但是，栈可以帮助我们递归地处理这种情况，即从外部到内部。

算法详解（官方解释）

1. 初始化栈 S。2. 一次处理表达式的每个括号。3. 如果遇到开括号，我们只需将其推到栈上即可。这意味着我们将稍后处理它，让我们简单地转到前面的 子表达式。4. 如果我们遇到一个闭括号，那么我们检查栈顶的元素。如果栈顶的元素是一个 相同类型的 左括号，那么我们将它从栈中弹出并继续处理。否则，这意味着表达式无效。5. 如果到最后我们剩下的栈中仍然有元素，那么这意味着表达式无效。