Tagged
• DSA Problems
• Stack
•

# Problem Statement

```1Problem Description :2Given a string expression, where it only contains open and closed characters like '(' , ')', '{', '}', '[', ']'. Determine whether "expression" has a valid sequence of closing and opening parenthesis. 3
4Expression will be valid if :5   1.Open brackets must be closed with the same type of brackets.6   2.Open brackets must be closed in the correct order.7
8Problem Constraints:9   1. 1 <= str.length <= 10⁴10   2. str consists of parentheses only '()[]{}'. 11
12Input:  A string13
14Output: 15  Return false, if the given expression is not balanced.16  Return true, if the given expression is balanced.```

`1Example 1 :2  Input : str = "()[]{}"3  Output: true4  Explanation : str contains valid parenthesis`

`1Example 2 :2  Input : str = "{}"3  Output: true 4  Explanation : str contains valid parenthesis`

`1Example 3 :2  Input : str = "({" 3  Output: false4  Explanation : open brackets not closed`

`1Example 4 :2  Input : str = "([)]"3  Output: false4  Explanation : Incorrect closing bracket for an opening bracket. 5                Here [ is closed by ) which is wrong.`

# Using Stack

## Algorithm

```1Input : A String str 2 3Step 0: Initialize a stack to store characters 4Step 1: For each character 'ch' in the given string 'str'  5Step 2: if ch is an open bracket, then push char into the stack 6Step 3: else if stack is empty return false 7Step 4: else if ch is valid closed bracket for the top element of the stack, pop element from the stack 8Step 5: else, return false 9Step 6: If stack is not empty, return false 10        As we have processed all characters of the stack and 11        still stack is having open brackets 12Step 7: return true 13
14Output : true/false```

## Example Dry Run

• Example 1 : ()[]{} - Valid

• Example 2 : ()] - Invalid

• Example 3: ([)] - Invalid

• Example 4: ([ - Invalid

## Code Implementation

1. Java
2. Python

```1import java.util.Stack;2
3public class ValidParentheses {4
5    // method to check given expression is valid or not6    public boolean isValidExpression(String str) {7        Stack<Character> stack = new Stack<>();8
9        // traverse through each character of the string10        for(int i=0; i < str.length(); i++){11            Character ch = str.charAt(i);12
13            // if the current character is open bracket push into the stack14            if(isOpenBracket(ch)) {15                stack.push(ch);16            }else {17
18                // Example 2 : when an expression has a closed bracket,19                // but no open bracket encountered before closed bracket20                if(stack.isEmpty()) {21                    return false;22                }23
24                // Example 3 : when an open bracket which is not 25                // closed with closing bracket26                if(!isValidPair(stack.peek(), ch)) {27                    return false;28                }29
30                // as we found correct pair for the peek element, pop it..31                stack.pop();32            }33        }34        // Example 4: when an expression has only open brackets example {(35        // or ended with extra open brackets  (){36        if(!stack.isEmpty()) {37            return false;38        }39
40        // Example 1 which is valid41        return true;42    }43
44    // method to check does two brackets valid pair with each other45    private boolean isValidPair(char openBracket, char closedBracket){46        if(openBracket == '{' && closedBracket == '}') {47            return true;48        }49        if(openBracket == '[' && closedBracket == ']') {50            return true;51        }52        if(openBracket == '(' && closedBracket == ')') {53            return true;54        }55        return false;56    }57
58    // method to check a character is open bracket or not59    private boolean isOpenBracket(char ch){60        switch(ch){61            case '{' :62            case '(' :63            case '[' :64                return true;65        }66        return false;67    }68
69    // Driver method70    public static void main(String[] args){71        ValidParentheses obj = new ValidParentheses();72
73        String str = "()[]{}";74        if(obj.isValidExpression(str)) {75            System.out.println(str +" is a valid expression") ;76        }else {77            System.out.println(str +" is an  invalid expression") ;78        }79
80        str = "()";81        if(obj.isValidExpression(str)) {82            System.out.println(str +" is a valid expression") ;83        }else {84            System.out.println(str +" is an  invalid expression") ;85        }86
87        // Case 1 : when an expression has a closed bracket,88        // but no open bracket encountered before closed bracket89        str = "()]";90        if(obj.isValidExpression(str)) {91            System.out.println(str +" is a valid expression") ;92        }else {93            System.out.println(str +" is an  invalid expression") ;94        }95
96        // Case 2 : when an open bracket is not closing with closing bracket97        str = "([)]";98        if(obj.isValidExpression(str)) {99            System.out.println(str +" is a valid expression") ;100        }else {101            System.out.println(str +" is an  invalid expression") ;102        }103
104        // Case 3 : when an expression has only open brackets105        //          or ended with extra open brackets106        str = "([{";107        if(obj.isValidExpression(str)) {108            System.out.println(str +" is a valid expression") ;109        }else {110            System.out.println(str +" is an  invalid expression") ;111        }112    }113}```

## Complexity Analysis

• Time Complexity : O(n) where n is the length of the given input string
• Space Complexity: O(n) as we are using stack data structure

• DSA Problems
• Stack
•
...