首页 > 试题广场 >

缺失的括号

[编程题]缺失的括号

热度指数：460 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 64M，其他语言128M
算法知识视频讲解

一个完整的括号字符串定义规则如下:
1、空字符串是完整的。
2、如果s是完整的字符串，那么(s)也是完整的。
3、如果s和t是完整的字符串，将它们连接起来形成的st也是完整的。
例如，"(()())", ""和"(())()"是完整的括号字符串，"())(", "()(" 和 ")"是不完整的括号字符串。
牛牛有一个括号字符串s,现在需要在其中任意位置尽量少地添加括号,将其转化为一个完整的括号字符串。请问牛牛至少需要添加多少个括号。

输入描述:

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

输出描述:

输出一个整数,表示最少需要添加的括号数

示例1

输入

(()(()

输出

算法知识视频讲解

﹏清心

public static void main(String args[]){
	    	 Scanner in = new Scanner(System.in);
	         String str = in.nextLine();
                 //count计数多出来的"("，n计数字符串最前面的")"
	         int count = 0, n=0;
	  
	         for(int i = 0; i < str.length(); i++){
	             if(str.charAt(i) == '('){
	            	 count++;
	             }
	             if(str.charAt(i) == ')') {
	            	 if(count == 0){
	            		 n++;
	            	 }else{
	            		 count--;
	            	 }
	             }
	         }
	         System.out.println(count+n);
	  
	     }

开始没想写代码的，就想看看评论代码，觉得有问题，就自己动手咯，对于这道题的话，求的是需要添加多少括号，而不是深度。

思路很清晰，就是一个左括号需要对应一个右括号，需要注意的点是，字符串最开始如果有右括号的话，需要单独计数。

不用判断输入为空，因为反正那样输出为0。

发表于 2017-12-22 14:47:25 回复(7)

苏堤

import java.util.Scanner;
public class Main {
public static void main(String[] args) {         // TODO Auto-generated method stub         Scanner sc = new Scanner(System.in);         String s= sc.nextLine();         int l=s.length();                  int Count=0;         int right =0;         char[]c=new char[l];                  c= s.toCharArray();                  for(int i=0;i<l;i++)         {             //if(s.charAt(i)=='(')             if( c[i]=='(')                 Count++;             else if( c[i]==')'&&Count>0)                 Count--;             else                 right++;                                       }         System.out.println(Count+right);          }
}

发表于 2018-04-19 15:50:31 回复(0)

yogurt😊

  importjava.util.*; 
  publicclassMain{ 
      publicstaticvoidmain(String[] args) { 
          Scanner sc = newScanner(System.in); 
          intans = 0; 
          Stack<Character> stack = newStack<>(); 
          String str = ""; 
          while(sc.hasNext()) { 
              str = sc.nextLine(); 
          } 
          for(charch : str.toCharArray()) { 
              if(ch == '('|| stack.empty()) stack.push(ch); 
              elseif(ch == ')'&& stack.peek() != '(') stack.push(ch); 
              elsestack.pop(); 
          } 
          ans = stack.size(); 
          System.out.println(ans); 
      } 
  } 

发表于 2018-04-19 15:38:10 回复(0)

Prass

def main():
    s = input()
    while True:
        i = s.find('()')
        if i < 0:
            break
        s = s[: i] + s[i + 2:]
    print(len(s))


if __name__ == '__main__':
    main()

发表于 2018-04-18 17:07:52 回复(0)

科大迷途小书童

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        char[] arr= str.toCharArray();
        //创建一个空栈
        Stack<Character> stack = new Stack<Character>();
        stack.push(arr[0]);
        //System.out.println(stack.size());
        for(int i = 1;i<arr.length;i++){
            if (stack.empty()||stack.peek()==arr[i]||stack.peek()==')'){
                stack.push(arr[i]);
            }else{
                stack.pop();
            }
        }
        System.out.println(stack.size());
    }
}

发表于 2018-04-02 15:25:22 回复(0)

Java

刘禅挥泪斩孔明

import java.util.Scanner;
public class Main {
  public static void main(String[] args) {
    Scanner sc = new Scanner(System.in);
    int cnt=0, bracket=0, i;
    String input = sc.nextLine();
    for (i=0; i<input.length(); ++i) {
      if (input.charAt(i) == '(')
        bracket++;
      else
        bracket--;
      if (bracket < 0) {
        bracket = 0;
        cnt++;
      }
    }
    System.out.println(cnt += bracket);
  }
}

发表于 2018-03-17 22:49:17 回复(0)

voidString

/*采用栈后进先出的思想匹配左右括号，遇到'('顶入栈，即count++，遇到')'栈顶出栈，即count--
每次count都与max比较大小，最大的数即为括号深度
*/
import java.util.Scanner;

public class Test {

    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);

        String str = sc.nextLine();

        int count = 0,max = 1;

        for(int i = 0; i < str.length()-1; i++){

            if(str.charAt(i) == '('){

                count ++;

            }

            if(str.charAt(i) == ')'){

                count--;

            }

            if(count > max){

                max = count;

            }

        }

        System.out.println(max);

    }

}

发表于 2017-12-11 09:06:14 回复(2)

Accepts

   我的有点啰嗦了。。。。。。
  
   importjava.util.Scanner;  
   importjava.util.Stack;  
      
   publicclassMain {  
       publicstaticvoidmain(String[] args) {  
           Stack<Character> stack =newStack<Character>();  
           Scanner in =newScanner(System.in);  
           String next = in.next();  
           intcount =0;;  
           for(inti =0; i < next.length(); i++) {  
               charvalue = next.charAt(i);  
               if(stack.isEmpty() && value==')'){  
                   count++;  
                   continue;  
               }  
               if(!stack.isEmpty()){  
                   Character peek = stack.peek();  
                   if(peek =='('&& value ==')'){  
                       stack.pop();  
                   }  
                   if(value =='('){  
                       stack.push(value);  
                   }  
               }else{  
                   stack.push(value);  
               }  
           }  
           System.out.println(stack.size()+count);  
       }  
   }  