华为面试题！

用java写一个函数判断字符串中"{"与"}"匹配？
提示："{"与"}"必须同时出现，"{"必须在"}"前面，允许嵌套

正则表达式"{+.}+"

用栈， push ,pop 方法应该能实现

跟解析XML 的 “<”和“ >” 一样，可以去看看人家怎么实现解析 XML 的，你可以从中学到解决方案

public class T {
	public static boolean isMatch(String value) {
		int numCount = 0, numMatch = 0;
		for (int i=0; null != value && i<value.length(); i++) {
			char ch = value.charAt(i);
			if (ch == '{') {
				numCount ++;
				numMatch ++;
			} else if (ch == '}') {
				numCount --;
			}
			if (numCount < 0) {
				return false;
			}
		}

		return (numMatch > 0 && numCount == 0);
	}

	public static void main(String args[])  {
		System.out.println( "=========must false=====" );
		System.out.println( isMatch(null) );
		System.out.println( isMatch("") );
		System.out.println( isMatch("ddddd") );
		System.out.println( isMatch("d{dddd") );
		System.out.println( isMatch("dd{}}ddd") );
		System.out.println( isMatch("d}dd{dd") );

		System.out.println( "=========must true=====" );
		System.out.println( isMatch("dd{}ddd") );
		System.out.println( isMatch("ddd{{}d}d") );
		System.out.println( isMatch("d{d{d}d}d") );
	}
}

这不就是传说中push pop 编辑器就是这个原理吧

你写的这个非常有问题：
1.题目要求{和}的数量是相等的，但是你这个做不到这点。
2.你中间的'.'只表示一个字符也就是说括号中间有两个字符就不行。

判断括号的一般思路是用一个栈，碰到{压栈，碰到}就出栈，最后判断栈是否为空。

明显是考数据结构：Stack

1.
XXX{XXX}XXX
2.
AAA{
  BBB{CCC}DDD
  FFF{GGG}LLL
}ZZZ
3.
AAA{
   BBB{
     BBB{CCC}DDD
   }DDD
   FFF{GGG}LLL
}ZZZ

解析:根据xml的解析规范去解析.
考虑Stack和List的数据结构
NodeList的成员为:
data(本身的值);nodeLise(子节点数组)
有点像json和xml样式解析.

明显是考stack这个数据结构

涉及到什么什么匹配的问题，我就想到正则表达式，用这个很方便，下面是个例子：

import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class TestCurlyBraces
{

	private Pattern pattern = Pattern.compile("[^{}]*(\\{[^{}]*(\\{[^{}]*\\}[^{}]*)*\\}[^{}]*)*[^{}]*");

	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		TestCurlyBraces instance = new TestCurlyBraces();
		String input = "asda{asd{fsfsff}sdfab245}2{32}";
		instance.match(input);
	}

	public void match(String input)
	{
		Matcher match = pattern.matcher(input);
		if (match.matches())
			System.out.println(match.group());
		else
			System.out.println("not matched.");
	}

}

不过用正则表达式有个缺点，就是要明确嵌套的层数，因为无法写出匹配任意层的表达式来，这个就是不太通用，用stack就能做的通用。通过压栈({)和出栈(})，结合递归是个很好的解决方案。后续再分享下代码。
用递归把简单的问题搞复杂了，不必用递归，简单的方法就行：

import java.util.LinkedList;

public class CurlyBracesMatcher
{
	private LinkedList<Character> stack = new LinkedList<Character>();

	/**
	 * @param args
	 */
	public static void main(String[] args)
	{
		CurlyBracesMatcher matcher = new CurlyBracesMatcher();
		System.out.println(matcher.matches("{{{{}}a}a}"));
	}

	public boolean matches(String string)
	{
		if (string == null || string.length() == 0 || string.trim().equals(""))
			return true;
		int i = 0;
		while (i < string.length())
		{
			char ch = string.charAt(i);
			if (ch == '{')
			{
				stack.push(ch);
			}
			else if (ch == '}')
			{
				if (stack.isEmpty())
					return false;
				stack.pop();
			}
			i++;
		}

		if (!stack.isEmpty())
			return false;
		return true;
	}
}