Expression contains redundant bracket or not
Last Updated :
28 Jun, 2023
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)
Please Login to comment...