一个完整的括号字符串定义规则如下:
1、空字符串是完整的。
2、如果s是完整的字符串,那么(s)也是完整的。
3、如果s和t是完整的字符串,将它们连接起来形成的st也是完整的。
例如,"(()())", ""和"(())()"是完整的括号字符串,"())(", "()(" 和 ")"是不完整的括号字符串。
牛牛有一个括号字符串s,现在需要在其中任意位置尽量少地添加括号,将其转化为一个完整的括号字符串。请问牛牛至少需要添加多少个括号。
输入包括一行,一个括号序列s,序列长度length(1 ≤ length ≤ 50). s中每个字符都是左括号或者右括号,即'('或者')'.
输出一个整数,表示最少需要添加的括号数
(()(()
2
import java.util.Scanner;
/**
* 缺失的括号
* 一个完整的括号字符串定义规则如下:
* 1、空字符串是完整的。
* 2、如果s是完整的字符串,那么(s)也是完整的。
* 3、如果s和t是完整的字符串,将它们连接起来形成的st也是完整的。
* 例如,"(()())", ""和"(())()"是完整的括号字符串,"())(", "()(" 和 ")"是不完整的括号字符串。
* 牛牛有一个括号字符串s,现在需要在其中任意位置尽量少地添加括号,将其转化为一个完整的括号字符串。
* 请问牛牛至少需要添加多少个括号。
* 输入描述:
* 输入包括一行,一个括号序列s,序列长度length(1 ≤ length ≤ 50).
* s中每个字符都是左括号或者右括号,即'('或者')'.
* 输出描述:
* 输出一个整数,表示最少需要添加的括号数
* 输入例子1:
* (()(()
* 输出例子1:
* 2
*
* @author shijiacheng
* @date 2018/1/24
*/
public class Main {
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
int result = 0;
int num = 0;
for (int i = 0; i <s.length() ; i++) {
if (s.charAt(i)=='('){
num++;
}else {
if(num == 0){
result++;
}else {
num--;
}
}
}
System.out.println(result+num);
}
}
s = input() l = [] count = 0 for i in range(len(s)): if s[i] == '(': l.append(s[i]) else: if len(l) == 0: count+=1 else: l.pop() count+=len(l) print(count)
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.nextLine(); int res = getNeed(s); System.out.println(res); } public static int getNeed(String s) { int cnt = 0; int res = 0; char[] chs = s.toCharArray(); for (int i = 0; i < chs.length; i++) { if (chs[i] == '(') { cnt++; } else { cnt--; } if (cnt < 0) { cnt = 0; res++; } } if (cnt > 0) { res += cnt; } return res; } }
def findPa(aStr): if not aStr: return -1 stack = [] anw = 0 for char in aStr: if char == "(": stack.append(char) elif stack and char == ")": stack.pop() else: anw += 1 return anw + len(stack) inputStr = str(input()) print(findPa(inputStr))
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.nextLine(); int n = Find(str); System.out.println(n); } public static int Find(String str) { int n = 0; if(str.isEmpty()) return n; Stack<Character> sk = new Stack<>(); sk.push(str.charAt(0)); for(int i=1; i<str.length(); i++) { if(sk.peek()=='(') { if(str.charAt(i)==')') { sk.pop(); }else { sk.push(str.charAt(i)); } }else { sk.push(str.charAt(i)); } if(sk.empty()) { i++; sk.push(str.charAt(i)); } } n = sk.size(); return n; } }
思路:通过工具栈来判断是否合法,若栈顶元素是)且工具栈中没有元素,则count++;若栈顶元素是)则加入到工具栈中,最后工具栈的大小和count之和即为需要的添加的个数。
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
String s = sc.nextLine();
System.out.println(minCost(s));
}
static int minCost(String s){
if (s == null) return 0;
int count = 0;
Stack<String> stack1 = new Stack<>();
Stack<String> stack2 = new Stack<>();
for (int i = s.length() - 1;i >= 0;i--){
stack1.add(String.valueOf(s.charAt(i)));
}
int size = stack1.size();
for (int i = 0;i < size;i++){
String peek = stack1.peek();
if (peek.equals("(")) {
stack2.add(peek);
stack1.pop();
}
else if (stack2.size() == 0) {
count++;
stack1.pop();
}else {
stack2.pop();
stack1.pop();
}
}
return count + stack2.size();
}
}