The **valid parentheses problem** involves checking that:
1. all the parentheses are *matched*, i.e., every opening parenthesis has a corresponding closing parenthesis.
2. the matched parentheses are in the *correct order​*, i.e., an opening parenthesis should come before the closing parenthesis.

## Algorithm
1. Declare an empty stack.
2. Push an opening parenthesis on top of the stack.
3. In case of a closing bracket, check *if* the stack is empty.
4. If not, pop in a closing parenthesis *if* the top of the stack contains the corresponding opening parenthesis.
5. If the parentheses are valid,​ then the stack will be empty once the input string finishes.

## Implementation

#include <iostream>
#include <stack>
#include <string>
using namespace std;
void valid_paren (string input)
{
 // Declaraing a stack.
 stack <char> s;
 int length = input.length();
 char top;
 // Iterating over the entire string.
 for(int i = 0; i< length; i++){
  //  If the input string contains an opening parenthesis,
  //  push in on to the stack.
   if(input[i] == '(' || input[i] == '{' || input[i] == '['){
     s.push(input[i]);
   }
   else
   { // In the case of valid parentheses, the stack cannot be 
    // be empty if a closing parenthesis is encountered.
     if(s.empty()){
       cout<<input<<" contains invalid parentheses."<<endl;
       return;
     }
      else{
      top = s.top();
     // If the input string contains a closing bracket,
     // then pop the corresponding opening parenthesis if
     // present.
      if(input[i] == ')' && top == '(' || 
        input[i] == '}' && top == '{' ||
        input[i] == ']' && top == '[') {
        s.pop();
      }
      else{
        // The opening and closing parentheses are of
        // different types. This implies an invaled sequence
        cout<<input<<" contains invalid parentheses."<<endl;
        return;
      }
     }
   }
 }
//  Checking the status of the stack to determine the
//  validity of the string.
 if (s.empty()){
   cout<<input<<" contains valid parentheses."<<endl;
 }
 else{
   cout<<input<<" contains invalid parentheses."<<endl;
 }
}
int main() {
 string input1 = "{{}}()[()]";
 string input2 = "{][}";
 string input3 = ")";
 valid_paren(input1);
 valid_paren(input2);
 valid_paren(input3);
 return 0;
}

def valid_paren(input_str):
  # Declaraing a stack.
  stack = []
  # Iterating over the entire string
  for paren in input_str:
    # If the input string contains an opening parenthesis,
    # push in on to the stack.
    if paren == '(' or paren == '[' or paren == '{':
      stack.append(paren)
    else:
      # In the case of valid parentheses, the stack cannot be 
      # be empty if a closing parenthesis is encountered.
      if not stack:
        print(input_str, "contains invalid parentheses.")
        return
      else:
        # If the input string contains a closing bracket,
        # then pop the corresponding opening parenthesis if
        # present.
        top = stack[-1]
        if paren == ')' and top == '(' or \
        paren == ']' and top == '[' or \
        paren == '}' and top == '{':
          stack.pop()
  # Checking the status of the stack to determine the
  # validity of the string.
  if not stack:
    print(input_str, "contains valid parentheses.")
  else:
    print(input_str, "contains invalid parentheses.")

input1 = "{{}}()[()]"
input2 = "{][}"
input3 = ")"
valid_paren(input1)
valid_paren(input2)
valid_paren(input3)




Python

 import java.util.*;
class HelloWorld {
  public static void valid_paren(String input_str) {
    // Declaring a stack
    Stack<Character> s = new Stack<Character>();
    // Iterating over the entire string.
    for (char st : input_str.toCharArray()) {
      //  If the input string contains an opening parenthesis,
      //  push in on to the stack.
      if (st == '(' || st == '{' || st == '[') {
        s.push(st);
      }
      else {
        // In the case of valid parentheses, the stack cannot be 
        // be empty if a closing parenthesis is encountered.
          if(s.empty()) {
            System.out.println(input_str + 
            " contains invalid parentheses.");
            return;
          }
          else{
          // If the input string contains a closing bracket,
          // then pop the corresponding opening parenthesis if
          // present.
          char top = (Character) s.peek();
          if(st == ')' && top == '(' ||
          st == '}' && top == '{' ||
          st == ']' && top == '['){
            s.pop();
          }
          else{
            System.out.println(input_str + 
            " contains invalid parentheses.");
            return;
          }
        }
      }
    }
    //  Checking the status of the stack to determine the
    //  validity of the string.
    if(s.empty()) {
      System.out.println(input_str + 
      " contains valid parentheses.");
    }
    else{
      System.out.println(input_str + 
      " contains invalid parentheses.");
    }
  }
  public static void main( String args[] ) {
    String input_str1 = "{{}}()[()]";
    String input_str2 = "(][)";
    String input_str3 = ")";
    valid_paren(input_str1);
    valid_paren(input_str2);
    valid_paren(input_str3);
  }
}

The valid parentheses problem

Algorithm

Implementation