A matched string is a sequence of and characters that

A matched string is a sequence of {, }, (, ), [, and ] characters that are properly matched. For example, ``{{()[]}}\'\' is a matched string, but this ``{{()]}\'\' is not, since the second { is matched with a ]. Show how to use a stack so that, given a string of length n, you can determine if it is a matched string in O(n) time. Your answer should consist in a commented pseudocode or Java code.

Solution

import java.util.*;

public class ParenthesisMatching
{
//function to check Balanced
public static boolean Balanced(String s) {
HashMap<Character, Character> map = new HashMap<Character, Character>();
map.put(\'(\', \')\');
map.put(\'[\', \']\');
map.put(\'{\', \'}\');

Stack<Character> stack = new Stack<Character>();

for (int i = 0; i < s.length(); i++) {
char curr = s.charAt(i);

if (map.keySet().contains(curr)) {
stack.push(curr);
} else if (map.values().contains(curr)) {
if (!stack.empty() && map.get(stack.peek()) == curr) {
stack.pop();
} else {
return false;
}
}
}

return stack.empty();
}
public static void main(String[] args)
{
Scanner sc=new Scanner(System.in);
String s=sc.next();
boolean flag=Balanced(s);
if(flag)
System.out.println(\"Balanced\");
else
System.out.println(\"Not Balanced\");
  
}
}

====================================================

akshay@akshay-Inspiron-3537:~/Chegg$ javac ParenthesisMatching.java

akshay@akshay-Inspiron-3537:~/Chegg$ java ParenthesisMatching

{{()[]}}   
Balanced