Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

data structures
c++

Which data structure is used to check balanced parenthesis?

Adnan Abbas

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Problem statement

We aim to write a program that checks whether the parentheses in an expression are balanced. This means that the closing symbol should match the most recently seen opening symbol. e.g. {()} is legal, {() ({})} is legal, but {((} and {(}) are not legal.

Input

A string consisting of brackets "{, }, (, ), [, ]" .

Return value

The function returns true if the expression is balanced. Otherwise, it returns false.

%0 node_1624452580281 { node_1624452580156 [ node_1 ( node_2 ) node_3 ] node_1624442885054 }
The function returns true for such a string

Data structure and solution

We will use the built-in stack data structure provided by the C++ library. Remember that the stack is FIFO (First In First Out) data structure. Here are the steps of the algorithm which checks balanced parentheses:

  • Initialize a character stack that will store the parentheses.
  • Traverse the input string from the left side to the right.
  • If the character is an opening bracket such as {, [, and ( then push it in the stack.
  • If the character is a closing bracket such as }, ], and ), then pop the recent character from the stack and check if it is the corresponding opening bracket. If it is not the opening bracket, then the input is unbalanced. We can see this here:
#include<iostream>
#include<stack>
using namespace std;

bool isBalanced(string expr) {
   stack <char> s;
   char ch;
   for (int i=0; i < expr.length(); i++) {    //for each character in the input, we check various possibilities
      if (expr[i] =='('||expr[i]=='['||expr[i]=='{') {    //when it is an opening bracket, we push in stack
         s.push(expr[i]);
         continue;
      }
      if (s.empty())    //no opening bracket, there must be some closing bracket in the beginning so its unbalanced
         return false;
         switch (expr[i]) {
            case ')':    //for closing parenthesis, pop it and check if opening parenthesis is present
               ch = s.top();
               s.pop();
               if (ch != '(')
                  return false;
                  break;
            case '}': //for closing braces, pop it and check if opening brace is present
               ch = s.top();
               s.pop();
               if (ch != '{')
                  return false;
                  break;
            case ']': //for closing square bracket, pop it and check if closing square bracket is present
               ch = s.top();
               s.pop();
               if (ch != '[')
                  return false;
                  break;
         }
      }
      return (s.empty()); //when stack is empty, return true
}
main() {
   string expr = "[{}(){()}]";
   if (isBalanced(expr))
      cout << "Balanced Parenthesis!!";
   else
      cout << "Not Balanced Parenthesis";
}

RELATED TAGS

data structures
c++

CONTRIBUTOR

Adnan Abbas
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring