Check for balanced parenthesis in an expression

Given a sequence of parenthesis, check if the parenthesis are balanced and make a valid expression. For example, an expression { [ ] }is balanced and correct, where as an expression { [ } ] or { [ { } ] is not balanced.

There are three kinds of parenthesis - {}, [], (). One approach to solve this problem is to use a stack. The idea is that a close parenthesis is always preceded by an open parenthesis of the same type. When an open parenthesis is encountered, it is pushed onto the stack. When a close parenthesis is encountered, it should always pair up with the open parenthesis on the top of the stack to make it a valid expression. This pair is then discarded. When the entire expression is traversed, an empty stack confirms that the input expression is balanced and valid.

Consider an expression { [ ( ) ] ( ) } as an example. Following shows the step-by-step traversal: (the top of the stack is highlighted)

Input character = {. Push it onto the stack.

{

Input character = [. Push it onto the stack.

[

{

Input character = (. Push it onto the stack.

(

[

{

Input character = ). Check it with the character on the top of the stack, which is (. It makes a valid pair. Pop ( from the stack.

[

{

Input character = ]. Check it with the character on the top of the stack, which is [. It makes a valid pair. Pop [ from the stack. If the input character is a } instead of a ], it does not make a valid pair and hence the parenthesis expression is not balanced.

{

Input character = (. Push it onto the stack.

(

{

Input character = ). Check it with the character on the top of the stack, which is (. It makes a valid pair. Pop ( from the stack.

{

Input character = }. Check it with the character on the top of the stack, which is {. It makes a valid pair. Pop { from the stack.

The end of input is reached and the stack is empty. Hence, the given input expression is balanced.

Following is the C++ code:

bool IsBalanced(const string& expression_input) {

  stack<char> p;

  int i = 0;

  int expression_input_length = expression_input.length();

  while(i < expression_input_length) {

    char input = expression_input[i];

    if(input == '{' || input == '[' || input == '(') {

      p.push(input);

    } else if(input == '}' || input == ']' || input == ')') {

        if(p.empty()) { //stack is empty

          return false;

        }

        char stack_top = p.top();

        p.pop();

        //does not make a valid pair

        if((stack_top == '(' && input != ')') || (stack_top == '{' && input != '}') || 

           (stack_top == '[' && input != ']') ) {

          return false;

        }

    } else { //a character other than parenthesis is encountered

        cout << "Invalid input character encountered" << endl;

        return false;

    }

   ++i;

  }

  if(p.empty()) { //end of input is reached; stack is empty

    return true;

  }

  return false;

}

Implementing a queue using two stacks

Implement the enqueue, dequeue and peek functionalities of a queue using two stacks.

A queue is a FIFO (first-in, first-out) data structure and a stack is a LIFO (last-in, first-out) data structure. Consider two stacks stack_A and stack_B. A queue can be implemented by using stack_A for the enqueue() operation and stack_B for the dequeue() and peek() operations. Consider the following example: (the top of the stack is highlighted)

enqueue(10): Push 10 onto the stack_A

stack_A	stack_B
10

enqueue(20): Push 20 onto the stack_A

stack_A	stack_B
20
10

enqueue(30): Push 30 onto the stack_A

stack_A	stack_B
30
20
10

Peek(): The element which was inserted first has to be returned without popping it. In order to do this, first transfer all the elements from stack_A to stack_B if stack_B is empty. Return the topmost element from the stack_B. If the stack_B is not empty, just return the topmost element.

In this example, first pop the elements from stack_A and push them onto stack_B. Return the topmost element from stack_B, which is 10.

stack_A	stack_B
	10
	20
	30

enqueue(40): Push 40 onto the stack_A

stack_A	stack_B
	10
	20
40	30

Peek(): As stack_B is not empty, just return the topmost element from stack_B. In this case, it is 10.

dequeue(): The same logic as for the peek() operation holds true here. The difference here is the topmost element from the stack_B has to be popped out instead of returning it.

stack_A	stack_B
	20
40	30

Following is the C++ code:

#include <algorithm>

#include <stack>

class QueueStack {

  stack<int> stack_A;

  stack<int> stack_B;

public:

  void enqueue(int item);

  void dequeue();

  int peek();

};

void QueueStack::enqueue(int item) {

  stack_A.push(item);

}

void QueueStack::dequeue() {

  if(stack_B.empty()) {

    if(stack_A.empty()) {

      cout << "The queue is empty" << endl;

      return;

    } else {

      while(!stack_A.empty()) {

        stack_B.push(stack_A.top());

        stack_A.pop();

      }

      cout << "Removing " << stack_B.top() << " from the queue" << endl;

      stack_B.pop();

    }

  } else {

      cout << "Removing " << stack_B.top() << " from the queue" << endl;

      stack_B.pop();

  }

}

int QueueStack::peek() {

  if(stack_B.empty()) {

    if(stack_A.empty()) {

      cout << "The queue is empty" << endl;

      return -1;

    } else {

      while(!stack_A.empty()) {

        stack_B.push(stack_A.top());

        stack_A.pop();

      }

      cout << "The topmost element is " << stack_B.top() << endl;

      return stack_B.top();

    }

  } else {

      cout << "The topmost element is " << stack_B.top() << endl;

      return stack_B.top();

  }

}

In our case, the enqueue() worked only on stack_A and dequeue() worked on both stack_A and stack_B. A modified implementation could be to update stack_A and stack_B after each enqueue() and work on stack_B for dequeue().

A sequence of n combined enqueues and dequeues take O(n) time.

Phone number to strings

Consider that a person enters a sequence of numbers on a telephone key pad. What are all the possible strings that correspond to the dialed number?

For example, consider the number 23, the possible strings are ad,ae,af,bd,be,bf,cd,ce,cf.

On a telephone keypad, there is mapping between the numbers and the letters associated. Here is the mapping. The numbers 0 and 1 are not associated with any letters.

0	0
1	1
2	a, b, c
3	d, e, f
4	g, h, I
5	j, k, l
6	m, n, o
7	p, q, r, s
8	t, u, v
9	w, x, y, z

Given a number sequence, we have to consider all possible letter combinations. We can build a recursive solution by considering one digit at a time. We stop when all the digits in the input number are explored. Here is the C++ code:

void PhoneNumbers(const string& num, const string& curr, int start) {

  const char Letters[][4] = {

    {'0'},

    {'1'},

    {'a', 'b', 'c'}, //letters starts from 2

    {'d', 'e', 'f'},

    {'g', 'h', 'i'},

    {'j', 'k', 'l'},

    {'m', 'n', 'o'},

    {'p', 'q', 'r', 's'},

    {'t', 'u', 'v'},

    {'w', 'x', 'y', 'z'}

  };

  if(start == num.length()) {

    cout << curr << endl;

    return;

  }

  int digit = num[start] - '0';

  for(int i = 0; i < 4; ++i) { //all possible letters for this digit

    char letter = Letters[digit][i];

    if (letter != 0) {

      PhoneNumbers(num,curr+letter,start+1); 

    } 

  }

}

For an input number 328, invoke the function as:

string n = "328";

PhoneNumbers(n,"",0);

The algorithm is exponential in the length of the input.

As an extension, a dictionary can be used. For an input of reasonable length, only some of the strings make valid English language words. A dictionary can be used to eliminate invalid words. A data structure, such as a hash set can be used. If the length of the input number is fixed, considering a set of dictionary words of that length is sufficient. Invalid words can also be pruned earlier in the enumeration using a dictionary stored in the form of a Trie to detect prefixes that do not occur in the dictionary.