Java Program to Determine Whether a Given String of Parentheses (Multiple Types) is Properly Nested

Determining if a string of multiple types of parentheses is properly nested involves checking if every opening parenthesis ((, {, [) has a matching and correctly placed closing parenthesis (), }, ]).

Proper nesting ensures that parentheses are balanced and correctly ordered. It is essential in applications like programming language syntax checking and mathematical expression evaluation. A common approach to solve this problem is using a stack, which helps manage the nested structure and verify that parentheses are matched in the correct sequence.

A string S consisting of N characters is adequately considered nested if it satisfies one of the following conditions:

1. Empty String: The string S is empty.
2. Basic Proper Nesting: The string S is structured as (U), [U], or {U}, where U is a string that is properly nested.
3. Concatenation of Properly Nested Strings: The string S can be separated into two substrings, V and W, with V and W both being correctly nested strings.

For example:

• The string {[()()]} is properly nested.
• The string ([)()] is not properly nested.

Algorithm

Step 1: Initialize an empty stack to keep track of opening parentheses.

Step 2: Go through every character in the string: If it is an opening parenthesis ((, {, [), add it to the stack. If the character is a closing parenthesis (), }, ]):

• Check if the stack is empty. If so, return false (no matching opening parenthesis).
• Otherwise, pop the top element from the stack and ensure it matches the corresponding opening parenthesis for the current closing parenthesis. If it doesn't match, return false.

Step 3: If the character is not a valid parenthesis, return false.

Step 4: If the stack is empty, return true (all opening parentheses were matched). If the stack is not empty, return false (some opening parentheses were not matched).

Step 5: Return the Result based on the final stack check.

Let's implement the above approach in a Java program.

File Name: ParenthesesChecker.java

Output:

 String: () is properly nested: true String: {[()]} is properly nested: true String: {[(])} is properly nested: false String: {{[[(())]]}} is properly nested: true String: ([)] is properly nested: false String: is properly nested: true