Java - 高效的括号匹配方法对输入进行分组

Question

编辑:我应该提到该程序必须严格非递归。

我正在尝试创建一种方法来将组分配给匹配的括号。例如输入:m (a (b c) (d (e (f g h) i) j) k) n 输出将是:

Inputted text: m (a (b c) (d (e (f g h) i) j) k) n
group 0 =  m (a (b c) (d (e (f g h) i) j) k) n
group 1 = (a (b c) (d (e (f g h) i) j) k)
group 2 = (b c)
group 3 = (d (e (f g h) i) j)
group 4 = (e (f g h) i)
group 5 = (f g h)

我创建了以下方法，但如您所见，它将第一个遇到的左括号与第一个遇到的右括号匹配，而不是每个左括号都表示新组的开始。如果不重新开始，我想不出一种简单的方法来复制上述输出。有什么想法吗？

    public class Matching {

    public static String[] group(String s){
        Stack<Integer> indexStack = new Stack<Integer>();
        String[] groupArray = new String[15];
        int count = 0;

        for(int i = 0; i != s.length(); i++){
            /*
             * If character in index position is a left parenthesis, push the current
             * index onto stack. If a right parenthesis is encountered, pop the stack and
             * store its index temporarily. Use index and current position at right
             * parenthesis to create a substring.   
             */
            if(s.charAt(i) == '(')
                indexStack.push(i);
            else if( s.charAt(i) == ')' ){

                try{
                    int index = indexStack.pop();
                    groupArray[count++] = s.substring(index, i + 1);
                }
                catch(Exception e){ //An exception results from popping empty stack 
                    System.out.println("Unbalanced in input " + s +  
                            " at index " + i + "\n");

                    return null; //return null to caller
                }
            }
        }
        //If stack not empty at the end of loop, return null to caller
        if(!indexStack.isEmpty()){ 
                System.out.println("Unbalanced in input " + s + 
                        " at index " + indexStack.pop() + "\n");

                return null; 
        }
        //initial input that starts with a character other than ( needed to be added.
        if (s.charAt(0) != '(')
            groupArray[count++] = s;

        return groupArray;
    }
}

Answer 1

不需要使用递归。如果输出元素的顺序不受限制，则尝试使用它(请注意，输入中的所有字符都有一次迭代):

private List<String> findSubSets(final String expresion) {
    final List<String> result = new ArrayList<>();
    final Stack<StringBuilder> stack = new Stack<>();
    StringBuilder builder = new StringBuilder();
    for (char c : expresion.toCharArray()) {
        if (c == '(') {
            stack.push(builder);
            builder = new StringBuilder();
        }
        builder.append(c);
        if (c == ')') {
            final String value = builder.toString();
            final StringBuilder parent = stack.pop();
            parent.append(value);
            result.add(value);
            builder = parent;
        }
    }
    if (!expresion.startsWith("(")) {
        result.add(builder.toString());
    }
    return result;
}

输出

Group 0 = (b c)
Group 1 = (f g h)
Group 2 = (e (f g h) i)
Group 3 = (d (e (f g h) i) j)
Group 4 = (a (b c) (d (e (f g h) i) j) k)
Group 5 = m (a (b c) (d (e (f g h) i) j) k) n

附言算法假定输入格式正确 - ( 和 ) 的不均匀计数可能会导致 EmptyStackException。