首页 > 试题广场 >

括号匹配

[编程题]括号匹配

热度指数：1991 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个只包含括号的字符串，判断字符串是否有效。其中，括号种类包含： ‘(’，’)’，’{’，’}’，’[’，’]'。有效字符串需满足：1) 左括号必须用相同类型的右括号闭合；2）左括号必须以正确的顺序闭合。注意空字符串可被认为是有效字符串

示例1

输入

"{[]}"

输出

true

示例2

输入

"([)]"

输出

false

示例3

输入

"([]"

输出

false

算法知识视频讲解

Java

old李

import java.util.Scanner;
import java.util.Stack;
public class 有效的括号 {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        while (scanner.hasNextLine()) {
            String str = scanner.nextLine();
            boolean valid = isValid(str);
            System.out.println(valid);
        }
        scanner.close();
    }

    private static boolean isValid(String str) {
        if(str == null) {
            return false;
        }

        Stack<Character> stack = new Stack<>();
        for(char ch: str.toCharArray()) {
            if(!valid(ch)) {
                return false;
            }
            if(isLeft(ch) || stack.isEmpty()) {
                stack.push(ch);
            } else {
                Character left = stack.pop();
                if(!isValid(left, ch)) {
                    stack.push(left);
                    stack.push(ch);
                }
            }
        }

        return stack.isEmpty();
    }

    private static boolean isValid(char left, char right) {
        return (left == '(' && right == ')')
                || (left == '[' && right == ']')
                || (left == '{' && right == '}');
    }
    private static boolean isLeft(char ch) {
        return ch == '(' || ch == '[' || ch == '{';
    }
    private static boolean valid(char ch) {
        return ch == '(' || ch == ')'
               || ch == '[' || ch == ']'
               || ch == '{' || ch == '}';
    }
}

发表于 2021-05-08 00:02:58 回复(1)