华为面试题！

写个大家看看呗?

正解!

public class MatchTest {
String getInput() {
Scanner sc = new Scanner(System.in);
String in = sc.next();
return in;
}

boolean isMatch(String s) {
LinkedList<Character> ls = new LinkedList<Character>();
for (int i = 0; s != null && i < s.length(); i++) {
if (s.charAt(i) == '{') {
ls.addFirst('{');
} else if (s.charAt(i) == '}') {
if (!ls.isEmpty())
ls.removeFirst();
else
return false;
}
}
if (ls.isEmpty())
return true;
else
return false;
}

public static void main(String... args) {
MatchTest mt=new MatchTest();
System.out.print(mt.isMatch(mt.getInput()));
}
}

遇"{"压栈，遇"}"出栈

int n = 0;
for each char in string:
    if char is '{'
        n++;
    if char is '}'
        n--;
        if n < 0
            exit('no match')

if n !== 0
    exit('no match')

exit('match')

好像连栈也不需要了……

感觉用数据结构的栈实现比较合适，支持用栈来实现

import java.util.ArrayList;
import java.util.List;

public class Test {

public static boolean isCompile(String exp) {

List<Character> list = new ArrayList<Character>();

boolean b = true;

for (int i = 0; i < exp.length(); i++) {
//将"{" "}" 放入链表数组
char c = exp.charAt(i);
if (c == '{') {
list.add(c);
} else if (c == '}') {
list.add(c);
}
}
if (list.size() % 2 != 0) {
//如果不是成对出现，返回fasle
b = false;
}
for (int i = 0; i < list.size() / 2; i++) {
if (list.get(i) != '{') {
//如果链表数组前半出现的不是"{"返回false
b = false;
break;
} else if (list.get(list.size() - 1 - i) != '}') {
//如果对应该位置的后半出现的不是"}"返回false
b = false;
break;
}
}
return b;
};

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
System.out.println(Test.isCompile("{afdsadsadas{asdsadsa}}"));

}

}
这个应该是没有问题的，请指教！

栈结构，读到{ 压入栈，读到}，从栈中弹出一个第一个元素 如果是{，配对，如果是} ，报错，以此类推，读完，栈中无元素，正确，如果还有{，错误----缺失}

import java.util.Stack;

public class StackTest {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		System.out.println(isMatch("{}"));
		System.out.println(isMatch("{"));
		System.out.println(isMatch("{kljdfj}}fj;fj"));
		System.out.println(isMatch("{}}"));
		System.out.println(isMatch("{{fdsfs}}{}"));
		
	}
	
	public static boolean isMatch(final String str) {
		Stack<Character> stack = new Stack<Character>();
		for (int i=0;i<str.length();i++) {
			if (str.charAt(i) == '{') {
				stack.push(str.charAt(i));
				continue;
			} 
			if (str.charAt(i) == '}'  && stack.size() != 0) {
				stack.pop();
				//System.out.println("{ }");
				continue;
			}
			if (str.charAt(i) == '}'  && stack.size() == 0)
				return false;
		}
		if (stack.size() > 0) 
			return false;
		return true;
	}
}

输出结果：
true
false
false
false
true