Related Tags

The valid parentheses problem


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;
}
RELATED COURSES
View all Courses