Posts Balanced Parenthesis
Post
Cancel

Balanced Parenthesis

PROBLEM DESCRIPTION

Given an expression string A, examine whether the pairs and the orders of “{“,”}”, ”(“,”)”, ”[“,”]” are correct in A.

SOLUTION

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
public class Solution {

    Map<String, String> map = new HashMap<>();

    public int solve(String A) {

        map.put("(",")");
        map.put("{","}");
        map.put("[","]");

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

        //Loop through each character in the string
        for(int i=0; i<A.length(); i++){
            
            //Get the current character
            String x = String.valueOf(A.charAt(i));

            //If the current char is opening bracket, push it to the stack
            if(map.containsKey(x)){
                stack.push(x);
            }else{
                //Else, check if stack is not empty and the current char is the corresponding closing bracket of the top most elment on the stack
                //Pop the top most element in the stack them as they form one pair like (), {} or []
                if(!stack.isEmpty() && x.equals(map.get(stack.peek()))){
                    stack.pop();
                }else{
                //If they don't form the right pair, the brackets are definitely not in the right order. Like: {] or (] etc.
                    return 0;
                }
            }

        }
        
        //If the stack is empty, all brackets have corresponding closing bracket in the right order
        return stack.isEmpty()?1:0;

    }
}
This post is licensed under CC BY 4.0 by the author.