{"id":9276,"date":"2022-08-25T10:20:31","date_gmt":"2022-08-25T10:20:31","guid":{"rendered":"https:\/\/www.prepbytes.com\/blog\/?p=9276"},"modified":"2023-05-11T06:39:42","modified_gmt":"2023-05-11T06:39:42","slug":"check-for-balanced-parentheses-in-an-expression","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/check-for-balanced-parentheses-in-an-expression\/","title":{"rendered":"Check for Balanced Parentheses in an Expression"},"content":{"rendered":"

\"\"<\/p>\n

In computer science, balanced parentheses are a common requirement for many programming languages and applications. Balanced parentheses refer to an expression in which all opening and closing parentheses are properly matched and nested. A balanced expression ensures that the program can be executed without any errors.<\/p>\n

To check for balanced brackets in an expression using stack in C programming, you need to traverse the expression and keep track of the opening and closing parentheses using a stack data structure. If an opening parenthesis is encountered, it is pushed onto the stack, and if a closing parenthesis is encountered, it is compared with the top element of the stack.<\/p>\n

If the closing parenthesis matches the top element, the top element is popped, and the traversal continues. If the closing parenthesis does not match the top element or there are no more elements in the stack, the expression is considered unbalanced.<\/p>\n

How to Check for Balanced Parentheses in an Expression<\/h2>\n

Given an expression containing only \u2018(\u2018, \u2019)\u2019, \u2019{\u2018, \u2018}\u2019, \u2018[\u2018, \u2018]\u2019 , check whether the expression is balanced or not.<\/p>\n

An expression is balanced if each opening bracket is closed by the same type of closing bracket in the exact same order.<\/p>\n

Input<\/strong>:<\/p>\n

A string representing the given expression<\/code><\/pre>\n
Output<\/strong>:<\/p>\n
Boolean value<\/code><\/pre>\n
Test cases<\/strong>:
\nInput 1<\/strong>:<\/p>\n
\u201c({[]})\u201d<\/code><\/pre>\n
Output 1<\/strong>:<\/p>\n
true<\/code><\/pre>\n
Input 2<\/strong>:<\/p>\n
\u201c(){}](\u201c<\/code><\/pre>\n
Output 2<\/strong>:<\/p>\n
false<\/code><\/pre>\n
Approach \u2013 Check for Balanced Brackets in an Expression using Stack<\/h3>\n
The idea is to use the LIFO functionality of the stack. As a stack is LIFO data structure<\/a>, we will remove every opening bracket (\u2018(\u2018, \u2018{\u2018, \u2018[\u2018), whenever we encounter the same type of closing bracket (\u2018)\u2019, \u2018}\u2019, \u2018]\u2019).
\nIf for any opening bracket we don’t have a closing bracket, the opening bracket will remain in the stack forever.
\nSimilarly if we only have a closing bracket without a preceding opening bracket we will just push the closing bracket into the stack and it will remain there forever.
\nSo, at last after traversing the whole expression, if the stack is empty then it will mean that the given expression is balanced, otherwise if the stack contains elements that would mean the given expression was unbalanced.<\/p>\n
Algorithm to Check Balanced Parentheses in C using Stack<\/h3>\n
    \n
  1. Initialize an empty stack.<\/li>\n
  2. Iterate i from 0 to length(expression).\n
      \n
    • Store the current character in a variable \u2018ch\u2019.<\/li>\n
    • If stack is empty: Push \u2018ch\u2019 to the stack<\/li>\n
    • Else if current character is a closing bracket and of the top of the stack contains an opening bracket of the same type then remove the top of the stack:  Else, push \u2018ch\u2019 to the stack<\/li>\n<\/ul>\n<\/li>\n
    • If the stack is empty, return true, else false.<\/li>\n<\/ol>\n
      Dry Run to Check for Balanced Brackets in an Expression using Stack<\/h3>\n
      Input:<\/strong><\/p>\n
      \u201c({[]})\u201d<\/code><\/pre>\n
      Output:<\/strong><\/p>\n
      true<\/code><\/pre>\n\n\n\n\n\n\n\n\n\n\n\n
      Stack<\/th>\nExpression<\/th>\nAction<\/th>\n<\/tr>\n<\/thead>\n
      <\/td>\n({[]})<\/td>\nPush<\/td>\n<\/tr>\n
      (<\/td>\n{[]})<\/td>\nPush<\/td>\n<\/tr>\n
      ({<\/td>\n[]})<\/td>\nPush<\/td>\n<\/tr>\n
      ({[<\/td>\n]})<\/td>\nPop<\/td>\n<\/tr>\n
      ({<\/td>\n})<\/td>\nPop<\/td>\n<\/tr>\n
      (<\/td>\n)<\/td>\nPop<\/td>\n<\/tr>\n
      Empty<\/td>\n<\/td>\n<\/td>\n<\/tr>\n<\/tbody>\n<\/table>\n
      As the stack is empty, hence the given expression was balanced.<\/p>\n
      \"\"<\/p>\n
      Code Implementation<\/h3>\n\t\t\t\t\t\t