括号字符串的有效性

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

#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;
}

#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;
}

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.*;
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;
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");
        }
    }
}