Basic Recursion, Check Balanced Parenthesis

balanced parentheses python recursion
balanced parentheses without stack
check balanced parentheses recursive
balanced parentheses java recursion
java program to check balanced parentheses using stack
program to check balanced parentheses in c
balanced parentheses recursion scala
regular expression balanced parentheses

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?

There are many ways to do this, but the simplest algorithm is to simply process forward left to right, passing the stack as a parameter

FUNCTION isBalanced(String input, String stack) : boolean
  IF isEmpty(input)
    RETURN isEmpty(stack)
  ELSE IF isOpen(firstChar(input))
    RETURN isBalanced(allButFirst(input), stack + firstChar(input))
  ELSE IF isClose(firstChar(input))
    RETURN NOT isEmpty(stack) AND isMatching(firstChar(input), lastChar(stack))
      AND isBalanced(allButFirst(input), allButLast(stack))
  ELSE
    ERROR "Invalid character"

Here it is implemented in Java. Note that I've switched it now so that the stack pushes in front instead of at the back of the string, for convenience. I've also modified it so that it just skips non-parenthesis symbols instead of reporting it as an error.

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 stack) {
    return
        input.isEmpty() ?
            stack.isEmpty()
        : isOpen(input.charAt(0)) ?
            isBalanced(input.substring(1), input.charAt(0) + stack)
        : isClose(input.charAt(0)) ?
            !stack.isEmpty() && isMatching(stack.charAt(0), input.charAt(0))
              && isBalanced(input.substring(1), stack.substring(1))
        : isBalanced(input.substring(1), stack);
}

Test harness:

    String[] tests = {
        "()[]<>{}",
        "(<",
        "]}",
        "()<",
        "(][)",
        "{(X)[XY]}",
    };
    for (String s : tests) {
        System.out.println(s + " = " + isBalanced(s, ""));
    }

Output:

()[]<>{} = true
(< = false
]} = false
()< = false
(][) = false
{(X)[XY]} = true

Check for balanced parenthesis without using stack, Generate all strings of n pairs of balanced parentheses. Option One: Enumerate all strings of n copies of ( and n copies of ) and, for each, check whether One simple approach is to compute the mirror of the original tree, then determine� Check for balanced parentheses in an expression 12-04-2010 Given an expression string exp, write a program to examine whether the pairs and the orders of “{“, “}”, “(“, “)”, “[“, “]” are correct in exp.

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!

[PDF] Recursion Problem Solutions: Group A, 03 C | How to check balanced parenthesis - Duration: 6:30. Yusuf Shakeel 12,685 views � 6:30 Duration: 7:21 Posted: Dec 10, 2015 If k = 1, then we will simply keep a count variable c = 0, whenever we encounter an opening parentheses we will increment c and whenever we encounter a closing parentheses we will reduce the count of c, At any stage we shouldn’t have c < 0 and at the end we must have c = 0 for string to be balanced.

CSC180: Matching Parentheses Recursively, Well this is what i have so far. /** * Checks if the expression is balanced or not, making use of recursion. * @param in Expression to be checked. */� Check if the given push and pop sequences of Stack is valid or not; Check if the bracket sequence can be balanced with at most one change in the position of a bracket | Set 2; Reverse substrings between each pair of parenthesis; Find if an expression has duplicate parenthesis or not; Identify and mark unmatched parenthesis in an expression; Calculate weight of parenthesis based on the given conditions; Infix to Postfix using different Precedence Values for In-Stack and Out-Stack; Find

 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;
    }
}

Challenge 2: Balance Parenthesis, Now we can look at simple Algorithm for Parentheses balancing with Recursively checks if string contains matching amount of opening and� Recursively checks if string contains matching amount of opening and closing parentheses by calling isBalanced() on the string without first element. Expectancy of parentheses in the string is kept in a kind of balance indicator numOfPositions – positives indicate amount of needed ‘)’ and negatives amount of needed ‘ (‘.

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

java, Here is a simple recursive solution which illustrates the clarity of pattern matching : def balance(chars: List[Char]): Boolean = { def go(cs: List[Char], level: Int):� I was thinking of counting the number of times each outer or inner parenthesis pops up in a string, but then it would miss cases like this "()())()(" or this ")(". My instructor had examples of recursion that solved factorials and calculated numbers of the fibonacci sequence, but she never really went over solving other types of problems.

Parentheses balancing Algorithm with recursion in Scala– J2eeDev, A deep dive into the generation of balanced parentheses, inspired by a that inspired the post to begin with, and a basic recursive solution for it. parentheses count for i in range(1, 2 * n + 1): # If we are checking the very� I was able to finish it without a problem using stacks, but recursion is giving me a really hard time since I dont know how to check for two matching pairs of parentheses. Well this is what i have so far. /** * Checks if the expression is balanced or not, making use of recursion. * @param in Expression to be checked.

Checking for balanced parentheses, Simple Balanced Parentheses�. We now turn our attention to using stacks to solve real computer science problems. You have no doubt written arithmetic� Basic Recursion, Check Balanced Parenthesis (8) @indiv's answer is nice and enough to solve the parentheses grammar problems. If you want to use stack or do not want to use recursive method you can look at the python script on github. It is simple and fast.

Generating All Balanced Parentheses: A Deep Dive Into An , Category: C Programming Data Structure Stacks Programs Tags: balanced parentheses using stack in c, bracket matching using stack in c, c data structures, c stack programs, Check Balanced Expression In C, Check for balanced parentheses in an expression, check nesting of parentheses using stack, parenthesis matching using stack in data structure

Comments
  • if the question is check if parenthesis are balanced using recursion, you don't want to explicit pass a stack as an arg of the recursive function
  • This ternary nesting makes this really hard to read. This isn't code golf. You can use explicit flow of control. .
  • +1 for showing how to utilize the call stack instead of having an explicit one. I thought it was quite strange that no one had provided an answer showing that yet... Still, this would have looked better in Lisp ;)
  • @Sid: When I run the test program on ())(, I get "Bad @ char 3", which looks good to me. ideone.com/e.js/VBM8IU
  • +1, though it would be good to have a (non-recursive) wrapper function is_balanced that delegates to this one. The whole "returns a pointer to the first mismatch" thing is really an implementation detail that callers shouldn't have to understand.
  • Add some explanation with answer for how this answer help OP in fixing current issue
  • This is wrong solution! You can't assume first mid will perfect match to other mid! Your solution would work only for (()), ((())), (((())))...and so on...What about ((())()())? It's perfect idea to use Stack but you keep pushing only opening braces and whenever closing brace encounter, you pop from stack. If stack is empty then it's an invalid string. At the end of the string you make sure that stack is empty. If not it's invalid string else valid string.