Question

You are given a string containing a sequence of open and close brackets. and isOpen, isClose, isMatching methods as defined below. Write a recursive algorithm in pseudocode for the method isBalanced that takes the  string and a stack of characters as the input and checks if the given input string contains balanced brackets. For example "(][)" would be considered not balanced where "[()]" would be considered balanced.

The recursive isBalanced method utilizes  isOpen, isClose, isMatching methods as defined below.

static String open = "([<{";
static String close = ")]>}";

static boolean isOpen(char ch)
{
    return open.indexOf(ch) != -1;
}

static boolean isClose(char ch)
{
    return close.indexOf(ch) != -1;
}

static boolean isMatching(char chOpen, char chClose)
{
    return open.indexOf(chOpen) == close.indexOf(chClose);
}

static boolean isBalanced(String input, String<Character> stack) 
{

// write pseudocode for the recursive algorithm here

}

Answer 1

static boolean isBalanced(String input, String<Character> stack) 
{
    if input[0] == '\0' //end of String
    {
        if (stack.isEmpty())
            return true;
        else
            return false;
        
    }
    if (isOpen(input[0]))
    {
        stack.push(input[0])
        return isBalanced(input[1:length(input)],stack)
    }
    else if(isClose(input[0]))
    {
        if (isMatching(stack.pop(),input[0]))
            return isBalanced(input[1:length(input)],stack)
        else
            return false;
    }
    
}