Checking for matching delimiters using multiple stacks or counters

Question

I know my algorithm is very naive and slow for this problem. I would like to learn how to improve upon it?

import java.util.Stack;

/**
 * Created by mona on 3/12/16.
 */
public class ValidParanthesis {
    public static boolean isValid(String s){
        char[] charArr=s.toCharArray();
        Stack<Character> s1= new Stack<>();
        Stack<Character> s2= new Stack<>();
        Stack<Character> s3= new Stack<>();
        Stack<Character> s4= new Stack<>();
        Stack<Character> s5= new Stack<>();
        Stack<Character> s6= new Stack<>();

        for (int i=0; i<charArr.length; i++){
            if (charArr[i]=='{'){
                s1.push('{');
            }
            else if (charArr[i]=='}'){
                s2.push('}');
            }
            else if (charArr[i]=='('){
                s3.push('(');
            }
            else if (charArr[i]==')'){
                s4.push(')');
            }
            else if (charArr[i]=='{'){
                s5.push('{');
            }
            else if (charArr[i]=='}'){
                s6.push('}');
            }

        }

        if (s1.size()==s2.size() && s3.size()==s4.size() && s5.size()==s6.size()){
            return true;
        }
        return false;
    }
    public static void main(String[] args){
        String s="][{}";
        System.out.println(isValid(s));
    }
}

I assume this one is better, right? are there faster methods than the below?

import java.util.Stack;

/**
 * Created by mona on 3/12/16.
 */
public class ValidParanthesis {
    public static boolean isValid(String s){

        if (s.length()==1 || s==null){
            return true;
        }

        int cnt1=0,cnt2=0,cnt3=0,cnt4=0,cnt5=0,cnt6=0;
        for (int i=0; i<s.length(); i++){
            if (s.charAt(i)=='{'){
                cnt1++;
            }
            else if (s.charAt(i)=='}'){
                cnt2++;
            }
            else if (s.charAt(i)=='('){
                cnt3++;
            }
            else if (s.charAt(i)==')'){
                cnt4++;
            }
            else if (s.charAt(i)=='['){
                cnt5++;
            }
            else if (s.charAt(i)==']'){
                cnt6++;
            }
        }
        return ((cnt1==cnt2) && (cnt3==cnt4) && (cnt5==cnt6));
    }
    public static void main(String[] args){
        String s="][{";
        System.out.println(isValid(s));
    }
}

Answer 1

Code

I would change

for (int i=0; i<charArr.length; i++){ 
    ...
}

to

for (char c : s.toCharArray()) {
    ...
}

Algorithm

Everything you need is only one stack. Keep scanning the input string one character at a time, and do the following:

• If the stack is empty, just push the character to it.
• If the top of the stack "matches" the current character, ignore the input character and pop the matching character. For example, if the current character is ], the stack matches if the top element is [; same goes for ) and }.
• If the top of the stack does not match the current character, push the current character to it.
• After you have processed all the characters of the input string, the parenthesis structure is balanced if and only if the stack ends up empty; otherwise, you will have some "unmatched" characters in it.

I think you need something like this:

import java.util.ArrayDeque;
import java.util.Deque;

public class ValidParenthesis {

    public static boolean isValid(String s){
        Deque<Character> stack = new ArrayDeque<>();

        for (char c : s.toCharArray()) {
            if (stack.isEmpty()) {
                switch (c) {
                    case ')':
                    case '}':
                    case ']':
                        return false;
                }

                stack.addLast(c);
                continue;
            } 

            char topChar = stack.getLast();

            switch (c) {
                case '(':
                    stack.addLast('(');
                    break;

                case '{':
                    stack.addLast('{');
                    break;

                case '[':
                    stack.addLast('[');
                    break;

                case ')':
                    if (topChar == '(') {
                        stack.removeLast();
                    } else {
                        return false;
                    }

                    break;

                case '}':
                    if (topChar == '{') {
                        stack.removeLast();
                    } else {
                        return false;
                    }

                    break;

                case ']':
                    if (topChar == '[') {
                        stack.removeLast();
                    } else {
                        return false;
                    }

                    break;
            }
        }

        return stack.isEmpty();
    }

    public static void main(String[] args){
        String s="([{(){}}])";
        System.out.println(isValid(s));
    }
}

Also, if you need to validate the parenthesis structure intermixed with other text (for example, when validating foo(char[]){...}, just ignore all the other characters.

Edit

Whenever you are pushing a closing parenthesis, bracket or brace, if the stack is empty, your input string is not balanced. Also, in case the stack is not empty, and if the top of it is not a corresponding opening symbol, your input string cannot be balanced either.

Answer 2

You could tighten the design a bit:

public class Main {

    static Map<Character, Character> matchingParen;

    static {
        matchingParen = new HashMap<>();
        matchingParen.put(')', '(');
        matchingParen.put(']', '[');
        matchingParen.put('}', '{');
    }

    public static void main(String[] args) {
        String parens = "[]{}";
        System.out.println(isValidParens(parens));

    }

    private static boolean isValidParens(String parens) {
        Deque<Character> stack = new ArrayDeque<>();
        boolean hasErrors = false;
        for (int i = 0; i < parens.length() && !hasErrors; i += 1) {
            char c = parens.charAt(i);
            switch (c) {
                case '(':
                case '[':
                case '{':
                    stack.addLast(c);
                    break;
                case ')':
                case ']':
                case '}':
                    if (!stack.isEmpty() && stack.getLast() == matchingParen.get(c)) {
                        stack.removeLast();
                    } else hasErrors = true;
                default:
                    break;
            }
        }
        return !hasErrors;
    }
}