有效的括号

题目要求

编写一个算法来判断一个只包含括号字符的字符串是否为有效的括号组合。有效字符串的定义如下：

任何左括号 '(' 必须有一个对应的右括号 ')'。
任何左大括号 '{' 必须有一个对应的右大括号 '}'。
任何左方括号 '[' 必须有一个对应的右方括号 ']'。
左括号必须以正确的顺序闭合，这意味着括号之间不能交叉或不匹配。

解题思路

为了解决这个问题，我们可以使用栈（Stack）这一数据结构。栈是一种后进先出（LIFO）的数据结构，它允许我们只在一端（顶部）添加或移除数据。以下是解题的步骤：

初始化一个空栈。
遍历字符串中的每个字符：
- 如果当前字符是开括号（'('，'{' 或 '['），则将其推入栈中。
- 如果当前字符是闭括号（')'，'}' 或 ']'）：
  - 检查栈是否为空。如果为空，说明没有对应的开括号，因此字符串无效。
  - 否则，弹出栈顶元素。如果弹出的开括号与当前闭括号类型不匹配，则字符串无效。
在遍历完所有字符后，如果栈为空，则说明所有开括号都找到了匹配的闭括号，字符串有效。
如果栈不为空，则说明有未匹配的开括号，字符串无效。

通过这种方式，我们可以确保所有的开括号都有对应的闭括号，并且它们的顺序是正确的。

Golang 版本

package main

import (
	"fmt"
)

func isValid(s string) bool {
	stack := []rune{}

	for _, char := range s {
		switch char {
		case '(', '{', '[':
			stack = append(stack, char)
		case ')', '}', ']':
			if len(stack) == 0 {
				return false
			}
			top := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			if (char == ')' && top != '(') || (char == '}' && top != '{') || (char == ']' && top != '[') {
				return false
			}
		}
	}

	return len(stack) == 0
}

func main() {
	s := "([]{})"
	fmt.Println(isValid(s)) // 输出应为 true
}

这段代码定义了一个isValid函数，它接受一个字符串s并返回一个布尔值，表示字符串中的括号是否有效。主函数main中给出了一个示例字符串，并打印出了isValid函数的返回结果。

C++版本

#include <iostream>
#include <stack>
#include <string>

bool isValid(std::string s) {
    std::stack<char> stack;

    for (char c : s) {
        switch (c) {
            case '(':
            case '{':
            case '[':
                stack.push(c);
                break;
            case ')':
                if (stack.empty() || stack.top() != '(') return false;
                stack.pop();
                break;
            case '}':
                if (stack.empty() || stack.top() != '{') return false;
                stack.pop();
                break;
            case ']':
                if (stack.empty() || stack.top() != '[') return false;
                stack.pop();
                break;
            default:
                // Invalid character
                return false;
        }
    }

    return stack.empty();
}

int main() {
    std::string s = "([]{})";
    std::cout << (isValid(s) ? "true" : "false") << std::endl; // 应输出 true
    return 0;
}

这段 C++代码定义了一个isValid函数，它接受一个字符串s并返回一个布尔值，表示字符串中的括号是否有效。主函数main中给出了一个示例字符串，并打印出了isValid函数的返回结果。

Python 版本

def is_valid(s: str) -> bool:
    stack = []
    bracket_map = {')': '(', '}': '{', ']': '['}

    for char in s:
        if char in bracket_map:
            top_element = stack.pop() if stack else '#'
            if bracket_map[char] != top_element:
                return False
        else:
            stack.append(char)

    return not stack

# 测试代码
s = "([]{})"
print(is_valid(s))  # 应输出 True

Java 版本

import java.util.Stack;

public class Solution {
    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '{' || c == '[') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                char top = stack.pop();
                if ((c == ')' && top != '(') || (c == '}' && top != '{') || (c == ']' && top != '[')) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "([]{})";
        System.out.println(solution.isValid(s)); // 应输出 true
    }
}

这段 Java 代码定义了一个Solution类，其中包含了一个isValid方法，用于判断字符串中的括号是否有效。在main方法中，创建了一个Solution对象，并用一个示例字符串调用了isValid方法，然后打印出了方法的返回结果。

Rust 版本

fn is_valid(s: String) -> bool {
    let mut stack: Vec<char> = Vec::new();
    for c in s.chars() {
        match c {
            '(' | '{' | '[' => stack.push(c),
            ')' => if stack.pop() != Some('(') { return false; },
            '}' => if stack.pop() != Some('{') { return false; },
            ']' => if stack.pop() != Some('[') { return false; },
            _ => return false,
        }
    }
    stack.is_empty()
}

fn main() {
    let s = String::from("([]{})");
    println!("{}", is_valid(s)); // 应输出 true
}

这段 Rust 代码定义了一个is_valid函数，它接受一个字符串s并返回一个布尔值，表示字符串中的括号是否有效。在main函数中，创建了一个示例字符串，并调用了is_valid函数，然后打印出了函数的返回结果。

总结

上述代码示例中，无论是 Golang、C++、Python、Java 还是 Rust 版本，核心算法思路都是相同的，即使用栈（Stack）数据结构来确保括号的正确匹配。算法的步骤可以总结如下：

创建一个空栈来存储开括号。
遍历输入字符串中的每个字符。
当遇到开括号（'('，'{'，'['）时，将其推入栈中。
当遇到闭括号（')'，'}'，']'）时，检查栈顶元素：
- 如果栈为空，或者栈顶元素与当前闭括号不匹配，则字符串无效。
- 如果栈顶元素与当前闭括号匹配，将栈顶元素弹出。
在遍历完成后，如果栈为空，则说明所有的开括号都找到了匹配的闭括号，字符串有效。
如果栈不为空，则还有未匹配的开括号，字符串无效。

不同语言在实现上有细微差别，主要体现在语法和数据结构的使用上。例如：

Golang 使用切片（slice）模拟栈。
C++使用std::stack标准库中的栈。
Python 直接使用列表（list）作为栈。
Java 使用java.util.Stack类。
Rust 使用向量（Vec）来模拟栈。

尽管实现的细节不同，但所有这些解法都遵循了相同的逻辑和算法步骤。

hot-100