Algorithm Analysis

Declare a stack in which we will only store opening brackets. Upon receiving the next character, we perform the following operation with the stack:

• if the character ‘(‘ is encountered, then we put it in the stack;

• if the character ‘)’ is encountered, then we remove an element from the stack. If the stack is empty at this point, then the sequence is not bracketed (at some point, the number of closing brackets is greater than the number of opening ones);

At the end of processing the string, the stack must be empty.

We can model the stack using a single variable. Let the variable cnt store the number of open brackets in the stack. Then, when adding the character ‘(‘ to the stack, we will perform the operation cnt++, and when removing an element from the stack, the operation cnt--.

Example

Let's model the stack operation for the string “((())())” from the first example.

Algorithm Implementation

Read the input string.

cin >> s;

The variable cnt stores the number of current unclosed brackets (i.e., the number of opening brackets that have not yet met their corresponding closing ones).

The variable flag will become equal to 1 if, at any iteration, the number of closing brackets becomes greater than the number of opening ones. Initially, set flag = 0.

cnt = flag = 0;

Process the input string character by character, modeling the stack operation.

for (i = 0; i < s.size(); i++)
{
    if (s[i] == '(') cnt++; else cnt--;
    if (cnt < 0) flag = 1;
}

Depending on the values of the variables flag and cnt, output the answer. The stack will be empty at the end of processing the string if cnt = 0.

if (flag == 0 && cnt == 0) cout << "YES\n"; else cout << "NO\n";

Java implementation using string

import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner con = new Scanner(System.in);
        String s = con.nextLine();
        boolean flag = false; 
        int open = 0;
        for(int i = 0; i < s.length(); i++)
        {
            if (s.charAt(i) == '(') open++; else open--;
            if (open < 0) flag = true;
        }
        if (flag || (open > 0)) System.out.println("NO"); else System.out.println("YES");
        con.close();    
    }
}

Java implementation using character array

import java.util.*;

public class Main
{
    public static void main(String[] args)
    {
        Scanner con = new Scanner(System.in);
        char s[] = con.nextLine().toCharArray();
        boolean flag = false; 
        int open = 0;
        for(int i = 0; i < s.length; i++)
        {
            if (s[i] == '(') open++; else open--;
            if (open < 0) flag = true;
        }
        if (flag || (open > 0)) System.out.println("NO"); else System.out.println("YES");
        con.close();    
    }
}

Python implementation

Read the input string.

s = input()

The variable cnt stores the number of current unclosed brackets (i.e., the number of opening brackets that have not yet met their corresponding closing ones).

The variable flag will become equal to 1 if, at any iteration, the number of closing brackets becomes greater than the number of opening ones. Initially, set flag = 0.

cnt = flag = 0

Process the input string character by character, modeling the stack operation.

for ch in s:
    if ch == '(': cnt += 1
    else: cnt -= 1
    if cnt < 0: flag = 1

Depending on the values of the variables flag and cnt, output the answer. The stack will be empty at the end of processing the string if cnt = 0.

if flag == 0 and cnt == 0:
    print("YES")
else:
    print("NO")