缺失的括号

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();
    }
}