括号匹配问题的总结

括号匹配问题有若干种，这里分析其中一种括号里有数字有字符，然后求的最终结果的问题。
给出两道例题，Leetcode224和Leetcode394。

Leetcode224

题目描述

实现一个基本的计算器来计算一个简单的字符串表达式的值。

字符串表达式可以包含左括号 ( ，右括号 )，加号 + ，减号 -，非负整数和空格  。

示例

输入: "(1+(4+5+2)-3)+(6+8)"
输出: 23

解决方案

class Solution {
    public int calculate(String s) {
        int n = s.length();
        Stack<Integer> st = new Stack<>();
        int sign = 1,res = 0;
        for(int i = 0;i < n;i++){
            char c = s.charAt(i);
            if(Character.isDigit(c)){
                int t = c - '0';
                while(i+1 < n && Character.isDigit(s.charAt(i+1))){
                    t = t*10 + s.charAt(++i) - '0';
                }
                res = sign * t + res;
            }
            else if(c == '-') sign = -1;
            else if(c == '+') sign = 1;
            //遇到左括号用栈保存之前的信息，并将信息重置
            else if(c == '('){
                st.add(res);
                res = 0;
                st.add(sign);
                sign = 1;
            }
             //遇到右括号取出栈中信息，并计算出结果
            else if(c == ')'){
                res = st.pop()*res + st.pop();
            }
        }
        return res;
    }
}

Leetcode394

题目描述

给定一个经过编码的字符串，返回它解码后的字符串。

编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。

你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。

此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。

示例

s = "3[a]2[bc]", 返回 "aaabcbc".
s = "3[a2[c]]", 返回 "accaccacc".
s = "2[abc]3[cd]ef", 返回 "abcabccdcdcdef".

解决方案

class Solution {
    public String decodeString(String s) {
        int n = s.length();
        StringBuilder res = new StringBuilder();
        Stack<StringBuilder> stack = new Stack<>();
        int t = 0;
        for(int i = 0;i < n;i++){
            char c = s.charAt(i);
            if(Character.isDigit(c)){
                t = c - '0';
                while(i+1 < n && Character.isDigit(s.charAt(i+1))){
                    t = t*10 + s.charAt(++i)-'0';
                }
            }
            //保存当前信息
            else if(c == '['){
                StringBuilder sb = new StringBuilder();
                sb.append(t);
                stack.add(sb);
                t = 0;
                stack.add(res);
                res = new StringBuilder();
            }
            //提出信息，得到总结果
            else if(c == ']'){
                StringBuilder tmp = stack.pop();
                int cnt = Integer.valueOf(stack.pop().toString());
                for(int k = 0;k < cnt;k++) tmp.append(res);
                res = tmp;
            }
            else{
                res.append(c);
            }
        }
        return res.toString();
    }
}

总结：核心思路就是在遇到左括号，保存当前信息，然后去算括号中的逻辑，当遇到右括号时候，把之前栈中保存的之前的信息与括号里的信息进行拼接处理即可。