有效的括号

image-20241105150902689

很经典的一道栈题

只要遍历字符串s,是左括号就放入栈,是右括号就弹出,不匹配或者空栈就false

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
char pairs(char a){
    if(a==')') return '(';
    if(a=='}') return '{';
    if(a==']') return '[';
    return 0;
}



bool isValid(char* s) {
    int n=strlen(s);
    if(n%2==1){
        return false;
    }
    int stack[n+1],top=0;
    for(int i=0;i<n;i++){
        char ch=pairs(s[i]);
        if(ch){
            if(top==0||stack[top-1]!=ch){
                return false;
            }
            top--;
        }
        else{
            stack[top++]=s[i];
        }
    }
    return top==0;
}

java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
ublic char pairs(char a){
        return switch (a) {
            case ')' -> '(';
            case ']' -> '[';
            case '}' -> '{';
            default -> 0;
        };
    }

    public boolean isValid(String s) {
        Deque<Character> stack = new ArrayDeque<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c); // 左括号入栈
            } else {
                if (stack.isEmpty() || stack.pop() != pairs(c)) {
                    return false; // 栈为空或括号不匹配
                }
            }
        }
        return stack.isEmpty(); // 栈必须为空才算完全匹配

    }