Monthly Archives: May 2013

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;
}

Counting characters in the given string using C++ STL map

Map is one of the most useful data structure in solving many programming problems. Today we will see how to use C++ STL map with a simple example. Counting the frequency of letters in a given string. The map data structure stores <key,value> pairs. In this example key will be the character, and the value will be it’s frequency. Here is the code to do this.

#include <iostream>
#include <string>
#include <map>

using namespace std;

void getFrequency(string strInput,map<char,int> & fMap)
{
map<char,int>::iterator it; //iterator to find the entries in map
for(int i = 0 ; i < strInput.length() ; i++ )
{
char ch = strInput.at(i);
it = fMap.find(ch); //find the character in the map
if( it == fMap.end() ) //if not present in the map
{
fMap.insert( make_pair(ch,1) );//add an entry
}
else
{
it->second++; //else increment the frequency
}
}
}

void printFrequency(map<char,int> & fMap)
{
map<char,int>::iterator it;//iterator to loop through all the chars
for( it = fMap.begin() ; it != fMap.end() ; ++it )
{
cout<<"["<< it->first<<"]"<<"->"<<it->second<<endl;
}
}

int main()
{
string strInput;
//read input string; this implementation does not reed space separated strings
cin>>strInput;
map<char,int> frequencyMap; //frequency map
getFrequency(strInput, frequencyMap); //get the frequencies
printFrequency(frequencyMap); //print the frequencies
return 0;
}

Finding count of a number in a sorted array

In Competitive programming, learning to use the standard library than coding from scratch saves a lot of time. In this post we will use C++ STL(Standard Template Library) binary search algorithm with an example.
Given a sorted array of numbers, How to find the frequency of a given number?

Here is an efficient algorithm to do it. Use binary search to find the left-most(L), and right-most(R) occurrence of the given number. Then R-L+1 gives us the result. 

C++ STL has two functions namely lower_bound, upper_bound which finds out the left-most and right-most occurrences of a given number in a sorted array.
The lower_bound() function returns an iterator to the left-most element, and the upper_bound() function returns an iterator to one element beyond right-most occurrence. So the difference of these two gives the count.

Here is the C++ code.
 

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>

using namespace std;

int getCount(vector<int> & numVector, int d)
{
int result = 0;
vector<int>::iterator left, right;
//find the left-most occurence
left = lower_bound( numVector.begin(), numVector.end(), d );
//find right-most occurence only if the number is present
if( left != numVector.end() )
{
right = upper_bound( numVector.begin(), numVector.end(), d );
result = right-left; //right points to one element beyond.
}
return result;
}
int main()
{
int n;
//read array size
cin>>n;
int i,num;
vector<int> nums;
//read the array
for( i = 0 ; i < n ; i++ )
{
cin>>num;
nums.push_back(num);
}
//read the number to be counted
cin>>num;
cout<<getCount(nums,num);
return 0;
}

Finding duplicates from given set of numbers

Given a list of numbers. How do we write a program to find the duplicates among them?
A simple algorithm is to compare each possible pair in the list to see if there are any duplicates. But this algorithm runs in O(n2) time.
We can use the following simple algorithm using the set data structure. This data structure supports insert/add, find operations. We read one number at a time and try to find it in the set. If the set already contains that element, we declare that element as a duplicate, otherwise we insert that element into that set. The following is a Java implementation of the same.

 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
import java.io.*;
import java.util.HashSet;
/**
*
* @author Ravi
*/
public class DuplicateNums {

/**
* @param args the command line arguments
*/
public static void main(String[] args) {
try
{
//Read from the standard input
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String input = br.readLine();
String [] strNums = input.split(" ");

//create the hash set to store the unique numbers
HashSet<Integer> hSet = new HashSet<Integer>();

for( int i = 0 ; i < strNums.length ; i++)
{
//try to add the number to the set,
//if add method returns false, the number is a duplicate
if( !hSet.add( Integer.parseInt(strNums[i]) ) )
{
System.out.print(strNums[i] + " ");
}
}
System.out.println();
}
catch(IOException ioe)
{
System.out.println("Exception while reading the input" + ioe.getMessage());
}
catch(NumberFormatException nfe)
{
System.out.println("Invalid Input "+ nfe.getMessage());
}
}
}

We have used HashSet data structure from the Java standard library. This provides O(1) time for insert and find operations in an average case. So the average time complexity of the above program is O(n). Since we are storing the elements in the set, the space complexity is O(n) in the worst case (No duplicates in the list).