首页 > 试题广场 >

缺失的括号

[编程题]缺失的括号
  • 热度指数:298 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 64M,其他语言128M
  • 算法知识视频讲解
一个完整的括号字符串定义规则如下:
1、空字符串是完整的。
2、如果s是完整的字符串,那么(s)也是完整的。
3、如果s和t是完整的字符串,将它们连接起来形成的st也是完整的。
例如,"(()())", ""和"(())()"是完整的括号字符串,"())(", "()(" 和 ")"是不完整的括号字符串。
牛牛有一个括号字符串s,现在需要在其中任意位置尽量少地添加括号,将其转化为一个完整的括号字符串。请问牛牛至少需要添加多少个括号。

输入描述:
输入包括一行,一个括号序列s,序列长度length(1 ≤ length ≤ 50).
s中每个字符都是左括号或者右括号,即'('或者')'.


输出描述:
输出一个整数,表示最少需要添加的括号数
示例1

输入

(()(()

输出

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

    }
}
发表于 2018-01-24 21:43:34 回复(0)
注意右边括号大于左边括号这种情况就行
#include <bits/stdc++.h>
using namespace std;
int main()
{
   string str;
   cin>>str;
   stack<char> st;
   int l=0,r=0,count;
   for(int i=0;i<str.size();i++)
   {
      if(str[i]=='(')
        ++l;
      else if(str[i]==')')
      {
         if(r>=l)  +count;
         else    ++r;
      }
   }
   cout<<(count+l-r)<<endl;
}

发表于 2019-11-26 10:38:23 回复(0)
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)

发表于 2021-08-02 20:10:22 回复(0)
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;
    }
}
发表于 2021-04-13 15:21:14 回复(0)
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))

发表于 2021-03-21 12:56:58 回复(0)
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;
    }
}

发表于 2020-03-29 09:42:16 回复(0)

思路:通过工具栈来判断是否合法,若栈顶元素是)且工具栈中没有元素,则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();
    }
}
编辑于 2018-09-04 20:19:14 回复(0)