Java求解添加最少括号数的问题的具体代码及实例

问题描述：

给定一个仅包含字符'('和')'的字符串，你需要添加最少的括号来使得整个字符串都是有效的。

有效的字符串需要满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例：

输入: "())"
输出: 1
解释: 用一个'('来替换第一个')'，这样字符串变为有效字符串。

输入: "((("
输出: 3
解释: 添加三个')'可以使字符串变为有效字符串。

输入: "()"
输出: 0
解释: 字符串已经是有效的，不需要添加任何括号。

Java代码实现：

public class Solution {
    public int minAddToMakeValid(String S) {
        // 初始化计数器和栈
        int count = 0;
        Stack<Character> stack = new Stack<>();

        // 遍历字符串
        for (char c : S.toCharArray()) {
            // 如果当前字符是左括号，压入栈中
            if (c == '(') {
                stack.push(c);
            } else {
                // 如果当前字符是右括号
                if (!stack.isEmpty()) {
                    // 如果栈不为空，弹出栈顶元素
                    stack.pop();
                } else {
                    // 如果栈为空，需要添加左括号，计数器加1
                    count++;
                }
            }
        }

        // 最后需要将栈中剩余的左括号全部匹配，计数器加上栈的大小
        count += stack.size();

        return count;
    }
}

代码解析：

首先，我们初始化计数器和栈。

然后，遍历字符串。如果当前字符是左括号，我们将其压入栈中。如果当前字符是右括号，我们需要判断栈是否为空，如果不为空，则弹出栈顶元素，表示当前右括号已经匹配上了一个左括号。如果栈为空，说明当前右括号没有匹配上任何一个左括号，需要添加一个左括号，计数器加1。

最后，需要将栈中剩余的左括号全部匹配，计数器加上栈的大小，得到最终的结果。

测试样例：

String s1 = "())";
Solution solution = new Solution();
int result = solution.minAddToMakeValid(s1);
System.out.println(result); // 1

String s2 = "(((";
result = solution.minAddToMakeValid(s2);
System.out.println(result); // 3

String s3 = "()";
result = solution.minAddToMakeValid(s3);
System.out.println(result); // 0

完整代码及运行结果：

import java.util.Stack;

public class Solution {
    public int minAddToMakeValid(String S) {
        // 初始化计数器和栈
        int count = 0;
        Stack<Character> stack = new Stack<>();

        // 遍历字符串
        for (char c : S.toCharArray()) {
            // 如果当前字符是左括号，压入栈中
            if (c == '(') {
                stack.push(c);
            } else {
                // 如果当前字符是右括号
                if (!stack.isEmpty()) {
                    // 如果栈不为空，弹出栈顶元素
                    stack.pop();
                } else {
                    // 如果栈为空，需要添加左括号，计数器加1
                    count++;
                }
            }
        }

        // 最后需要将栈中剩余的左括号全部匹配，计数器加上栈的大小
        count += stack.size();

        return count;
    }

    public static void main(String[] args) {
        String s1 = "())";
        Solution solution = new Solution();
        int result = solution.minAddToMakeValid(s1);
        System.out.println(result); // 1

        String s2 = "(((";
        result = solution.minAddToMakeValid(s2);
        System.out.println(result); // 3

        String s3 = "()";
        result = solution.minAddToMakeValid(s3);
        System.out.println(result); // 0
    }
}

输出结果：

1
3
0