括号匹配那个小题真不简单……
这是一个括号匹配的小问题引发的思考，很多题目很简单，很多刚接触编程的人都可以做出来。
但是一道算法题不是解出来就完事了，更多的要去探索不同的解法，分析每种解法的不同之处，尝试找出来最优的那种解法。不如你也来试试看。
先来看看这个小题目，简单的来说就是括号匹配的最基础版本。
Description：
有这样一个数学表达式：((2+3)*(4+5))，判断它的左右括号是否匹配。如果匹配正确输出括号的对数，否则输出-1。
Example ：
Input：((2+3)*(4+5)) Output：3
Tips：
括号匹配这种题，里面需要操作的符号有两种：左括号和右括号，那么我们就可以针对这两个符号操作，其余的数字字符都可以忽略掉。
这里有一些要考虑的特殊情况，比如表达式没有括号的存在，这时候该怎么办呢？
学过栈的同学可以使用栈的操作把这一题给解答了，那么除此以外，不使用栈的情况下，是不是还有其他解法呢？
Solutions:
我们先来看看第一种解法，使用栈操作，只需要一个栈就可以了，此时遇到右括号进栈，遇到左括号则出栈，这时候栈中的右括号少一个，计数变量 +1 操作。最后判断栈是否为空？为空则表示括号匹配，输出计数变量的值，否则输出 -1。
代码实现如下所示：
import java.util.Scanner; import java.util.Stack; /** * 使用栈解法，此处有遗留问题 */ public class Solution01 { public static void main(String[] args) { Scanner in = new Scanner(System.in); String str = in.nextLine(); int count = 0; int len = str.length() - 1; Stack stack = new Stack<String>(); while (len >= 0) { char c = str.charAt(len); if (c == ')') { stack.push(c); } else if (c == '(') { stack.pop(); ++count; } --len; } if (stack.isEmpty()) { System.out.println(count); } else { System.out.println(-1); } } }
你是不是以为这样就结束了？哦不……还有两个问题，假如在出栈的时候，栈为空，这里会抛异常的，这该怎么搞呢？如果( 的数量比 ) 的数量少，那又会怎么样？
那么就接下来分析一下栈解法的时间复杂度和空间复杂度，其中包含一个循环操作，循环的次数跟字符串的长度相同，那么我们使用大O表示法，那么此时的时间复杂度可以记做O(n)。
然后我们分析一下空间复杂度，这里额外使用的空间最多的就是开辟的栈空间，这里的栈空间可大可小，最小的时候可以为空，最大的时候需要空间就是字符串的长度，即为n，平均空间复杂度的分析可以使用我们上次的内容进行分析，忽略系数的情况下，可以记为O(n)
然后我们来看看第二种解法，我们是不是可以把栈替换掉呢？比如使用变量计数，使用两个变量分别记录左右括号的数量，如果最后数量相同则输出统计的数量，否则输出-1。
代码实现如下所示：
import java.util.Scanner; public class Solution02 { public static void main(String[] args) { Scanner in = new Scanner(System.in); String str = in.nextLine(); int i = str.length() - 1; int left = 0; int right = 0; while (i >= 0) { char c = str.charAt(i); if (c == ')') { ++right; } else if (c == '(') { ++left; } --i; } if (left == right) { System.out.println(left); } else { System.out.println(-1); } } }
我们来分析这段代码，同样的循环操作，循环的次数跟字符串的长度相同，那么我们使用大O表示法，这里的时间复杂度也可以记做O(n)。
然后我们分析一下空间复杂度，这里额外使用的空间就是两个计数的变量，这两个变量不会随着字符串规模的增长而需要更多的空间，所以这里的空间复杂度是常量级别的，可以记做O(1)。
你以为这就结束了？不可能的，这还不是最优的，还有一种解法，比较有意思，我只提供一下思路，有兴趣的可以去试试。
首先剔除掉字符串中的非括号字符，然后判断字符串中包含()的数量。匹配一对删除一对，在最后的时候，判断字符串的长度是否为0，是的话就输出数量，不是的话，就是-1咯。
代码实现可以参考下图，有兴趣的建议自己实现一下。
最后来一个问题，那么它的时间复杂度和空间复杂度是多少呢？
