博客

差值比较

利用’(’ – ‘)’ 的值是-1，’[’ – ‘]’、’{’ – ‘}’等的值是-2来判断是否匹配

思路：遍历字符串，若栈为空，或栈顶元素与遍历到的当前元素不匹配则入栈，匹配则弹栈（弹栈后遍历的当前元素不入栈）。若遍历结束后栈为空，则说明括号都匹配上了。

private static void solution01() {
        String str = "{()[[()]]<>{}()<>}()";
        ArrayStack<Character> stack = new ArrayStack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (stack.isEmpty()) {
                stack.push(c);
            } else {
                char top = stack.peek();
                if (top - c == -1 || top - c == -2) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
        }
        System.out.println(stack.isEmpty());
    }

利用HashMap

设栈顶为键，遍历到的字符为值，若满足hash匹配则弹栈（弹栈后遍历到的当前元素不入栈），不满足则入栈。

思路：遍历字符串，若栈为空，或栈顶元素与遍历到的当前元素不匹配则入栈，匹配则弹栈（弹栈后遍历的当前元素不入栈）。若遍历结束后栈为空，则说明括号都匹配上了。

private static void solution02() {
        String str = "{()[[()]]<{()>}()";
        HashMap<Character,Character> map = new HashMap<>();
        map.put('[',']');
        map.put('<','>');
        map.put('(',')');
        map.put('{','}');
        ArrayStack<Character> stack = new ArrayStack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (stack.isEmpty()) {
                stack.push(c);
            } else {
                char top = stack.peek();
                if (map.containsKey(top) && c == map.get(top)) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
        }
        System.out.println(stack.isEmpty());
    }

源代码

package p2.线性结构;
//括号匹配是否成对
import java.util.HashMap;

public class matchBracket {
    public static void main(String[] args) {
        solution01();
        solution02();
    }
    private static void solution01() {
        String str = "{()[[()]]<>{}()<>}()";
        ArrayStack<Character> stack = new ArrayStack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (stack.isEmpty()) {
                stack.push(c);
            } else {
                char top = stack.peek();
                if (top - c == -1 || top - c == -2) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
        }
        System.out.println(stack.isEmpty());
    }

    private static void solution02() {
        String str = "{()[[()]]<{()>}()";
        HashMap<Character,Character> map = new HashMap<>();
        map.put('[',']');
        map.put('<','>');
        map.put('(',')');
        map.put('{','}');
        ArrayStack<Character> stack = new ArrayStack<>();
        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);
            if (stack.isEmpty()) {
                stack.push(c);
            } else {
                char top = stack.peek();
                if (map.containsKey(top) && c == map.get(top)) {
                    stack.pop();
                } else {
                    stack.push(c);
                }
            }
        }
        System.out.println(stack.isEmpty());
    }
}