题目描述:
一个完整的括号字符串定义规则如下:
1、空字符串是完整的。
2、如果s是完整的字符串,那么(s)也是完整的。
3、如果s和t是完整的字符串,将它们连接起来形成的st也是完整的。
例如,"(()())", ""和"(())()"是完整的括号字符串,"())(", "()(" 和 ")"是不完整的括号字符串。
有一个括号字符串s(字符串只包含“(”或者“)”),需要在其中任意位置尽量少地添加括号,将其转化为一个完整的括号字符串。请输出至少需要添加括号的个数。
=====================
输入示例:
(()(()
输出示例:
2
=====================
public static void main(String[] args) {
// ()aa)(
StringBuilder param = new StringBuilder("a((()");
Scanner scanner = new Scanner(System.in);
param = new StringBuilder(scanner.next());
Integer left = 0;
Integer right = 0;
Integer result = 0;
StringBuilder stack = new StringBuilder();
for (int i = 0; i < param.length(); i++) {
if (')' == param.charAt(i)) {
// 出栈
int j = stack.length() - 1;
for (; j >= 0; j--) {
char c = stack.charAt(j);
stack.deleteCharAt(j);
if ('(' == c) {
result++;
break;
}
}
if (j == -1) {
left++;
}
} else {
stack.append(param.charAt(i));
}
}
for (int k = 0; k < stack.length(); k++) {
if ('(' == stack.charAt(k)) {
right++;
}
}
System.out.println("匹配:" + result);
System.out.println("(:" + left);
System.out.println("):" + right);
}