Question

1. Using a Stack, describe the algorithm below (with pre conditions and post conditions) how you would check a block of code and be sure it has the appropriate amount of curly brackets { }. (java)

Answer 1

Given an piece of code, how to examine whether the pairs and the orders of “{“, “}”, “(“, “)”, “[“, “]” are correct.

Example:

Input: exp = “[()]{}{[()()]()}”
Output: correct

Input: exp = “[(])”
Output: Not correct

Algorithm:

• Declare a character stack S.
• Now traverse the expression string exp.
  1. If the current character is a starting bracket (‘(‘ or ‘{‘ or ‘[‘) then push it to stack.
  2. If the current character is a closing bracket (‘)’ or ‘}’ or ‘]’) then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced.
• After complete traversal, if there is some starting bracket left in stack then “not balanced”

// Java program for checking

// balanced Parenthesis

import java.util.*;

public class BalancedParan

{

    // function to check if paranthesis are balanced

    static boolean areParanthesisBalanced(String expr)

    {

        // Using ArrayDeque is faster than using Stack class

        Deque<Character> stack

            = new ArrayDeque<Character>();

        // Traversing the Expression

        for (int i = 0; i < expr.length(); i++)

        {

            char x = expr.charAt(i);

            if (x == '(' || x == '[' || x == '{')

            {

                // Push the element in the stack

                stack.push(x);

                continue;

            }

            // IF current current character is not opening

            // bracket, then it must be closing. So stack

            // cannot be empty at this point.

            if (stack.isEmpty())

                return false;

            char check;

            switch (x)

            {

            case ')':

                check = stack.pop();

                if (check == '{' || check == '[')

                    return false;

                break;

            case '}':

                check = stack.pop();

                if (check == '(' || check == '[')

                    return false;

                break;

            case ']':

                check = stack.pop();

                if (check == '(' || check == '{')

                    return false;

                break;

            }

        }

        // Check Empty Stack

        return (stack.isEmpty());

    }

    // Driver code

    public static void main(String[] args)

    {

        String expr = "([{}])";

       

        // Function call

        if (areParanthesisBalanced(expr))

            System.out.println("Balanced ");

        else

            System.out.println("Not Balanced ");

    }

}

Output

Balanced

Time Complexity: O(n)
Auxiliary Space: O(n) for stack