Java 括号匹配算法 - 栈结构实现

本篇文章将探讨使用 Java 实现一个判断括号匹配的算法。给定一个包含花括号 \{\}、中括号 \{\}、小括号 \(\) 的字符串，算法需要判断括号是否正确匹配。例如，\"(\{\}[]\)\" 匹配正确，而 \"(\{\)[]\" 则不匹配。

解决方案

该问题可以使用栈结构来解决。栈是一种后进先出 (LIFO) 的数据结构，非常适合处理括号匹配这类需要根据顺序进行匹配的问题。
**算法流程：**

1. 遍历输入字符串，遇到左括号 (\{\}, \{\}, \(\)) 就将该括号入栈。
2. 遇到右括号 (\}, \}, \)) 时，判断栈顶元素是否与其匹配。
   • 如果匹配，则将栈顶元素出栈。
   • 如果不匹配，则说明括号不匹配，直接返回 false。
3. 遍历完字符串后，如果栈为空，则说明所有括号都匹配成功，返回 true；否则，说明存在未匹配的左括号，返回 false。

Java 代码实现

import java.util.Stack;
import java.util.Scanner;
public class BracketMatching {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
String str = scanner.nextLine();
boolean isMatched = checkBracketMatching(str);
if (isMatched) {
System.out.println("括号匹配正确");
} else {
System.out.println("括号不匹配");
}
}
public static boolean checkBracketMatching(String str) {
    Stack<Character> stack = new Stack<>();
    for (int i = 0; i < str.length(); i++) {
        char ch = str.charAt(i);
        if (ch == '{' || ch == '[' || ch == '(') {
            stack.push(ch);
        } else if (ch == '}' || ch == ']' || ch == ')') {
            if (stack.isEmpty()) {
                return false;
            }
            char top = stack.pop();
            if ((ch == '}' && top != '{') || (ch == ']' && top != '[') || (ch == ')' && top != '(')) {
                return false;
            }
        }
    }
    return stack.isEmpty();
}

}

总结

通过使用栈结构，我们成功地实现了判断括号匹配的算法。该算法清晰易懂，并且可以扩展到其他类型的括号匹配问题。希望本篇文章能够帮助您理解和应用该算法。