La expresión contiene corchetes redundantes o no

Dada una string de expresión equilibrada, encuentre si contiene un paréntesis redundante o no. Un conjunto de paréntesis es redundante si la misma subexpresión está rodeada por corchetes innecesarios o múltiples. Escriba ‘Sí’ si es redundante, de lo contrario ‘No’.
Nota: La expresión puede contener operadores ‘ + ‘, ‘ * ‘, ‘ ‘ y ‘ / ‘. La expresión dada es válida y no hay espacios en blanco presentes.
Ejemplo: 
 

Input: 
((a+b))
(a+(b)/c)
(a+b*(c-d))
Output: 
Yes
Yes
No

Explanation:
1. ((a+b)) can reduced to (a+b), this Redundant
2. (a+(b)/c) can reduced to (a+b/c) because b is
surrounded by () which is redundant.
3. (a+b*(c-d)) doesn't have any redundant or multiple
brackets.

La idea es usar stack, que se analiza en este artículo. Para cualquier subexpresión de expresión, si somos capaces de elegir cualquier subexpresión de expresión rodeada por(), entonces nuevamente nos quedamos con() como parte de la string, tenemos llaves redundantes. 
Iteramos a través de la expresión dada y para cada carácter en la expresión, si el carácter es un paréntesis abierto ‘(‘ o cualquiera de los operadores u operandos, lo empujamos a la pila. Si el carácter es un paréntesis cerrado ‘)’, entonces extraiga los caracteres de la pila hasta que se encuentre el paréntesis abierto ‘(‘. 
Ahora, para la redundancia, surgirán dos condiciones mientras se extrae: 
 

  1. Si pop inmediato golpea un paréntesis abierto ‘(‘, entonces hemos encontrado un paréntesis duplicado. Por ejemplo, (((a+b))+c) tiene corchetes duplicados alrededor de a+b . Cuando llegamos al segundo «)» después a+b, tenemos “ (( ” en la pila. Dado que la parte superior de la pila es un corchete de apertura, concluimos que hay corchetes duplicados. 
     
  2. Si pop inmediato no toca ningún operando (‘*’, ‘+’, ‘/’, ‘-‘), entonces indica la presencia de corchetes no deseados rodeados por expresión. Por ejemplo, (a)+b contienen () no deseados alrededor de a , por lo que es redundante. 
     

C++

/* C++ Program to check whether valid
 expression is redundant or not*/
#include <bits/stdc++.h>
using namespace std;
 
// Function to check redundant brackets in a
// balanced expression
bool checkRedundancy(string& str)
{
    // create a stack of characters
    stack<char> st;
 
    // Iterate through the given expression
    for (auto& ch : str) {
 
        // if current character is close parenthesis ')'
        if (ch == ')') {
            char top = st.top();
            st.pop();
 
            // If immediate pop have open parenthesis '('
            // duplicate brackets found
            bool flag = true;
 
            while (!st.empty() and top != '(') {
 
                // Check for operators in expression
                if (top == '+' || top == '-' ||
                    top == '*' || top == '/')
                    flag = false;
 
                // Fetch top element of stack
                top = st.top();
                st.pop();
            }
 
            // If operators not found
            if (flag == true)
                return true;
        }
 
        else
            st.push(ch); // push open parenthesis '(',
                  // operators and operands to stack
    }
    return false;
}
 
// Function to check redundant brackets
void findRedundant(string& str)
{
    bool ans = checkRedundancy(str);
    if (ans == true)
        cout << "Yes\n";
    else
        cout << "No\n";
}
 
// Driver code
int main()
{
    string str = "((a+b))";
    findRedundant(str);
 
    str = "(a+(b)/c)";
    findRedundant(str);
 
    str = "(a+b*(c-d))";
    findRedundant(str);
 
    return 0;
}

Java

/* Java Program to check whether valid
expression is redundant or not*/
import java.util.Stack;
public class GFG {
// Function to check redundant brackets in a
// balanced expression
 
    static boolean checkRedundancy(String s) {
        // create a stack of characters
        Stack<Character> st = new Stack<>();
        char[] str = s.toCharArray();
        // Iterate through the given expression
        for (char ch : str) {
 
            // if current character is close parenthesis ')'
            if (ch == ')') {
                char top = st.peek();
                st.pop();
 
                // If immediate pop have open parenthesis '('
                // duplicate brackets found
                boolean flag = true;
 
                while (top != '(') {
 
                    // Check for operators in expression
                    if (top == '+' || top == '-'
                            || top == '*' || top == '/') {
                        flag = false;
                    }
 
                    // Fetch top element of stack
                    top = st.peek();
                    st.pop();
                }
 
                // If operators not found
                if (flag == true) {
                    return true;
                }
            } else {
                st.push(ch); // push open parenthesis '(',
            }                // operators and operands to stack
        }
        return false;
    }
 
// Function to check redundant brackets
    static void findRedundant(String str) {
        boolean ans = checkRedundancy(str);
        if (ans == true) {
            System.out.println("Yes");
        } else {
            System.out.println("No");
        }
    }
 
// Driver code
    public static void main(String[] args) {
        String str = "((a+b))";
        findRedundant(str);
 
        str = "(a+(b)/c)";
        findRedundant(str);
 
        str = "(a+b*(c-d))";
        findRedundant(str);
    }
}

Python3

# Python3 Program to check whether valid
# expression is redundant or not
 
# Function to check redundant brackets
# in a balanced expression
def checkRedundancy(Str):
     
    # create a stack of characters
    st = []
 
    # Iterate through the given expression
    for ch in Str:
 
        # if current character is close
        # parenthesis ')'
        if (ch == ')'):
            top = st[-1]
            st.pop()
 
            # If immediate pop have open parenthesis
            # '(' duplicate brackets found
            flag = True
 
            while (top != '('):
 
                # Check for operators in expression
                if (top == '+' or top == '-' or
                    top == '*' or top == '/'):
                    flag = False
 
                # Fetch top element of stack
                top = st[-1]
                st.pop()
 
            # If operators not found
            if (flag == True):
                return True
 
        else:
            st.append(ch) # append open parenthesis '(',
                          # operators and operands to stack
    return False
 
# Function to check redundant brackets
def findRedundant(Str):
    ans = checkRedundancy(Str)
    if (ans == True):
        print("Yes")
    else:
        print("No")
 
# Driver code
if __name__ == '__main__':
    Str = "((a+b))"
    findRedundant(Str)
 
    Str = "(a+(b)/c)"
    findRedundant(Str)
 
    Str = "(a+b*(c-d))"
    findRedundant(Str)
 
# This code is contributed by PranchalK

C#

/* C# Program to check whether valid
expression is redundant or not*/
using System;
using System.Collections.Generic;
 
class GFG
{
    // Function to check redundant brackets in a
    // balanced expression
    static bool checkRedundancy(String s)
    {
        // create a stack of characters
        Stack<char> st = new Stack<char>();
        char[] str = s.ToCharArray();
         
        // Iterate through the given expression
        foreach (char ch in str)
        {
 
            // if current character is close parenthesis ')'
            if (ch == ')')
            {
                char top = st.Peek();
                st.Pop();
 
                // If immediate pop have open parenthesis '('
                // duplicate brackets found
                bool flag = true;
 
                while (top != '(')
                {
 
                    // Check for operators in expression
                    if (top == '+' || top == '-'
                            || top == '*' || top == '/')
                    {
                        flag = false;
                    }
 
                    // Fetch top element of stack
                    top = st.Peek();
                    st.Pop();
                }
 
                // If operators not found
                if (flag == true)
                {
                    return true;
                }
            }
            else
            {
                st.Push(ch); // push open parenthesis '(',
            }         // operators and operands to stack
        }
        return false;
    }
 
    // Function to check redundant brackets
    static void findRedundant(String str)
    {
        bool ans = checkRedundancy(str);
        if (ans == true)
        {
            Console.WriteLine("Yes");
        }
        else
        {
            Console.WriteLine("No");
        }
    }
 
    // Driver code
    public static void Main(String[] args)
    {
        String str = "((a+b))";
        findRedundant(str);
 
        str = "(a+(b)/c)";
        findRedundant(str);
 
        str = "(a+b*(c-d))";
        findRedundant(str);
    }
}
 
/* This code contributed by PrinciRaj1992 */

Javascript

<script>
 
/* JavaScript Program to check whether valid
 expression is redundant or not*/
 
 
// Function to check redundant brackets in a
// balanced expression
function checkRedundancy(str)
{
    // create a stack of characters
    var st = [];
    var ans = false;
    // Iterate through the given expression
    str.split('').forEach(ch => {
         
 
        // if current character is close parenthesis ')'
        if (ch == ')') {
            var top = st[st.length-1];
            st.pop();
 
            // If immediate pop have open parenthesis '('
            // duplicate brackets found
            var flag = true;
 
            while (st.length!=0 && top != '(') {
 
                // Check for operators in expression
                if (top == '+' || top == '-' ||
                    top == '*' || top == '/')
                    flag = false;
 
                // Fetch top element of stack
                top = st[st.length-1];
                st.pop();
            }
 
            // If operators not found
            if (flag == true)
                ans = true;
        }
 
        else
            st.push(ch); // push open parenthesis '(',
                  // operators and operands to stack
    });
    return ans;
}
 
// Function to check redundant brackets
function findRedundant(str)
{
    var ans = checkRedundancy(str);
    if (ans == true)
        document.write( "Yes<br>");
    else
        document.write( "No<br>");
}
 
// Driver code
 
var str = "((a+b))";
findRedundant(str);
 
str = "(a+(b)/c)";
findRedundant(str);
 
str = "(a+b*(c-d))";
findRedundant(str);
 
 
</script>
Producción

Yes
Yes
No

Complejidad temporal : O(n) 
Espacio auxiliar : O(n)

Publicación traducida automáticamente

Artículo escrito por Shubham Bansal 13 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *