Bracket matching problem

Stack is one of the most widely used data structure. In this post we will learn how to use the stack container (data structure) provided by C++ STL with an example.

Let us consider the following problem. We have a string which contains only ‘(‘ and ‘)’ characters. We have to write a program to check if it forms a valid expression.
For example the string “(()())” is a valid expression where as “(()()” and “())” are not.

The algorithm for solving the question goes like this. 

1. For each character in the string
    If the symbol is ‘(‘
         push it on to the stack
   else
        If the stack is empty
            return false
       If top of the stack contains ‘(‘
            pop off the top element
2. If the stack is empty return true otherwise return false

Here is the program which implements the above algorithm.

#include <iostream>
#include <string>
#include <stack>

using namespace std;

bool isValidExpr(string input)
{
 stack<char> stck;

 for(int i = 0; i < input.length() ; i++)
 {
  char ch = input.at(i);

  if( ch == '(' ) //if open brace, push
  {
   stck.push(ch);
  }
  else //closed brace
  {
   if( stck.empty() )// if stack is empty, there no matching open brace
    return false;
   if ( stck.top() == '(' ) //matching open brace found, so pop
   {
    stck.pop();
   }
  }
 }
 if( stck.empty() )
  return true;
 return false;
}

int main()
{
 string inputExpr;
 cin>>inputExpr;
 if( isValidExpr(inputExpr) )
  cout<<"Valid Expression";
 else
  cout<<"Invalid Expression";
 return 0;
}