给定一个字符串str,判断是不是整体有效的括号字符串(整体有效:即存在一种括号匹配方案,使每个括号字符均能找到对应的反向括号,且字符串中不包含非括号字符)。
数据范围:
输入包含一行,代表str。
输出一行,如果str是整体有效的括号字符串,请输出“YES”,否则输出“NO”。
(())
YES
()a()
NO
()a()中包含了 ‘a’,a不是括号字符
时间复杂度,额外空间复杂度
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String s = sc.nextLine(); System.out.println(isBracketsStr(s) ? "YES" : "NO"); } sc.close(); } /** 此算法真正实现了时间复杂度O(n)、额外空间复杂度O(1) */ public static boolean isBracketsStr(String str) { if (str == null || str.length() == 0 || str.length() > 1e5) { return false; } char[] chars = str.toCharArray(); // 相当于栈中有多少个'(' int brackets = 0; for (int i = 0; i < chars.length; i++) { if (chars[i] != '(' && chars[i] != ')') { return false; } // 首位字符如果是右括号,不用进行后续的流程了,肯定不是有效括号串 if (chars[0] == ')') { return false; } if (chars[i] == '(') { // 相当于将'('压栈 brackets++; } else if (chars[i] == ')') { // 相当于将'('出栈 brackets--; // 栈已为空,此时再进行出栈操作,则说明在左括号'('后面有多于其数量的右括号')',因此直接判定不是有效括号串 if (brackets < 0) { return false; } } } return (brackets == 0); } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String input = sc.nextLine(); boolean res = validBracket(input); if (res) { System.out.println("YES"); } else { System.out.println("NO"); } } } public static boolean validBracket(String input) { // Corner case if (input == null || input.length() == 0) { return true; } if (input.length() % 2 != 0) { return false; } char[] array = input.toCharArray(); // Use a stack LinkedList<Character> stack = new LinkedList<>(); for (int i = 0; i < array.length; i++) { if (array[i] == '(') { stack.push(array[i]); } else if (array[i] == ')') { if (!stack.isEmpty() && stack.peek() == '(') { stack.pop(); } else { return false; } } else { return false; } } // Post Processing return stack.isEmpty(); } }
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Stack; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); char[] str = br.readLine().toCharArray(); Stack<Character> stack = new Stack<>(); for(int i = 0; i < str.length; i++){ if(str[i] != '(' && str[i] != ')'){ System.out.println("NO"); return; }else if(str[i] == '('){ stack.push(str[i]); }else{ if(!stack.isEmpty()){ stack.pop(); }else{ System.out.println("NO"); return; } } } if(stack.isEmpty()) System.out.println("YES"); else System.out.println("NO"); } }
#include <bits/stdc++.h> using namespace std; int main(){ stack<char> S; string s; cin>>s; for(auto c: s){ if(c=='(') S.push(c); else if(c==')'){ if(!S.empty() && S.top()=='(') S.pop(); else{ puts("NO"); return 0; } }else{ puts("NO"); return 0; } } if(S.empty()) puts("YES"); else puts("NO"); return 0; }
import java.util.Scanner; import java.util.regex.Matcher; public class Main{ public static void main(String[] args){ Scanner scanner = new Scanner(System.in); while(scanner.hasNext()){ String input = scanner.next(); while(true){ if(input.equals("")){ System.out.println("YES"); break; }else if(input.equals(input.replace("()",""))){ System.out.println("NO"); break; }else{ input=input.replace("()",""); } } } } }
#include <stdio.h> #include <string.h> #include <stdbool.h> #define MAXLEN 100001 bool isValid(char *str); int main(void) { char str[MAXLEN]; scanf("%s", str); printf("%s\n", isValid(str) ? "YES" : "NO"); return 0; } bool isValid(char *str) { int len = (int) strlen(str); int sum = 0; for (int i = 0; i < len; i++) { if (str[i] != '(' && str[i] != ')') return false; sum += str[i] == '(' ? 1 : -1; if (sum < 0) return false; } return sum == 0; }
#include<bits/stdc++.h> using namespace std; int main() { string str; stack<char>s; cin>>str; for(int i=0;i<str.size();i++) { if(str[i]=='(') s.push(str[i]); else if(str[i]==')') { if(s.empty()) { cout<<"NO"<<endl; return 0; } else s.pop(); } else { cout<<"NO"<<endl; return 0; } } if(s.empty()) cout<<"YES"<<endl; else cout<<"NO"<<endl; return 0; }
#include <bits/stdc++.h> using namespace std; int main() { string s; getline(cin, s); stack<char> st; for (auto& c: s) { if (c != '(' && c != ')' && c != '[' && c != ']' && c != '{' && c != '}') { cout<<"NO"<<endl; return 0; } if (st.empty()) { st.push(c); } else { char t = st.top(); if (t == '(' && c == ')') { st.pop(); } else if (t == '{' && c == '}') { st.pop(); } else if (t == '[' && c == ']') { st.pop(); } else { st.push(c); } } } if (st.empty()) { cout<<"YES"<<endl; } else { cout<<"NO"<<endl; } return 0; }
#include<iostream> #include<string> #include<vector> using namespace std; void func(string s){ int n = s.size(); vector<char> q; for(auto ch:s){ if(ch == '(')q.emplace_back(ch); else if(ch == ')' && !q.empty()){ q.pop_back(); } else{ cout<<"NO"<<endl; return; } } if(q.empty()) cout<<"YES"<<endl; else cout<<"NO"<<endl; return; } int main(){ string input; while(cin>>input){ func(input); } return 0; }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); while (sc.hasNext()) { String str = sc.next(); System.out.println(judge(str)); } } public static String judge(String str) { //如果空串直接返回null if (str.length() == 0 || str == null) { return null; } while (true) { //记录旧长度 int old = str.length(); str = str.replace("()", ""); //记录新长度 int now = str.length(); //如果替换()全部替换成功那么直接返回YES if ("".equals(str)) { return "YES"; } //如果老长度和新长度一样,那么代表没有替换成功,直接返回NO if (old == now) { return "NO"; } } } }
import java.util.Scanner; import java.util.Stack; public class Main { public boolean check(String str){ if(str.length()%2!=0) return false; Stack<Character> stack=new Stack<>(); char[] chars = str.toCharArray(); for(char ch:chars){ if(ch!=')') stack.push(ch); else if(ch==')' &&!stack.isEmpty()) stack.pop(); } return stack.isEmpty(); } public static void main(String[] args) { Main main=new Main(); Scanner scanner = new Scanner(System.in); String str=scanner.nextLine(); boolean res=main.check(str); if(res) System.out.print("YES"); else System.out.print("NO"); } }栈
import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.nextLine(); while(true){ int l1 = str.length(); str = str.replace("()",""); int l2 = str.length(); if(l1==l2){ break; } } if(str.length()>0){ System.out.println("NO"); }else System.out.println("YES"); } }
#include <stdio.h> #include <stdlib.h> #include <string.h> #define STACK_INIT_SIZE 100002 typedef char SElemtype; typedef struct{//定义栈 SElemtype *base; SElemtype *top; }SqStack; int InitStack(SqStack *S){//创建空栈 S->base=(SElemtype *)malloc(STACK_INIT_SIZE*sizeof(SElemtype)); S->top=S->base; return 1; } int PushAndCompare(SqStack *S,char p){//压栈并判断和栈顶括号是否匹配 if(p==')'){ if(*(S->top-1)=='('){ S->top--; return 1; } *S->top++=p; return 1; } *S->top++=p; return 1; } int main() { char str[STACK_INIT_SIZE]; while(fgets(str,STACK_INIT_SIZE,stdin)!=NULL){ char *p=strchr(str,'\n'); *p='\0'; SqStack *S=(SqStack *)malloc(sizeof(SqStack)); InitStack(S); int flag=0; for(int i=0;i<strlen(str);i++){ if(str[i]=='('||str[i]==')'){ if(!PushAndCompare(S,str[i])){ printf("NO\n"); flag=1; break; } } } if(flag){ continue; } if(S->top-S->base==0){ printf("YES\n"); } else{ printf("NO\n"); } } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String next = scanner.next(); int count = 0; for (int i = 0; i < next.length(); i++) { if (count <= 0 && i != 0) { System.out.println("NO"); return; } if (next.charAt(i) == '(') { count++; } else if (next.charAt(i) == ')') { count--; } else { System.out.println("NO"); return; } } if (count==0){ System.out.println("YES"); }else { System.out.println("NO"); } } }
import java.util.*; public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); while (in.hasNext()) { //注意while处理多个case int a = in.nextInt(); String b = in.next(); System.out.println(isStr(b)); } } public static String isStr(String str){ Stack<Character> stack = new Stack<>(); char[] chars = str.toCharArray(); for(char c : chars){ if(c == '('){ stack.push(')'); }else if(stack.isEmpty() || c != stack.pop()){ return "NO"; } } return stack.isEmpty() ? "YES" : "NO"; } }
import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String s = sc.next(); System.out.println(check(s) ? "YES": "NO"); } private static boolean check(String s) { if (s == null || s.length() == 0) return false; int count = 0; for (int i = 0; i < s.length(); ++i) { if (s.charAt(i) == '(') { count++; } else if (s.charAt(i) == ')'){ if (--count < 0) { return false; } } else { return false; } } return count == 0; } }
import java.util.*; public class Main{ public static void main(String[] args){ Scanner sc = new Scanner(System.in); String str = sc.next(); ppkh(str); } public static void ppkh(String str){ if(str != null){ char[] arr = str.toCharArray(); int qkh = 0; boolean flag = false; for(int i=0;i<arr.length;i++){ if('(' == arr[i]){//左括号加 qkh++; }else if(')' == arr[i]){//右括号减 qkh--; }else{//不是括号跳出 flag = true; break; } if(qkh < 0){//值为负说明有括号没匹配上,跳出 flag = true; break; } } if(flag){ System.out.println("NO"); }else if(qkh == 0){ System.out.println("YES"); }else{ System.out.println("NO"); } } } }
import java.util.Scanner; import java.util.Stack; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String str = scanner.nextLine().trim(); Stack<Character> stack = new Stack<>(); char[] ch = str.toCharArray(); for (int i = 0; i < ch.length; i++) { if (ch[i] == '(') { stack.push('('); } else if (ch[i] == ')') { if (stack.isEmpty()) { System.out.println("NO"); return; } stack.pop(); } else { System.out.println("NO"); return; } } if (stack.isEmpty()) { System.out.println("YES"); } else { System.out.println("NO"); } } }
import java.util.*; public class Main { public boolean test(String nums){ int length = nums.length(); //数组长度为奇数,一定不匹配 if (length % 2 != 0) return false; char[] chars = nums.toCharArray(); Stack<Character> stack = new Stack<Character>(); int i = 0; while (i < length) { if (chars[i]=='(') stack.push(chars[i++]); else if (chars[i++]==')'){ if (stack.size()==0) return false; if (stack.pop()!='(') return false; } else return false; } //可能存在'('多于')'的情况,需要判断此时栈顶是否还存在元素 if (stack.size()!=0) return false; return true; } public static void main(String[] args) { Scanner in = new Scanner(System.in); String str = in.nextLine(); Main main = new Main(); if (main.test(str)) { System.out.println("YES"); } else { System.out.println("NO"); } } }