Parentheses Balance#2479

Parentheses Balance (Editorial)

Algorithm Analysis

To solve the problem, we will use a symbolic stack. We will move sequentially through the characters of the input string and:

if the current character is an opening bracket (either round or square), then we put it into the stack.
if the current character is a closing bracket, then on the top of the stack there must be the corresponding opening bracket. If this is not the case, or if the stack is empty, then the bracket expression is not correct.

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

Example

Consider the stack simulation for the string “( ( [ ] ) [ ] )”.

Algorithm Implementation

We will read the input bracket expression into an array stroka. Declare a stack s, which is used in the problem.

char stroka[150];
stack<char> s;

Read the number of tests tests. For each input string stroka, calculate its length len. The variable flag will become equal to 1 if the input bracket expression is not correct.

scanf("%d\n",&tests);
while(tests--)
{
    gets(stroka); flag = 0;
    
    // Clear the stack s.
    while(!s.empty()) s.pop();

    // Move through the characters of the input string stroka.
    for(i = 0; i < strlen(stroka); i++)
    {
        // Put the opening bracket into the stack.
        if ((stroka[i] == '(') || (stroka[i] == '[')) s.push(stroka[i]);
        
        // If the current character stroka[i] is a closing bracket, then
        // extract the character from the top of the stack, which must be the corresponding
        // opening bracket. If this is not the case, or if the stack is empty, then set flag equal to 1.
        else if (!s.empty() && ((stroka[i] == ')' && s.top() == '(') || (stroka[i] == ']' && s.top() == '['))) s.pop();
        else flag = 1;
    }

    // If at the end of processing the string the stack is not empty, then the input bracket expression is not correct.
    if (!s.empty()) flag = 1;

    // Depending on the value of the variable flag, output the answer.
    if (flag) printf("No\n"); else printf("Yes\n");
}

Java Implementation

import java.util.*;

public class Main
{
    static char rev(char c)
    {
        return (c == ')') ? '(' : '[';
    }

    public static void main(String[] args)
    {
        Scanner con = new Scanner(System.in);
        int tests = con.nextInt();
        String Line = con.nextLine();
        while(tests-- > 0)
        {
            Line = con.nextLine();
            Stack<Character> s = new Stack<Character>();
            int Flag = 0;
            for(int i = 0; i < Line.length(); i++)
            {
                if (Flag > 0) break;
                if ((Line.charAt(i) == '(') || (Line.charAt(i) == '[')) s.push(Line.charAt(i));
                if ((Line.charAt(i) == ')') || (Line.charAt(i) == ']'))
                {
                    if (s.empty() or (s.peek() != rev(Line.charAt(i)))) Flag = 1;
                    else s.pop();
                }
            }
            if (!s.empty()) Flag = 1;
            if (Flag > 0) System.out.println("No");
            else System.out.println("Yes");
        }
    }
}

Java