Java求解添加最少括号数问题 括号序列由（）、{}、[]组成，例如“（（[{}]））（）”是合法的，而“（}{）”“（}（}”和“（{）}”都是不合法的。如果一个序列不合法，编写一个实验程序求添加的最少括号数，使这个序列变成合法的。例如，“（}（}”最少要添加4个括号变成合法的，即变为“（）{}（）{}”

这个问题可以使用栈来解决。我们遍历序列中的每个字符，如果遇到左括号就将其压入栈中，如果遇到右括号，我们就检查栈顶元素是否是与之相匹配的左括号。如果是，那么弹出栈顶元素，否则我们就需要添加一些括号来使其匹配。

具体来说，我们可以定义一个计数器来记录需要添加的括号数。当遇到未匹配的右括号时，我们可以根据栈顶元素的类型来判断需要添加哪种类型的左括号。例如，如果遇到“}”，而栈顶元素是“[”，那么我们需要添加一个左括号“{”，使其匹配。添加括号后，我们将计数器加1。

最后，如果遍历完序列后栈不为空，说明存在未匹配的左括号，我们需要添加相应数量的右括号来使其匹配。添加括号后，我们同样需要将计数器加1。

下面是Java代码实现：

相关问题

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

添加最少括号数问题可以使用栈来解决，具体代码如下：

import java.util.Stack;

public class MinParentheses {
    public static int minAddToMakeValid(String s) {
        Stack<Character> stack = new Stack<>();
        int count = 0;
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            if (c == '(') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) {
                    count++;
                } else {
                    stack.pop();
                }
            }
        }
        return count + stack.size();
    }

    public static void main(String[] args) {
        String s = "(()))";
        int res = minAddToMakeValid(s);
        System.out.println(res);
    }
}

上述代码的主要思路是遍历字符串中的每一个字符，如果是左括号就将其入栈，如果是右括号就将栈顶元素出栈，如果栈为空则需要添加一个左括号使其匹配，计数器加一。遍历完成后，如果栈中还有元素，则需要添加右括号使其匹配，计数器加上栈中元素个数即为最少需要添加的括号数。

例如，对于输入字符串"(()))"，运行上述代码的输出结果为2，表示最少需要添加2个括号才能使其成为一个匹配的括号序列。

求解添加最少括号数问题。括号序列由()、{}、[]组成，例如“(([{}]))()”是合法的，而“(}{)”、“({({”和“({)}”都是不合法的。如果一个序列不合法，可以通过添加合适的括号，使这个序列变成合法的。对于一个不合法的序列，编写一个程序求需添加的最少括号数。（C语言）

这个问题可以使用栈来解决。我们从左到右遍历括号序列，遇到左括号就将其推入栈中，遇到右括号就将栈顶的左括号弹出，如果弹出的左括号和右括号不匹配，则需要添加一个括号使得它们匹配。最后，如果栈为空，则括号序列合法，否则需要添加括号使得栈为空。

下面是代码实现：

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct {
    char *data;
    int top;
    int capacity;
} Stack;

Stack *createStack(int capacity) {
    Stack *stack = (Stack *)malloc(sizeof(Stack));
    stack->data = (char *)malloc(capacity * sizeof(char));
    stack->top = -1;
    stack->capacity = capacity;
    return stack;
}

bool isStackEmpty(Stack *stack) {
    return stack->top == -1;
}

void push(Stack *stack, char c) {
    stack->top++;
    stack->data[stack->top] = c;
}

char pop(Stack *stack) {
    char c = stack->data[stack->top];
    stack->top--;
    return c;
}

void destroyStack(Stack *stack) {
    free(stack->data);
    free(stack);
}

int getMatchingParenthesis(char c) {
    switch (c) {
        case ')':
            return '(';
        case '}':
            return '{';
        case ']':
            return '[';
        default:
            return 0;
    }
}

int getMinParenthesisCount(char *s) {
    int count = 0;
    Stack *stack = createStack(100);
    for (int i = 0; s[i] != '\0'; i++) {
        if (s[i] == '(' || s[i] == '{' || s[i] == '[') {
            push(stack, s[i]);
        } else if (s[i] == ')' || s[i] == '}' || s[i] == ']') {
            if (isStackEmpty(stack) || pop(stack) != getMatchingParenthesis(s[i])) {
                count++;
            }
        }
    }
    if (!isStackEmpty(stack)) {
        count += stack->top + 1;
    }
    destroyStack(stack);
    return count;
}

int main() {
    char s[100];
    printf("请输入括号序列：");
    scanf("%s", s);
    int count = getMinParenthesisCount(s);
    printf("需要添加的最少括号数为：%d\n", count);
    return 0;
}

这个程序的时间复杂度是 O(n)，其中 n 是括号序列的长度。