Given a string of balanced expressions, find if it contains a redundant parenthesis or not. A set of parenthesis is redundant if the same sub-expression is surrounded by unnecessary or multiple brackets. Print ‘Yes‘ if redundant, else ‘No‘.
Note: Expression may contain ‘+‘, ‘*‘, ‘–‘ and ‘/‘ operators. Given expression is valid and there are no white spaces present.
Examples:
Input: str = “((a+b))”
Output: YES
Explanation: ((a+b)) can reduced to (a+b), this Redundant
Input: str = “(a+(b)/c)”
Output: YES
Explanation: (a+(b)/c) can reduced to (a+b/c) because b is surrounded by () which is redundant.
Checking Redundant Bracket using Stack
The idea is to use the stack, For any sub-expression of expression, if we are able to pick any sub-expression of expression surrounded by (), then we are again left with ( ) as part of the string, we have redundant braces.
Follow the steps mentioned below to implement the approach:
- We iterate through the given expression and for each character in the expression
- if the character is an open parenthesis ‘(‘ or any of the operators or operands, we push it to the stack.
- If the character is close parenthesis ‘)’, then pop characters from the stack till matching open parenthesis ‘(‘ is found.
- Now for redundancy two conditions will arise while popping.
- If immediate pop hits an open parenthesis ‘(‘, then we have found a duplicate parenthesis. For example, (((a+b))+c) has duplicate brackets around a+b. When we reach the second “)” after a+b, we have “((” in the stack. Since the top of the stack is an opening bracket, we conclude that there are duplicate brackets.
- If immediate pop doesn’t hit any operand(‘*’, ‘+’, ‘/’, ‘-‘) then it indicates the presence of unwanted brackets surrounded by expression. For instance, (a)+b contains unwanted () around a thus it is redundant.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>
using namespace std;
bool checkRedundancy(string& str)
{
stack<char> st;
for (auto& ch : str) {
if (ch == ')') {
char top = st.top();
st.pop();
bool flag = true;
while (!st.empty() and top != '(') {
if (top == '+' || top == '-' ||
top == '*' || top == '/')
flag = false;
top = st.top();
st.pop();
}
if (flag == true)
return true;
}
else
st.push(ch);
}
return false;
}
void findRedundant(string& str)
{
bool ans = checkRedundancy(str);
if (ans == true)
cout << "Yes\n";
else
cout << "No\n";
}
int main()
{
string str = "((a+b))";
findRedundant(str);
return 0;
}
|
Java
import java.util.Stack;
public class GFG {
static boolean checkRedundancy(String s) {
Stack<Character> st = new Stack<>();
char[] str = s.toCharArray();
for (char ch : str) {
if (ch == ')') {
char top = st.peek();
st.pop();
boolean flag = true;
while (top != '(') {
if (top == '+' || top == '-'
|| top == '*' || top == '/') {
flag = false;
}
top = st.peek();
st.pop();
}
if (flag == true) {
return true;
}
} else {
st.push(ch);
}
}
return false;
}
static void findRedundant(String str) {
boolean ans = checkRedundancy(str);
if (ans == true) {
System.out.println("Yes");
} else {
System.out.println("No");
}
}
public static void main(String[] args) {
String str = "((a+b))";
findRedundant(str);
}
}
|
Python3
def checkRedundancy(Str):
st = []
for ch in Str:
if (ch == ')'):
top = st[-1]
st.pop()
flag = True
while (top != '('):
if (top == '+' or top == '-' or
top == '*' or top == '/'):
flag = False
top = st[-1]
st.pop()
if (flag == True):
return True
else:
st.append(ch)
return False
def findRedundant(Str):
ans = checkRedundancy(Str)
if (ans == True):
print("Yes")
else:
print("No")
if __name__ == '__main__':
Str = "((a+b))"
findRedundant(Str)
|
C#
using System;
using System.Collections.Generic;
class GFG
{
static bool checkRedundancy(String s)
{
Stack<char> st = new Stack<char>();
char[] str = s.ToCharArray();
foreach (char ch in str)
{
if (ch == ')')
{
char top = st.Peek();
st.Pop();
bool flag = true;
while (top != '(')
{
if (top == '+' || top == '-'
|| top == '*' || top == '/')
{
flag = false;
}
top = st.Peek();
st.Pop();
}
if (flag == true)
{
return true;
}
}
else
{
st.Push(ch);
}
}
return false;
}
static void findRedundant(String str)
{
bool ans = checkRedundancy(str);
if (ans == true)
{
Console.WriteLine("Yes");
}
else
{
Console.WriteLine("No");
}
}
public static void Main(String[] args)
{
String str = "((a+b))";
findRedundant(str);
}
}
|
Javascript
<script>
function checkRedundancy(str)
{
var st = [];
var ans = false;
str.split('').forEach(ch => {
if (ch == ')') {
var top = st[st.length-1];
st.pop();
var flag = true;
while (st.length!=0 && top != '(') {
if (top == '+' || top == '-' ||
top == '*' || top == '/')
flag = false;
top = st[st.length-1];
st.pop();
}
if (flag == true)
ans = true;
}
else
st.push(ch);
});
return ans;
}
function findRedundant(str)
{
var ans = checkRedundancy(str);
if (ans == true)
document.write( "Yes<br>");
else
document.write( "No<br>");
}
var str = "((a+b))";
findRedundant(str);
</script>
|
Time Complexity: O(N)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It's time for a change! Join our DSA course, where we'll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 geeks!