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
If the stack is empty
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.