- Trending Categories
- Data Structure
- Networking
- RDBMS
- Operating System
- Java
- iOS
- HTML
- CSS
- Android
- Python
- C Programming
- C++
- C#
- MongoDB
- MySQL
- Javascript
- PHP

- Selected Reading
- UPSC IAS Exams Notes
- Developer's Best Practices
- Questions and Answers
- Effective Resume Writing
- HR Interview Questions
- Computer Glossary
- Who is Who

A balanced expression of parentheses is an expression that contains pairs of all sort of parentheses together in a correct order.this means that for every opening parentheses there is a closing parentheses in proper order of parentheses i.e. { }.

let's take a few examples to understand the concept better −

**Expression** − {([][]{})({}[]{})}

**Output** − balanced

**Explanation** − we can see that for every opening parentheses there is a closing parentheses. all the parentheses lying between an opening parentheses and closing parentheses in Pairs.

**Output** − not balance

**Explanation** − there are some unordered pairs of parentheses which makes the the expression unbalanced.

In this problem called **balance expression with replacement**, we are given a string that contains an expression of these brackets ‘{’ , ‘}’ , ‘[’ , ‘]’ , ‘(’ , ‘)’ . there are some places where the brackets are missing and “*” is placed instead of it. And we have to check that weather on replacing all the asterisk symbols with appropriate brackets can the given expression is is able to become a valid expression.

Example

**Input ** − exp = “{[*(*)]}”

**Output ** − the expression can be balanced

**Explanation ** − There are two symbols that need to be replaced. And on replacement will become {[(())]}

**Input ** − exp = “[(*){}{{}}]”

**Output ** − the expression cannot be balanced

**Explanation** − There is one symbol that need to be replaced. And on replacement of * with any of the brackets the expression cannot be balanced.

Now since we have a clear understanding of the problem, we can generate a solution for this problem. To check whether a given parentheses expression will be balanced or not we will use stack data structure to perform our tasks.

The operation that are performed to accomplish this task are −

Traverse every element of the string expression and do −

When an opening bracket is encountered in the expression i.e ‘{’ , ‘[’ , ‘(’ , push the element in the stack.

When a closing bracket is encountered in the expression i.e. ‘}’ , ‘]’ , ‘)’. Pop the element at the top of the stack and check if this is a matching opening for the encountered closing bracket.

If both parentheses matched, then move to the next element of the expression (step 1).

If both parentheses do not match, then the expression is

**not balanced.**

When an * is encountered in the expression which can be an opening as well as closing bracket. Then,

First treat it as opening bracket and push it into the stack and find a matching closing bracket using recursive call for the next element. If this results in fasle, follow the next step

Treat it as closing bracket , it must match the top of stack then pop the top of stack.

It the closing value of * does not match an opening return not balanced.

Print the statement based on the outcome.

Based on this solution let’s create a program

#include <bits/stdc++.h> using namespace std; int isMatching(char a, char b){ if ((a == '{' & b == '}') || (a == '[' & b == ']') || (a == '(' & b == ')') || a == '*') return 1; return 0; } int isBalancedexpression(string s, stack<char> ele, int ind){ if (ind == s.length()) return ele.empty(); char topEle; int res; if (s[ind] == '{' || s[ind] == '(' || s[ind] == '[') { ele.push(s[ind]); return isBalancedexpression(s, ele, ind + 1); } else if (s[ind] == '}' || s[ind] == ')' || s[ind] == ']') { if (ele.empty()) return 0; topEle = ele.top(); ele.pop(); if (!isMatching(topEle, s[ind])) return 0; return isBalancedexpression(s, ele, ind + 1); } else if (s[ind] == '*') { stack<char> tmp = ele; tmp.push(s[ind]); res = isBalancedexpression(s, tmp, ind + 1); if (res) return 1; if (ele.empty()) return 0; ele.pop(); return isBalancedexpression(s, ele, ind + 1); } } int main(){ string s = "{[*(*)]}"; stack ele; if (isBalancedexpression(s, ele, 0)) cout << "Balanced"; else cout << "Not Balanced"; return 0; }

Balanced

- Related Questions & Answers
- Check for balanced parentheses in an expression in C++
- Print the balanced bracket expression using given brackets in C Program
- Minimize Cost with Replacement with other allowed in C++
- Integer Replacement in C++
- Balanced Prime in C++
- Longest Repeating Character Replacement in C++
- C++ Program for Optimal Page Replacement Algorithm
- Regular Expression in C# with Examples
- Expression Tree with Example in C++
- Check for balanced parentheses in an expression - O(1) space - O(N^2) time complexity in C++
- Find a pair with given sum in a Balanced BST in C++
- C++ program to find the quantity after mixture replacement
- Split a String in Balanced Strings in C++
- Print all combinations of balanced parentheses in C++
- Replace the Substring for Balanced String in C++

Advertisements