Check for Valid Parentheses in java

java algorithm math recursion parentheses

10,298

Solution 1

have you tried replacing

validParen(input);

with

return validParen(input);

? Otherwise this line doesn't really do much ;)

From the call order point of view, it doesn't matter if you call method a() from a() or from anywhere else. Let's look at a simple example

public int getOne() {
   return 1;
}

public int getA(int a) {
   /*
   what you do here is call getOne(). The method will be called,
   and it will produce some result, but this result will not be persisted
   in any way, you will just go to the next line where the original a's
   value will be returned
    */
   getOne(); 
   return a;


}

Is this case a bit clearer? Obviously if you call getA(2), 2 will be returned, not 1, even though getOne() is called internally - it's result is ignored.

Solution 2

As said in the comment, you can consider use a stack. When current character is ( or { or [, put them in the stack. When current character is ) or } or ], check if there is the counterpart in the stack(for a valid input, it must exist) and pop it.

import java.util.Stack;

class Solution {

    public boolean validParen(String input) {

        if (input.isEmpty()) {
            return true;
        } else {
            Stack<Character> stack = new Stack<>();
            for (int i = 0; i < input.length(); i++) {
                char current = input.charAt(i);
                if (current == '(' || current == '[' || current == '{') {
                    stack.push(current);
                } else {
                    if(stack.isEmpty()) {
                          return false;
                    }
                    char peekChar = stack.peek();
                    if ((current == ')' && peekChar != '(')
                            || (current == '}' && peekChar != '{')
                            || (current == ']' && peekChar != '[')) {
                        return false;  // for a valid input, a close brackets must have an open brackets
                    } else {
                        stack.pop();
                    }
                }
            }
            return true; 
        }
    }


    public static void main(String[] args) {
        Solution sol = new Solution();
        System.out.println(sol.validParen(""));
        System.out.println(sol.validParen("()"));
        System.out.println(sol.validParen("()[]{}"));
        System.out.println(sol.validParen("(]"));
        System.out.println(sol.validParen("([)]"));
        System.out.println(sol.validParen("{[]}"));
    }

}

Solution 3

import java.util.Stack;

public class ValidBracesTest {

public static void main(String[] args) {

    System.out.println(isValid("( [ { } ] )".toCharArray())); // valid
    System.out.println(isValid("([{}])".toCharArray())); // valid
    System.out.println(isValid("([)]".toCharArray())); // invalid
    System.out.println(isValid("(}".toCharArray())); // invalid

}

public static boolean isValid(char[] charArray) {
    Stack<Character> container = new Stack<Character>();

    for (char c : charArray) {

        if (c == ' ') {
            continue;
        }

        if (c == '(' || c == '{' || c == '[') {
            container.push(c);
        } else if (c == ')' && container.peek() == '(' 
                || (c == '}' && container.peek() == '{')
                || (c == ']' && container.peek() == '[')) {
            container.pop();
        } else {
            return false;
        }

    }

    return container.isEmpty();
}

}

10,298

mendokusai

Updated on June 04, 2022

Comments

mendokusai almost 2 years

I'm trying to find out if the given input is a valid parentheses or not. The input string is made of '(', ')', '{', '}', '[' and ']' .
An input string is valid if:

1.Open brackets must be closed by the same type of brackets.
2.Open brackets must be closed in the correct order. 3. empty strings are valid

However my code below using recursion is not working on the valid cases. It is suppose to go to the base case (when input is "") but instead goes to the return statement after the for loop.

class Solution {

    public boolean validParen(String input) {

        if(input.isEmpty()) {
            return true;
        }

        else {
            for (int i = 0; i < input.length() - 1; i++) {
                if ((input.charAt(i) == '(' && input.charAt(i + 1) == ')') ||
                        (input.charAt(i) == '{' && input.charAt(i + 1) == '}') ||
                        (input.charAt(i) == '[' && input.charAt(i + 1) == ']')) {
                    input = input.substring(0, i) + input.substring(i + 2);
                    System.out.println("Input is " + input);
                    validParen(input);
                }
            }
            return false;
        }
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        //System.out.println(sol.validParen("")); 
        //System.out.println(sol.validParen("()")); // returns false for some reason 
        //System.out.println(sol.validParen("()[]{}")); // returns false for some reason
        //System.out.println(sol.validParen("(]"));
        //System.out.println(sol.validParen("([)]"));
        //System.out.println(sol.validParen("{[]}")); // returns false for some reason
    }
}

Mena almost 6 years

Not going into details, but have you considered using stacks (in the sense of LIFO collections, not the old Stack) instead?

mendokusai almost 6 years

Doesn't validParen(input) eventually reach the base case and return true? I don't understand how return makes a difference?
Jan Ossowski almost 6 years

think about it. you call a method, ignore it's outcome (doesn't matter if it returns true or false, it is ignored, as you don't "pass it on" in a return statement or assign it to a variable), and pass straight to the next line which is return false; Try to "debug" it in your head and think carefully what happens. Yes, maybe true will be returned, but not from your original method, but the one that is called within. this result is not taken into account in any way. thats essentialy the same as if you called int a = 1; a+1; // there is an addition here, but it's result is ignored. return a;
Jan Ossowski almost 6 years

let me edit my answer, because comments are not that comfortable to use
mendokusai almost 6 years

I'm sorry but I'm a beginner and having a hard time understanding this. Do you mean that inside that if statement I'm returning nothing even though it is recursively calling a method that eventually reaches a return statement?
Obicere almost 6 years

If the condition on line 15 is false, you can immediately return false. Otherwise, this is a great solution.
Jan Ossowski almost 6 years

of course. Look at my example. return; will not exit the whole call stack. It will just exit "1 level up" and the code block that called it will continue. In this case the validParen() method will continue to run (it doesnt matter that it's the same method, from the call stack point of view you are in a totally different place), and as it happens the next line in it is "return false;"
Andrey Tyukin almost 6 years

The solution is OK, but the introductory sentence is really confusing. For example, in (((())))[[[]]], the first character has nothing whatsoever to do with the character at length - 1.
mendokusai almost 6 years

I understand using a stack is a better solution but my solution will work on nested parentheses since it checks for the most nested pair and removes it and continues this process until the input is an empty string.
Jan Ossowski almost 6 years

@ken24ny always happy to help, conciser accepting the answer if you think that answers your question. To be honest I'm not sure that is the only problem with your code, because the usage of subString and those strange inclusive/exclusive index rules always confuses me, but that's the main problem i saw
Obicere almost 6 years

@ken24ny this works on nested parentheses as well. Stacks do not function like sets so there can be duplicate entries. Each level of nested parentheses visited pushes an extra opening symbol onto the stack. I just tested it and it works fine on an input like ((((())))).
Obicere almost 6 years

@NengLiu actually, going back to your original solution, that was invalid. Without the return false that you added, the input failed on expressions like ([}]), since it would skip the } character and eventually the stack would be empty!
xingbin almost 6 years

@Obicere You are right, I need push } in the stack if it does not match.
Jan Ossowski almost 6 years

I wonder why I'm being downvoted :) Is it because I tried to point out where the problem lies instead of giving out "the best solution" on a plate? Meh, the community
Andrey Tyukin almost 6 years

I can explain the downvote in detail. This doesn't solve the problem. Even if you add a return, OP's solution stays tail-recursive. Therefore, the function can be rewritten in a way that requires no unbounded call stack. The method itself contains no data structures that could hold an unbounded amount on information. Therefore, it cannot possibly work, no matter how you permute the symbols inside the method body.
Jan Ossowski almost 6 years

Since this is obviously a simple recursion exercise, not a commercial code, I don't see how "unbound amount of information" is a limiter. This code will work, provided there is no indexing mistake in the subString() methods called.
Andrey Tyukin almost 6 years

@JanOssowski What does it have to do with "commercial code"? The code is fundamentally broken beyond repair, and cannot work even on the simplest examples (not even theoretically). If you want, you can try to repair OP's code by adding returns, I bet I can break it with an example shorter than 20 symbols.
Jan Ossowski almost 6 years

Dude I don't know what your problem is, but this code DOES work. Enjoy
Andrey Tyukin almost 6 years

@JanOssowski Alright. It uses the new String glued from parts of the original String as a data structure that can hold unbounded amount of information. That's somewhat inefficient, but it works. I admit defeat^^ Here's your (+1) ;)
Jan Ossowski almost 6 years

Hah! :P It is obviously not efficient, but since the OP has difficulties understanding simple call order, I sincerely think my answer is more useful to him than serving the perfect solution using data structure he probably never heard of ;) Enjoy your day
Marcos Barbero almost 4 years

Please, consider explaining your code when you answer a question.
Disha Gajera over 2 years

This solution is not working for "[" this test case