CareerCup

The idea here is to use a stack. Since the parenthesis that opens last must close first, last in first out.

Step 1: Begin iterating over the given string character by character.

Step 2: If your current character is an opening parenthesis then push onto the stack.

Step 3: If your current character is a closing parenthesis then pop from the stack and validate if the current character matches appropriately with the popped element.

ex - if currentChar=']' then popped element should be '['. If they don't match or your stack is empty and there is nothing to pop then return false right away.

Step 4: By the end of the string your stack is empty then your string is valid and we return true.

Extension:

Most of the steps would remain the same, except that we could initially save all the values (NOT Keys) of the Map into a Set.

Now we could perform the earlier steps and to identify if the current character is an opening of a parenthesis we simply query the key in the given map & to identify the current character represents the closure of a parenthesis we query from our Set.
I felt the validation in Step 3 was a little tricky.

Time complexity is O(n)
Space complexity is O(m+n)
n - size of the string
m - number of elements in the given map

c++, implement

bool verify(string& str) {
	stack<char> s;
	int i;

	for (i = 0; i < str.size(); i++) {
		if (str[i] == '<' || str[i] == '[' || str[i] == '(') {
			s.push(str[i]);
		} else if (str[i] == '>') {
			if (s.size() == 0 || s.top() != '<') return false;
			s.pop();
		} else if (str[i] == ']') {
			if (s.size() == 0 || s.top() != '[') return false;
			s.pop();
		} else if (str[i] == ')') {
			if (s.size() == 0 || s.top() != '(') return false;
			s.pop();
		}
	}
	if (s.size() > 0) return false;

	return true;
}

//When using the hashmap. Have two pointers (one at the right end of the string(j), the other at the left end of the string(i)). On, the left end, if you encounter a '(','<','[' ,look up the matching key for i in the hashmap and retreive the corresponding value. See if the character at j matches the retrieved value.

import java.util.Stack;
import java.util.Map;
import java.util.HashMap;
import java.util.Set;
import java.util.HashSet;

public class ValidateParen
{
  public static boolean isValid(String s, Map<Character, Character> parens)
  {
    Set<Character> close = new HashSet<>();
    close.addAll(parens.values());
    Stack<Character> stack = new Stack<>();
    for (char c : s.toCharArray())
    {
      if (parens.containsKey(c))
      {
        stack.push(parens.get(c));
      }
      else if (close.contains(c))
      {
        if (stack.isEmpty() || stack.pop() != c)
        {
          return false;
        }
      }
    }
    return stack.isEmpty();
  }
}

Sample on java (it even will show the position of error)

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class TestParenthesis {

    public static void main(String[] args) {
        String text = "<sjd>iua[dsds(d]<sa)sa<sasa>>sasasa";
        System.out.println(checkSimple(text, '<', '>'));
        
        Map<Character,Character> mp= new HashMap<Character,Character>();
        mp.put('<', '>');
        mp.put('(', ')');
        mp.put('[', ']');
        mp.put('{', '}');
        
        System.out.println(checkMap(text, mp));
    }

    public static boolean checkSimple(String text, char begin, char end) {
        char[] textArray = text.toCharArray();
        int firstError = -1;
        int cnt = 0;
        for (int i = 0; i < textArray.length; i++) {
            char a = textArray[i];
            if (a == begin) {
                cnt++;
                if (cnt == 1) {
                    firstError = i;
                }
            } else if (a == end) {
                cnt--;
                if (cnt < 0) {
                    firstError = i;
                    break;
                }
            }
        }

        if (cnt != 0 && firstError >= 0) {
            System.out.println("Error at position " + (firstError+1));
            return false;
        }
        return true;
    }

    public static boolean checkMap(String text, Map<Character, Character> map) {
        // making set of ends
        Set<Character> ends = new HashSet<Character>();
        ends.addAll(map.values());
        char[] textArray = text.toCharArray();
        // position of error
        int firstError = -1;
        // here will store ends which we expect
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < textArray.length; i++) {
            Character a = map.get(textArray[i]);
            if (a != null) {
                // pushing into stack expected end
                stack.push(a);
                if (stack.size() == 1) {
                    // if this is first element at stack we should keep it's position as suspect for error
                    firstError = i;
                }
            } else if (ends.contains(textArray[i])) {
                if (stack.isEmpty() || textArray[i] != (char) stack.pop()) {
                    firstError = i;
                    break;
                }
            }
        }
        if (firstError >= 0) {
            System.out.println("Error at position " + (firstError+1));
            return false;
        }
        return true;
    }
}

On Java:

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;
import java.util.Stack;

public class TestParenthesis{

    public static void main(String[] args) {
        String text = "<sjd>iua[dsds(d]<sa)sa<sasa>>sasasa";
        System.out.println(checkSimple(text, '<', '>'));
        
        Map<Character,Character> mp= new HashMap<Character,Character>();
        mp.put('<', '>');
        mp.put('(', ')');
        mp.put('[', ']');
        mp.put('{', '}');
        
        System.out.println(checkMap(text, mp));
    }

    public static boolean checkSimple(String text, char begin, char end) {
        char[] textArray = text.toCharArray();
        int firstError = -1;
        int cnt = 0;
        for (int i = 0; i < textArray.length; i++) {
            char a = textArray[i];
            if (a == begin) {
                cnt++;
                if (cnt == 1) {
                    firstError = i;
                }
            } else if (a == end) {
                cnt--;
                if (cnt < 0) {
                    firstError = i;
                    break;
                }
            }
        }

        if (cnt != 0 && firstError >= 0) {
            System.out.println("Error at position " + (firstError+1));
            return false;
        }
        return true;
    }

    public static boolean checkMap(String text, Map<Character, Character> map) {
        // making set of ends
        Set<Character> ends = new HashSet<Character>();
        ends.addAll(map.values());
        char[] textArray = text.toCharArray();
        // position of error
        int firstError = -1;
        // here will store ends which we expect
        Stack<Character> stack = new Stack<Character>();
        for (int i = 0; i < textArray.length; i++) {
            Character a = map.get(textArray[i]);
            if (a != null) {
                // pushing into stack expected end
                stack.push(a);
                if (stack.size() == 1) {
                    // if this is first element at stack we should keep it's position as suspect for error
                    firstError = i;
                }
            } else if (ends.contains(textArray[i])) {
                if (stack.isEmpty() || textArray[i] != (char) stack.pop()) {
                    firstError = i;
                    break;
                }else{
                    firstError = -1;
                }
            }
        }
        if (firstError >= 0) {
            System.out.println("Error at position " + (firstError+1));
            return false;
        }
        return true;
    }
}

Also it will output the error position.

public static bool ParenthesisValidation(string input)
        {
            //Program Call
            //string input = "<[((kskfhdbh7)";
            //var output = ParenthesisValidation(input);
            var charToMatch = new List<Tuple<char, char>>()
            {
                new Tuple<char, char>('(', ')'),
                new Tuple<char, char>('<', '>'),
                new Tuple<char, char>('[', ']')
            };
            foreach (var pair in charToMatch)
            {
                if (input.Contains(pair.Item1) && input.Contains(pair.Item2))
                {
                    var item1Count = input.Where(c => c == pair.Item1).ToList().Count();
                    var item2Count = input.Where(c => c == pair.Item2).ToList().Count();
                    if (item1Count != item2Count)
                        return false;
                }
            }
            return true;
        }

public static bool ParenthesisValidation(string input)
        {
            //Program Call
            //string input = "<[((kskfhdbh7)";
            //var output = ParenthesisValidation(input);
            var charToMatch = new List<Tuple<char, char>>()
            {
                new Tuple<char, char>('(', ')'),
                new Tuple<char, char>('<', '>'),
                new Tuple<char, char>('[', ']')
            };
            foreach (var pair in charToMatch)
            {
                if (input.Contains(pair.Item1) && input.Contains(pair.Item2))
                {
                    var item1Count = input.Where(c => c == pair.Item1).ToList().Count();
                    var item2Count = input.Where(c => c == pair.Item2).ToList().Count();
                    if (item1Count != item2Count)
                        return false;
                }
            }
            return true;
        }

Is this example valid? "(<str)>"

/* package whatever; // don't place package name! */

import java.util.*;
import java.lang.*;
import java.io.*;

/* Name of the class has to be "Main" only if the class is public. */
class Main
{
	public static HashMap<Character,Character> paramMap=new HashMap<Character, Character>();
	public static void main (String[] args) throws java.lang.Exception
	{
		
		paramMap.put('<','>');
		paramMap.put('{','}');
		paramMap.put('[',']');
		paramMap.put('(',')');
		paramMap.put('@','&');
		
		String str="@sasas<sd[qw(1)qw]sd{>&";
		checkValidString(str);
	
	}
	
	public static void checkValidString(String str){
		char[] strchar=str.toCharArray();
		Stack st = new Stack();
		for(int i=0;i<str.length();i++){
			if(!isAlpha(strchar[i])){
				if(paramMap.containsKey(strchar[i]))
					st.push(strchar[i]);
				else{
				  char top=(char)st.pop();
				  if(!paramMap.get(top).equals(strchar[i])){
				    System.out.println("Invalid");
				    break;
				  }
				    
				}  
			}
		}
		if(st.empty()){
			System.out.println("Valid!");
		}
	}
	
	public static boolean isAlpha(char ch){
		if((ch >= 'a' && ch <= 'z') || (ch >= 'A' && ch <= 'Z') || (ch >= '0' && ch <= '9'))
		  return true;
		return false;  
	}

}

public class ValidString {
    private static final Map<Character, Character> brackets = new HashMap<>();

    static {
        brackets.put('(', ')');
        brackets.put('[', ']');
        brackets.put('<', '>');
    }

    public boolean isValid(String input) {
        if (input == null || input.isEmpty()) {
            return true;
        }

        char[] elements = input.toCharArray();
        Stack<Character> stack = new Stack<>();
        Set<Character> openBrackets = brackets.keySet();
        Set<Character> closeBrackets = new HashSet<>(brackets.values());

        for(char element : elements) {
            if (openBrackets.contains(element)) {
                stack.push(element);
            } else if (closeBrackets.contains(element)) {
                Character openElement;

                if (stack.isEmpty() || (openElement = stack.pop()) == null) {
                    return false; // no valid open bracket
                } else {
                    Character closeElement = brackets.get(openElement);
                    if (closeElement == null) {
                        return false; // unknown close bracket
                    } else if (!closeElement.equals(element)) {
                        return false;  // unexpected close bracket
                    }
                }
            } else {
                // do nothing
            }
        }

        return stack.isEmpty();
    }

    public static void main(String[] args) {
        ValidString test = new ValidString();
        System.out.println(test.isValid("<((([dada+-dad])))>"));
    }
}

bool isValid(string s){

	stack<char> st;
	
	for(int i = 0; i < s.length(); i++){
		if(s[i] == '<' || s[i] == '(' || s[i] == '['){
			st.push(s[i]);
		}
		else{
		 if(!st.empty() && ((s[i] == '>' && st.top() == '<') || (s[i] == ')' && st.top() == '(') || (s[i] == ']' && st.top() == '[')))
			{
				st.pop();
			}
			else if(isalpha(s[i]) || ispunct(s[i]) || (s[i] >= '0' && s[i] <= '9')){
				continue;
			}
			else{
				return false;
			}	
		}
	}
	
	return st.empty();
}

import java.util.*;

public class App {

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

        System.out.println(isValid("<<[>]>"));
    }

    public static boolean isValid(String s) {
        Stack<Character> stack = new Stack();
        for(Character c:s.toCharArray()){
            if (map.keySet().contains(c)) {
                stack.push(c);
            } else {
                if (!stack.isEmpty() && c.equals(map.get(stack.peek())))
                    stack.pop();
                else
                   return false;
            }
        }
        return stack.isEmpty();
    }

}