データ構造【スタック】(九):スタックを使用して括弧が一致するかどうかを検査する
2110 ワード
問題の説明
1つ以上のカッコを含む文字列式を与えます.スタックを使用して、文字列式のカッコがバランスしているかどうかを確認する必要があります.
考え方を解く.
文字列内の各文字を巡回する場合:
1)左かっこが現れるとスタックに入る
2)右かっこが表示されると、まずスタックが空であるかどうかをチェックし、空でない場合はスタックトップ要素と一致しているかどうかを判断し、一致している場合はスタックトップ要素をポップアップする.
3)最後にスタックが空であれば、マッチングが成功したことを示す.一致しない場合は、一致しません.
コード実装
コード最適化
1つ以上のカッコを含む文字列式を与えます.スタックを使用して、文字列式のカッコがバランスしているかどうかを確認する必要があります.
考え方を解く.
文字列内の各文字を巡回する場合:
1)左かっこが現れるとスタックに入る
2)右かっこが表示されると、まずスタックが空であるかどうかをチェックし、空でない場合はスタックトップ要素と一致しているかどうかを判断し、一致している場合はスタックトップ要素をポップアップする.
3)最後にスタックが空であれば、マッチングが成功したことを示す.一致しない場合は、一致しません.
コード実装
/**
* @param s
* @return ,true
*/
private static boolean isBalanced1(String s) {
Stack bracketsStack = new Stack<>();
char[] text = s.toCharArray();
for (char x : text) {
switch (x) {
case '{':
case '':
if (bracketsStack.peek() == '
コード最適化
//
private final static HashMap BRACKET_MAP = Maps.newHashMap();
//
private final static Set BRACKET_KEY_SET = Sets.newHashSet();
//
static {
BRACKET_MAP.put('[', ']');
BRACKET_MAP.put('{', '}');
BRACKET_MAP.put('(', ')');
BRACKET_MAP.put('');
BRACKET_KEY_SET.addAll(BRACKET_MAP.keySet());
}
/**
*
*
* @param str
* @return boolean
* @author lkf
* @date 2019/3/20 10:00
*/
private static boolean isBalanced2(String str) {
Stack stack = new Stack<>();
char[] chars = str.toCharArray();
for (char c : chars) {
if (BRACKET_KEY_SET.contains(c)) {
stack.push(c);
}
if (!stack.isEmpty() && BRACKET_MAP.get(stack.peek()) == c) {
stack.pop();
}
}
return stack.isEmpty();
}
public static void main(String args[]) {
String s = "({[9*9]})";
if (isBalanced2(s)) {
System.out.println(s + " ");
} else {
System.out.println(s + " ");
}
}