Generating and Checking Balanced Parentheses

In this article we will generate all the possible pairs of balanced parentheses and then we will test if the parenthesis input by a user is valid or not.

Generate Combinations of Parentheses

In this section we will generate all possible pairs of balanced parentheses with n pair of brackets (curly or round). The count of length of each balanced pair of parentheses will be 2*N (N is the given number of pairs). Suppose we need to generate balanced parentheses and we can only add ‘}’ to the pair if the count of ‘{’ is greater than the count of ‘}’ and we will add ‘{’ to our pair only if the count of ‘{’ is lesser than N.

Algorithm

Create a list in which we will store all possible combinations, List<String>
Array to store each pair - arr[]

Step 1: Call made to recursive method generator() with open and close bracket count, position for putting bracket, N integer and list will be passed as arguments.

Step 2: Check for base condition if position is equal to double of N.
if matched then
traverse arr[] and add into List<String>
return;
else go to Step 3

Step 3: Check if open_count is greater than close_count
then add ‘}’ into arr[]
recursively call generator() passing arr[], position++, open will remain same, close++, List as arguments.

Step 4: Check if open_count is lesser than N
then add ‘{’ into arr[]
recursively call generator() passing arr[], position++, open++, close remain same, list as arguments.

Step 5: Traverse List<String> and print all generated combinations.

Java Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
import java.io.*;
import java.util.*;

class Solution {
  static void generator(char arr[], int pos, int open, int close, int N, List < String > list) {
    if (pos == (2 * N)) {
      String s = "";
      for (int ii = 0; ii < 2 * N; ii++)
        s += String.valueOf(arr[ii]);
      list.add(s);
      return;
    }

    if (open > close) {
      arr[pos] = ')';
      generator(arr, pos + 1, open, close + 1, N, list);
    }
    if (open < N) {
      arr[pos] = '(';
      generator(arr, pos + 1, open + 1, close, N, list);
    }
    //return;
  }
  public static void main(String args[]) {

    /*Scanner object*/
    Scanner sc = new Scanner(System.in);
    System.out.println("Enter Number:");
    int n = sc.nextInt();

    List < String > list = new ArrayList < > ();
    char arr[] = new char[2 * n];
    generator(arr, 0, 0, 0, n, list);

    for (String pair: list) {
      System.out.println(pair);
    }
  }
}

Code Snippet

Check for Balanced Parentheses

Suppose we are given parentheses, or expressions, and we need to test if an expression is balanced or not. We can perform this check using a stack. If we get an open bracket we will push it into a stack and if we get a closed bracket we will pop it from the stack. If the popped character from the stack does not match with the open bracket ( like ‘{’ and ‘}’ matches but ‘{’ and ‘)’ do not), then it is not balanced. Otherwise we will process until the stack is empty.

Algorithm

Step 1: Call made to isBalanced() passing stack S and arr[] containing expression.

Step 2: Loop traverse the Expression or arr
if current character is ‘{’, ‘(’, ‘[’ then push into stack
return

Step 3: Check if stack empty
then return “Not Balanced”
else go to step 4

Step 4: Pop() from stack
check if popped character matches its pair then go to step 2
else return "“Not Balanced”

Java Implementation

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
import java.util.*;
import java.lang.*;
import java.io.*;

class Solution {

  static void isBalanced(ArrayDeque < Character > stack, char arr[]) {
    char x, y;

    boolean flag = true;
    for (int ii = 0; ii < arr.length; ii++) {
      x = arr[ii];

      if (x == '(' || x == '{' || x == '[') {
        stack.push(x);
        continue;
      }

      if (stack.isEmpty()) {
        System.out.println("not balanced");
        return;
      }

      y = stack.pop();
      if (x == '}') {
        if (y == '{')
          continue;
        else {
          System.out.println("not balanced");
          flag = false;
          break;
        }
      }
      if (x == ')') {
        if (y == '(')
          continue;
        else {
          System.out.println("not balanced");
          flag = false;
          break;
        }
      }
      if (x == ']') {
        if (y == '[')
          continue;
        else {
          System.out.println("not balanced");
          flag = false;
          break;
        }
      }
    }

    if (flag)
      if (stack.isEmpty())
        System.out.println("balanced");
      else
        System.out.println("not balanced");

  }

  public static void main(String[] args) throws IOException {

    BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
    System.out.print("Enter Test Cases:");
    int t = Integer.parseInt(bf.readLine());

    while (t > 0) {
      t--;

      String str = bf.readLine();
      str = str.trim();
      if (str.length() == 1) {
        System.out.println("not balanced");
        continue;
      }
      char arr[] = str.toCharArray();
      ArrayDeque < Character > stack = new ArrayDeque < > ();

      isBalanced(stack, arr);

    }

  }
}

Code Snippet