Program to check if given expression contains redundant braces

05 min read

 A string of characters is given as input and it is checked if it has redundant braces or not. This can be done using stacks as it is one of the important applications of stack data structure. If the expression or sub-expression is surrounded by extra or unnecessary braces, then the expression is said to have redundant brackets.

For example,

(( a - b )) has redundant brackets as it is having an extra set of parenthesis.

(( a * b ) - (c) + d) has redundant brackets as (c) is having unnecessary braces..

 

Steps to find if an expression has redundant brackets

 

  • Scan the expression character by character.
  • If the scanned character is an open parenthesis ‘(‘ or any of the operands or operators, push it to the stack.
  • If the scanned character is a closed parenthesis ‘)’, then pop characters from the stack till the matching open parenthesis ‘(‘ is found.
  • If immediate pop has an open parenthesis ‘(‘, then the duplicate parenthesis is found.

Let us now look at a program to check if the given expression has redundant brackets or not.

C++ program to check if the expression has redundant braces

 

#include <iostream> 
#include <stack>
using namespace std;

// Function to check redundant brackets
bool redundant_braces(string& str)
{
// creating a character stack
stack<char> st;
// Iterating the input expression
for (auto& ch : str) {
// If the scanned character is a closed parenthesis ')'
if (ch == ')') {
char top = st.top();
st.pop();
// If immediate pop has an open parenthesis '('
bool flag = true; // duplicate brackets found
while (top != '(') {
// Check for the operators in the input expression
if (top == '+' || top == '-' || top == '*' || top == '/')
flag = false;
// Pop the top element
top = st.top();
st.pop();
}
// If operators are not found
if (flag == true)
return true;
}
else
st.push(ch); // push '(', operators and operands to stack
}
return false;
}

// Function to check redundant braces
void redundancy_check(string& str)
{
bool ans = redundant_braces(str);
if (ans == true)
cout << "Yes\n";
else
cout << "No\n";
}

int main()
{
string str = "(a*b-(c+d))";
redundancy_check(str);
str = "((a+b))";
redundancy_check(str);
str = "(a/b*((c-d)))";
redundancy_check(str);
return 0;
}

OUTPUT

redundant braces in an expression



POST A NEW COMMENT
     
  • Input (stdin)

    Output (stdout)


    Input (stdin)

    Your Output (stdout)

    Expected Output

    Compiler Message

    Input (stdin)

    2    3

    Your Output (stdout)

    5

    Expected Output

    5

    Compiler Message

    5

    Error