1.题目描述
小洛看着一堆只包含’(‘和’)‘的括号序列犯愁了，小洛想知道这串序列里最长正确匹配的序列长度是多少，你能帮帮小洛吗？
输入
输入一个只包含’(‘与’)'的字符串，字符串长度n满足0＜n≤50000
输出
输出一个数表示子串长度
数据范围
对于100%的数据，0＜n≤50000
输入样例
((((())(
输出样例
4
2.问题分析
说到括号匹配问题，我们很容易想到利用栈来解决，但是直接使用栈来进行处理的话，你会发现，无法记录在入栈出栈过程中匹配的长度。因此，我们对栈进行优化，对于栈中存储的每个元素我们都把它当作一个结点，包含data（左括号或者右括号），以及标号值，用index表示。
对于一个序列"( ( ( ) ) ) ) )",首先我们将括号序列依次进行标号，分别为12345678我们让左括号直接入栈，遇到右括号则观察栈中栈顶元素是否为左括号，若是，则出栈；反之，则入栈。
反复进行入栈和出栈操作后，栈中只剩下标号为7、8的两个右括号，则最大匹配长度为7 - 0 - 1 = 6；
我们再来看一个序列"()()",标号分别为1234，进行入栈出栈操作后，最终栈中元素为0，此时最大匹配长度则为字符串的长度，即为4 - 0 = 4。
3.算法分析
对于执行后的栈，我们大致可以分为如下的三种情况：
栈为空：此时最大匹配长度为字符串的长度；
栈底为" ) "：此时隐藏一种匹配长度为栈底标号 - 0 - 1；
栈底为" ( ": 只需要比较任意相邻两个栈中元素标号的差，匹配长度为end - start - 1。
以题目的测试样例为例，输入字符串((((())(，最终剩余在栈中的为标号为1238的左括号，此时最大匹配长度为8 - 3 -1 = 4。
4.实现代码
这里简单对以上讨论的三种情况进行实现，详细可见注释内容。
import java.util.Scanner; import java.util.Stack; // 结点类，用于入栈元素的标号 class Node{ char data;// 存储括号值 int index;// 用于标号 public Node(char data, int index){ this.data = data; this.index = index; } } public class test03 { public static void main(String[] args) { Stack<Node> stack = new Stack<>(); // 入栈的每个元素都是带有标号的左括号，而匹配的长度则为两个相邻的左括号标号的差值-1 Scanner in = new Scanner(System.in); String s = in.next(); char[] strings = s.toCharArray(); boolean flag = false; int temp = 0; // 临时储存 // 遍历括号字符串 int i; // 这里把i单独声明是为了扩大作用域便于end使用 for ( i = 0 ; i < strings.length; i++) { // 遇到左括号入栈,栈中的标号以1为起点 if(strings[i] == '('){ stack.push(new Node(strings[i], i+1)); } // 遇到右括号看栈内是否匹配 if(strings[i] == ')'){ if(stack.empty()){ // 处理)))这种情况 flag = true; // 说明栈是以右括号为栈底 temp = i+1; stack.push(new Node(strings[i], i+1)); // 防止栈下溢 }else{ // 匹配则出栈,不匹配则入栈 if(stack.peek().data == '('){ stack.pop(); }else{ stack.push(new Node(strings[i], i+1)); } } } } // 计算匹配长度 int start = 0, length = 0, end = i+1; // 括号完全匹配，即栈中元素为0，则长度为字符串长度 if(stack.empty()) length = end - start - 1; while (!stack.empty()){ // 栈中以右括号为栈底元素,需要记录一次栈底元素标号与0的差值 if(flag){ length = Math.max(temp - start -1, length); } // 栈中以左括号为栈底元素,只需要比较标号的差值 start = stack.pop().index; //System.out.println("start = " + start); length = Math.max(end - start - 1, length); // 以start为新的end end = start; } // 输出结果 System.out.println(length); in.close(); } }
5.实现结果
输入((((())(测试1
输入()()测试2
输入)))))测试3
6.代码优化
从上面的实现中发现，分为三种情况即单独对栈空的情况进行计算、使用了flag变量来判断栈底是否为右括号、单独对栈底为左括号的情况进行运算。虽然逻辑上没有问题，但是这样不仅多声明了变量，还使代码显得异常复杂。
那么有没有办法可以简化计算呢？
我们发现，只要先将一个标号为0的无关量入栈，这样无论何种情况，在进行最后一步“计算最大匹配长度”时，栈都不会为空，这样就不需要对栈空的情形进行单独讨论；不仅如此，我们存储的0无关量也可以解决右括号为栈底的情况，可以把无关量想成左括号，进行一般情况下的栈元素的标号差操作，即可求出匹配长度。
6.1 具体代码优化实现
import java.util.Scanner; import java.util.Stack; // 结点类，用于入栈元素的标号 class Node{ char data;// 存储括号值 int index;// 用于标号 public Node(char data, int index){ this.data = data; this.index = index; } } public class test03 { public static void main(String[] args) { Stack<Node> stack = new Stack<>(); // 入栈的每个元素都是带有标号的左括号，而匹配的长度则为两个相邻的左括号标号的差值-1 Scanner in = new Scanner(System.in); String s = in.next(); char[] strings = s.toCharArray(); stack.push(new Node('0', 0));// 标号0位置存储一个无关量，便于计算 // 遍历括号字符串 int i; // 这里把i单独声明是为了扩大作用域便于end使用 for ( i = 0 ; i < strings.length; i++) { // 遇到左括号入栈,栈中的标号以1为起点 if(strings[i] == '('){ stack.push(new Node(strings[i], i+1)); } // 遇到右括号看栈内是否匹配 if(strings[i] == ')'){ if(stack.empty()){ stack.push(new Node(strings[i], i+1)); // 防止栈下溢 }else{ // 匹配则出栈,不匹配则入栈 if(stack.peek().data == '('){ stack.pop(); }else{ stack.push(new Node(strings[i], i+1)); } } } } // 计算匹配长度 int start = 0, length = 0, end = i+1; while (!stack.empty()){ start = stack.pop().index; //System.out.println("start = " + start); length = Math.max(end - start - 1, length); // 以start为新的end end = start; } // 输出结果 System.out.println(length); in.close(); } }
