0

Hi I'm working on the implementation of a boolean method to check if an expression has balanced parentheses using recursion. I cant figure out how to check if two elements of a given expression match i.e ( ).
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. 
     */
     public static boolean recIsBalanced(String in)
    {   
        if(in.isEmpty())
            return true;

        if(isOpen(in.charAt(0)))
        {
            return recIsBalanced(in.substring(1));
        }

        if(isClose(in.charAt(0)))
            return recIsBalanced(in.substring(1));
        else
            return false;

    }

    //Static parameters to check whether the character is open or a close parentheses
    static String open  = "([{";
    static String close = ")]}";

    private static boolean isOpen(char ch) 
    {
        return open.indexOf(ch) != -1;
    }
    private static boolean isClose(char ch) 
    {
        return close.indexOf(ch) != -1;
    }
    private static boolean isMatching(char chOpen, char chClose) 
    {
        return open.indexOf(chOpen) == close.indexOf(chClose);
    }
2
Contributors
1
Reply
16
Views
4 Years
Discussion Span
Last Post by chuck.kollars
0

While it's often true that with recursion the actual nugget of logic is surprisingly small, my style sense is you've got it TOO small this time. Have logic to find both the opening and closing markers, then recursively call yourself only once [not separate recursive calls for open(...) and close(...)] with the substring between the markers. The arguments to "substring(...)" should be variables that pull out what's inside the markers, not fixed '1'. (The '1' seems to assume that if a marker was found anywhere in the string, then it's valid to remove only the first character. ???) I see several other problems, including: any marker is adequate to close any other, so ...(...]... would be valid; there's no provision for parsing around or excising comments, so ...(.../***...)...***/... would be valid; and unless you use "regular expression" syntax, Javascript "indexOf(...)" is going to look for the exact_sequence of characters you specify rather than any one of them, so only things like ...([{... would be found (not things like ...(...[...{... or ...(...).

Edited by chuck.kollars: try again to get asterisk to show literally

This topic has been dead for over six months. Start a new discussion instead.
Have something to contribute to this discussion? Please be thoughtful, detailed and courteous, and be sure to adhere to our posting rules.