Basic Recursion, Check Balanced Parenthesis

Question

I've written software in the past that uses a stack to check for balanced equations, but now I'm asked to write a similar algorithm recursively to check for properly nested brackets and parenthesis.

Good examples: () [] () ([]()[])

Bad examples: ( (] ([)]

Suppose my function is called: isBalanced.

Should each pass evaluate a smaller substring (until reaching a base case of 2 left)? Or, should I always evaluate the full string and move indices inward?

Answer 1

It should be a simple use of stack ..

private string tokens = "{([<})]>";        
    Stack<char> stack = new Stack<char>();   

    public bool  IsExpressionVaild(string exp)
    {
        int mid = (tokens.Length / 2)  ;  

        for (int i = 0; i < exp.Length; i++)
        {
            int index = tokens.IndexOf(exp[i]);
            if (-1 == index) { continue; }

            if(index<mid ) stack .Push(exp[i]);
            else 
            {
                if (stack.Pop() != tokens[index - mid]) { return false; }       

            }          

        }
        return true;       

    }

Answer 2

The idea is to keep a list of the opened brackets, and if you find a closing brackt, check if it closes the last opened:

• If those brackets match, then remove the last opened from the list of openedBrackets and continue to check recursively on the rest of the string
• Else you have found a brackets that close a nerver opened once, so it is not balanced.

When the string is finally empty, if the list of brackes is empty too (so all the brackes has been closed) return true, else false

ALGORITHM (in Java):

public static boolean isBalanced(final String str1, final LinkedList<Character> openedBrackets, final Map<Character, Character> closeToOpen) {
    if ((str1 == null) || str1.isEmpty()) {
        return openedBrackets.isEmpty();
    } else if (closeToOpen.containsValue(str1.charAt(0))) {
        openedBrackets.add(str1.charAt(0));
        return isBalanced(str1.substring(1), openedBrackets, closeToOpen);
    } else if (closeToOpen.containsKey(str1.charAt(0))) {
        if (openedBrackets.getLast() == closeToOpen.get(str1.charAt(0))) {
            openedBrackets.removeLast();
            return isBalanced(str1.substring(1), openedBrackets, closeToOpen);
        } else {
            return false;
        }
    } else {
        return isBalanced(str1.substring(1), openedBrackets, closeToOpen);
    }
}

TEST:

public static void main(final String[] args) {
    final Map<Character, Character> closeToOpen = new HashMap<Character, Character>();
    closeToOpen.put('}', '{');
    closeToOpen.put(']', '[');
    closeToOpen.put(')', '(');
    closeToOpen.put('>', '<');

    final String[] testSet = new String[] { "abcdefksdhgs", "[{aaa<bb>dd}]<232>", "[ff{<gg}]<ttt>", "{<}>" };
    for (final String test : testSet) {
        System.out.println(test + "  ->  " + isBalanced(test, new LinkedList<Character>(), closeToOpen));
    }
}

OUTPUT:

abcdefksdhgs  ->  true
[{aaa<bb>dd}]<232>  ->  true
[ff{<gg}]<ttt>  ->  false
{<}>  ->  false

Note that i have imported the following classes:

import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;

Answer 3

 public static boolean isBalanced(String str) {
    if (str.length() == 0) {
        return true;
    }
    if (str.contains("()")) {
        return isBalanced(str.replaceFirst("\\(\\)", ""));
    }

    if (str.contains("[]")) {
        return isBalanced(str.replaceFirst("\\[\\]", ""));
    }
    if (str.contains("{}")) {
        return isBalanced(str.replaceFirst("\\{\\}", ""));
    } else {
        return false;
    }
}

Answer 4

PHP Solution to check balanced parentheses

<?php
/**
 * @param string $inputString
 */
function isBalanced($inputString)
{
    if (0 == strlen($inputString)) {
        echo 'String length should be greater than 0';
        exit;
    }

    $stack = array();
    for ($i = 0; $i < strlen($inputString); $i++) {
        $char = $inputString[$i];
        if ($char === '(' || $char === '{' || $char === '[') {
            array_push($stack, $char);
        }
        if ($char === ')' || $char === '}' || $char === ']') {
            $matchablePairBraces = array_pop($stack);
            $isMatchingPair = isMatchingPair($char, $matchablePairBraces);
            if (!$isMatchingPair) {
                echo "$inputString is NOT Balanced." . PHP_EOL;
                exit;
            }
        }
    }
    echo "$inputString is Balanced." . PHP_EOL;
}

/**
 * @param string $char1
 * @param string $char2
 * @return bool
 */
function isMatchingPair($char1, $char2)
{
    if ($char1 === ')' && $char2 === '(') {
        return true;
    }
    if ($char1 === '}' && $char2 === '{') {
        return true;
    }
    if ($char1 === ']' && $char2 === '[') {
        return true;
    }
    return false;
}

$inputString = '{ Swatantra (() {} ()) Kumar }';
isBalanced($inputString);
?>

Answer 5

First, to your original question, just be aware that if you're working with very long strings, you don't want to be making exact copies minus a single letter each time you make a function call. So you should favor using indexes or verify that your language of choice isn't making copies behind the scenes.

Second, I have an issue with all the answers here that are using a stack data structure. I think the point of your assignment is for you to understand that with recursion your function calls create a stack. You don't need to use a stack data structure to hold your parentheses because each recursive call is a new entry on an implicit stack.

I'll demonstrate with a C program that matches ( and ). Adding the other types like [ and ] is an exercise for the reader. All I maintain in the function is my position in the string (passed as a pointer) because the recursion is my stack.

/* Search a string for matching parentheses.  If the parentheses match, returns a
 * pointer that addresses the nul terminator at the end of the string.  If they
 * don't match, the pointer addresses the first character that doesn't match.
 */
const char *match(const char *str)
{
        if( *str == '\0' || *str == ')' ) { return str; }
        if( *str == '(' )
        {
                const char *closer = match(++str);
                if( *closer == ')' )
                {
                        return match(++closer);
                }
                return str - 1;
        }

        return match(++str);
}

Tested with this code:

    const char *test[] = {
            "()", "(", ")", "", "(()))", "(((())))", "()()(()())",
            "(() ( hi))) (())()(((( ))))", "abcd"
    };

    for( index = 0; index < sizeof(test) / sizeof(test[0]); ++index ) {
            const char *result = match(test[index]);

            printf("%s:\t", test[index]);
            *result == '\0' ? printf("Good!\n") :
                    printf("Bad @ char %d\n", result - test[index] + 1);
    }

Output:

(): Good!
(:  Bad @ char 1
):  Bad @ char 1
:   Good!
(())):      Bad @ char 5
(((()))):   Good!
()()(()()): Good!
(() ( hi))) (())()(((( )))):    Bad @ char 11
abcd:       Good!

Answer 6

Balanced Parenthesis (JS)

The more intuitive solution is to use stack like so:

function isBalanced(str) {
  const parentesis = {
    '(': ')',
    '[': ']',
    '{': '}',
  };
  const closing = Object.values(parentesis);
  const stack = [];

  for (let char of str) {
    if (parentesis[char]) {
      stack.push(parentesis[char]);
    } else if (closing.includes(char) && char !== stack.pop()) {
      return false;
    }
  }
 
  return !stack.length;
}

console.log(isBalanced('{[()]}')); // true
console.log(isBalanced('{[(]]}')); // false
console.log(isBalanced('([()]'));  // false

And using recursive function (without using stack), might look something like so:

function isBalanced(str) {
  const parenthesis = {
    '(': ')',
    '[': ']',
    '{': '}',
  };

  if (!str.length) {
    return true;
  }

  for (let i = 0; i < str.length; i++) {
    const char = str[i];

    if (parenthesis[char]) {
      for (let j = str.length - 1; j >= i; j--) {
        const _char = str[j];

        if (parenthesis[_char]) {
          return false;
        } else if (_char === parenthesis[char]) {
          return isBalanced(str.substring(i + 1, j));
        }
      }
    } else if (Object.values(parenthesis).includes(char)) {
      return false;
    }
  }
  return true;
}

console.log(isBalanced('{[()]}')); // true
console.log(isBalanced('{[(]]}')); // false
console.log(isBalanced('([()]'));  // false

* As @Adrian mention, you can also use stack in the recursive function without the need of looking backwards