首页 > 试题广场 >

括号配对问题

[编程题]括号配对问题
  • 热度指数:10569 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
\hspace{15pt}给定一个字符串 S,请检查字符串中仅由括号字符 \texttt{`['}\texttt{`]'}\texttt{`('}\texttt{`)'} 组成的子序列是否构成合法括号序列。合法括号序列的定义如下:

\hspace{23pt}\bullet\,空序列是合法括号序列;

\hspace{23pt}\bullet\,如果 A 是合法括号序列,则 `(A)` 和 `[A]` 都是合法括号序列;

\hspace{23pt}\bullet\,如果 AB 都是合法括号序列,则它们的拼接 AB 也是合法括号序列。

\hspace{15pt}字符串 S 可能包含其他字符,但只需考虑括号部分,忽略其他字符。

输入描述:
\hspace{15pt}在一行中输入一个字符串 S,长度 1 \leqq |S| \leqq 10^4,由可见字符组成。


输出描述:
\hspace{15pt}如果字符串 S 中的括号部分能构成合法括号序列,则输出 \texttt{true};否则输出 \texttt{false}
示例1

输入

abcd(])[efg

输出

false

说明

提取括号 `(`、`)`、`[`、`]` 后为 `(])[`,不是合法括号序列。
示例2

输入

a[x(y)z]

输出

true

说明

提取括号后为 `[()]`,是合法括号序列。
import java.util.Scanner;
import java.util.Stack;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.next();
        System.out.print(bracketMatch(str));
    }

    public static boolean bracketMatch(String str) {
        Stack<Character> stack = new Stack<>();

        for (int i = 0; i < str.length(); i++) {
            char c = str.charAt(i);

            // 如果是左括号,入栈
            if (c == '(' || c == '[') {
                stack.push(c);
            }
            // 如果是右括号
            else if (c == ')' || c == ']') {
                // 栈为空,没有匹配的左括号
                if (stack.isEmpty()) {
                    return false;
                }

                // 弹出栈顶元素并检查是否匹配
                char top = stack.pop();
                if ((c == ')' && top != '(') || (c == ']' && top != '[')) {
                    return false;
                }
            }
        }

        // 所有括号处理完毕后,栈必须为空才是完全匹配
        return stack.isEmpty();
    }
}

发表于 2025-07-31 16:43:06 回复(0)
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        Stack<Character> stack = new Stack<>();
        for (int i=0;i<str.length();i++){
            char c = str.charAt(i);
            if (c == '(' || c == '[')
                stack.push(c);
            else if (c == ')'){
                if (stack.isEmpty() || stack.pop() != '(') {
                    System.out.println(false);
                    return;
                }
            }else if (c == ']'){
                if (stack.isEmpty() || stack.pop() != '[') {
                    System.out.println(false);
                    return;
                }
            }
        }
        if (stack.isEmpty())
            System.out.println(true);
        else
            System.out.println(false);
    }
}

发表于 2019-08-14 15:27:33 回复(0)