Thu. Oct 6th, 2022

Hello Android

All android in one place

Balanced Parenthesis Problem Using C++

4 min read

In this article, we will solve the balanced parenthesis problem using C++. This is one of the most common features of a text editor and popular IDEs. Without a balanced parenthesis detector in your favorite IDE, you’ll struggle a lot during programming.

It’s not just related to programming, instead, various file formats like JSON, XML, HTML, YAML, etc. rely entirely on the balance of parenthesis, even a single missing balanced parenthesis can blow the structure of the whole file. Enough of talking, let’s directly jump to the problem statement.

Problem Statement

You are either given a string of finite length or a text file of any format. Check the string or the file for balanced parenthesis. If the parenthesis is not balanced then return the location of the first unbalanced parenthesis.

Balanced Parenthesis

Algorithm And Pseudocode

To find the solution to this problem, we’ll make use of the stack data structure. More specifically, we are going to use the LIFO property of a stack. Because the parenthesis that is encountered at the end is the first one to encounter its closing parenthesis on moving ahead.

Note: This problem is a more generic case of a balanced parenthesis problem for specific pair of parenthesis.

Below are the steps/pseudocode that we will follow while writing the algorithm.

  • We maintain a stack to store the parenthesis and its location.
  • And we use this location to return the location of the error if there is any.
  • So whenever we encounter a parenthesis in the input string or the input file, we follow the underlying logic.
    • Check if the parenthsis is an opening parenthesis or a closing parenthesis.
    • If it is an opening parenthesis, simply push it and its location into the stack.
    • Otherwise, follow the steps below.
      • Check if the stack contains any element or it’s empty.
        • If the stack turns out to be empty, then return false. Because there is no opening brace for the corresponding closing brace.
        • Else, check if the closing brace that is encountered completes the pair of the most recent element in the stack.
          • Check if the closing brace matches closing brace of the last element in the stack, just pop the last element of the stack out.
          • Else, return false. Because, every closing brace must match to its corresponding opening brace on encounter.
      • Repeat the same procedure for all the elements of the string.
  • If we exit this loop successfully then simply return true.

For a better understanding of the algorithm, let’s quickly work out through some easy examples given below.

Structure of the stack: stack <pair <parenthesis, location>>
/******************************************************/
Example 1:
String: {}
Stack implementation is as follows:

First call:
Stack: |'{', 1| pushed {'{', 1} into the stack

Second call:
Stack: |Empty| The closing brace corresponds to the closing brace of the last element in the stack. Hence simply remove the last element.
We iterated through all the elements of the input, and the stack is empty in the end thus return true.
/******************************************************/
Example 2:
String: [][]

First call:
Stack: |'[', 1| pushed '{' into the stack

Second call:
Stack: |Empty| removed the last element {'[', 1} out of the stack because the current element is a matching closing brace.

Third call :
Stack: |'[', 3| pushed {'[', 3} into the stack

Fourth call:
Stack: |Empty| popped {'[', 3} out of the stack because the matching closing brace was encountered

Since the stack is empty, return true.
/******************************************************/
Example 3:
String: hel(bar[i);

First call:
Stack: |Empty| since this element is not a parenthesis

Second call:
Stack: |Empty|

Third call:
Stack: |Empty| again, not a parenthesis

Fourth call:
Stack: |'(', 4| pushed {'(', 4} into the stack

Fift call:
Stack: |'(', 4| not a parenthesis

Sixth call:
Stack: |'(', 4| again, not a parenthesis

Seventh call:
Stack: |'(', 4| same as above

Eighth call:
Stack: |'[', 8| pushed {'[',8} into the stack
             |'(', 4|

Ninth call:
Stack: |'[', 8| only push parenthesis into the stack
             |'(', 4|

Tenth call:
Stack: |')', 10| This brace is : {')', 10} and it is not a matching brace for the last element of the stack.
Stack: |'[', 8| so we just push this pair into the stack
             |'(', 4|

Since the stack is not empty, we will check the topmost element of the stack, display its position and return false.
/******************************************************/

Balanced Parenthesis Algorithm Using C++

Let’s now write the actual code for implementing the balanced parenthesis algorithm in C++.

#include <iostream>
#include <stack>
#include <fstream>
#include <cstring>

using namespace std;

// custom class to check to store
// a {bracket, position} pair
// and provide its matching closing
// bracket, we will use this class
// to create our stack
class Bracket
{
public:
  // type can be either:
  // '{', '[', or '('
  char type;
  int position;

  // default constructor of this class
  Bracket(char type, int position): type(type), position(position) {}

  // this function will return true
  // if a given character is the closing
  // bracket for a particular type
  bool Matchc(char c)
  {
    if((type == '[' && c == ']') || (type == '{' && c == '}') || (type == '(' && c == ')'))
      return true;

    return false;
  }
};

// this function will use some file handling
// concepts and print the contents of the
// input file
void print_file_contents(char *FILE_NAME)
{
  ifstream input_file;
  input_file.open(FILE_NAME, ios :: in);
  input_file.seekg(0, ios :: beg);

  if(!input_file.is_open())
    cout << "Either the file is corrupted or the location is incorrect" << endl;

  int cnt = 0;
  int lines = 0;

  cout << "n|*******************************************************|nn";
  cout << "Printing the contents of the file: " << FILE_NAME << endl;
  cout << "n|*******************************************************|n";

  char ch;
  while(input_file.get(ch))
  {
    if(ch == 'n')
      lines ++;

    cnt ++;
    cout << ch;
  }
  cout << "n|*******************************************************|nn";
  cout << "Total lines in the file: " << lines << endl;
  cout << "Total characters read: " << cnt << endl;
  cout << "n|*******************************************************|nn";
  input_file.close();
}

// this function will check the balance parenthesis
// if the input is a string
void check_brackets_from_string(string input_text)
{
  bool flag = true;

  // custom stack data structure
  stack <Bracket> opening_brackets_stack;

  // iterate over all the elements of the input
  for (int position = 0; position < input_text.length(); ++position)
  {
    char next_char = input_text[position];

    // if the character is an opening bracket
    if (next_char == '(' || next_char == '[' || next_char == '{')
    {
      Bracket temp(next_char, position + 1);
      opening_brackets_stack.push(temp);
    }

    // if it is a closing bracket
    if (next_char == ')' || next_char == ']' || next_char == '}')
    {
      // check if the stack is empty or not
      if(opening_brackets_stack.empty())
      {
        // mark flag as false
        flag = false;

	// push the element into the stack
        Bracket temp(next_char, position + 1);
        opening_brackets_stack.push(temp);
        break;
      }
      else if(!opening_brackets_stack.top().Matchc(next_char))
      {
        // if the closing bracket does not match
	// with the last element's closing
	// bracket
        flag = false;

        Bracket temp(next_char, position + 1);
        opening_brackets_stack.push(temp);
        break;
      }
      else
      {
        // if current element is a closing bracket
	// for the last element of the stack
	// simply pop the last element out
        opening_brackets_stack.pop();
      }
    }
  }

  // check if the stack is empty or not
  // if yes, then print success
  if(opening_brackets_stack.empty() && flag)
    cout << "Successn";

  // otherwise, print the location of the error
  else
    cout << opening_brackets_stack.top().position << "n";
}

// this function will use the similar algorithm
// but it will check for input files
void check_brackets_from_file(char *FILE_NAME)
{
  ifstream input_file;
  input_file.open(FILE_NAME, ios :: in);
  input_file.seekg(0, ios :: beg);
  if(!input_file.is_open())
    cout << "Input File Couldn't be opened" << endl;

  stack <Bracket> opening_brackets_stack;
  bool flag = true;
  int position = 0;

  char ch;
  while(input_file.get(ch))
  {
    char next = ch;

    if (next == '(' || next == '[' || next == '{')
    {
      Bracket temp(next, position + 1);
      opening_brackets_stack.push(temp);
    }

    if (next == ')' || next == ']' || next == '}')
    {
      if(opening_brackets_stack.empty())
      {
        flag = false;
        Bracket temp(next, position + 1);
        opening_brackets_stack.push(temp);
        break;
      }
      else if(!opening_brackets_stack.top().Matchc(next))
      {
        flag = false;
        Bracket temp(next, position + 1);
        opening_brackets_stack.push(temp);
        break;
      }
      else
      {
        opening_brackets_stack.pop();
      }
    }
    position ++;
  }
  
  if(opening_brackets_stack.empty() && flag)
    cout << "Success, No Parenthesis Errors were foundn";

  else
    cout << "Error Found At Charater Position: " << opening_brackets_stack.top().position << "n";

  // make sure to close the file handler when not in use
  // this prevents the file from loosing any data
  input_file.close();
}

//  we will use the command line arguements in our main function
int main(int argc, char *argv[])
{
  // if the input file is not provided
  // then ask the user for a string
  if(argc < 2)
  {
    string s;
    getline(cin, s);
    cout << "String is : " << s << endl;
    check_brackets_from_string(s);
  }
  else
  {
    char *input_file_array[argc - 1];

    // this loop will check all the files that are provided as input
    for(int i = 0; i < argc - 1; i++)
    {
      cout << "|*******************************************************************|" << endl << endl;
      cout << "Checking file: " << argv[i + 1] << endl;
      input_file_array[i] = argv[i + 1];
      print_file_contents(input_file_array[i]);
      check_brackets_from_file(input_file_array[i]);
      cout << "|*******************************************************************|" << endl << endl;
    }
  }

  return 0;
}

Output

Balanced Parenthesis Output 1
Parenthesis Output 1
Balanced Parenthesis Output 2
Output 2
Balanced Parenthesis Output 3
Balanced Parenthesis Output 3

Conclusion

In today’s article, we learned to solve balanced parenthesis problems using C++. Later we discussed the pseudocode, and in the end, we developed a simple C++ program to demonstrate the algorithm. This is a very crucial real-world problem and we solved it in O(length) time, using O(length) extra space in the worst case. That’s all for today, thanks for reading.

Further Readings

To learn more about stacks, and balanced parenthesis problems, you can refer to the following websites.

https://www.journaldev.com/56477/stack-class-cpp

www.hello-android.com

Leave a Reply

Your email address will not be published. Required fields are marked *

Hello android © All rights reserved. | Newsphere by AF themes.