# Remove the redundant parentheses from valid expression

The problem is to remove redundant parentheses from a valid expression. A valid expression is one where all the parentheses are balanced, meaning each opening parenthesis has a corresponding closing parenthesis. Redundant parentheses are unnecessary parentheses that do not affect the meaning of the expression and can be safely removed without changing the result.

## Problem Statement

Given a valid expression with balanced parentheses, we need to remove any redundant parentheses and return the modified expression.

## Example

Consider the following examples:

1. Input: "(((x+y)))" Output: "(x+y)"

2. Input: "(((a-d))+(b)-(c/((ab))))" Output: "((a-d)+(b)-(c/(ab)))"

3. Input: "((((a+b))) / ((c+g)))" Output: "((a+b) / (c+g))"

## Idea to Solve the Problem

To remove redundant parentheses from the expression, we can use a stack to keep track of the indices of opening parentheses. We iterate through the expression and whenever we encounter a closing parenthesis, we check if there is a corresponding opening parenthesis at the top of the stack. If so, we mark both the opening and closing parentheses as not redundant. If there is no corresponding opening parenthesis, it means the expression is not valid, and we return without further processing. After processing the entire expression, we construct the modified expression by including only the non-redundant parentheses.

## Pseudocode

``````Function removeRedundantParentheses(expression):
n = length of expression
if n == 0:
return

Create a boolean array check of size n, initialized to true

Create an empty stack record
result = ""

for i from 0 to n - 1:
if expression[i] == ')':
if record is empty:
// Expression is not valid
return
else if expression[top of record] == '(':
// Mark both opening and closing parentheses as not redundant
check[i] = false
check[top of record] = false
pop the top element from record
else:
// Remove elements until an opening parenthesis is found
while record is not empty and expression[top of record] != '(':
pop the top element from record
if record is empty:
// Expression is not valid
return
pop the top element from record
else:
// Push the index of opening parenthesis onto record
push i onto record

// Construct the modified expression
for j from 0 to n - 1:
if check[j] is true:
append expression[j] to result

Display "Expression: " + expression
Display "Result: " + result
``````

## Algorithm

1. Create a class called `Redundant`.
2. Define a function called `removeRedundantParentheses` that takes the input expression as a parameter.
3. Get the length of the expression `n`.
4. If the expression is empty (n == 0), return without further processing.
5. Create a boolean array `check` of size n and initialize all its elements to `true`. This array will be used to mark redundant parentheses.
6. Create an empty stack called `record` to store the indices of opening parentheses.
7. Create an empty string `result` to store the modified expression.
8. Iterate through the expression from index 0 to n - 1 using a loop.
9. If the current character is a closing parenthesis: a. If the stack `record` is empty, it means there is no corresponding opening parenthesis for this closing parenthesis, and the expression is not valid. Return without further processing. b. If the top of the stack `record` contains the index of an opening parenthesis, mark both the opening and closing parentheses as not redundant by setting `check[i]` and `check[top of record]` to `false`. Pop the top element from the stack `record`. c. If the top of the stack `record` contains the index of a non-opening parenthesis (e.g., a closing parenthesis), it means there is an imbalance in the parentheses, and we need to remove redundant elements. Continue popping elements from the stack until an opening parenthesis is found. If the stack becomes empty before finding an opening parenthesis, it means the expression is not valid, and we return without further processing.
10. If the current character is not a closing parenthesis, it must be an opening parenthesis. Push the index `i` onto the stack `record`.
11. After processing the entire expression, construct the modified expression by including only the non-redundant parentheses. Iterate through the expression and append the characters at indices `j` to `result` if `check[j]` is `true`.
12. Display the original expression and the modified result.

## Code Solution

``````import java.util.Stack;
/*
Java program for
Remove the redundant parentheses from valid expression
*/
public class Redundant
{
public void removeRedundantParentheses(String expression)
{
// Assume given expres
int n = expression.length();
if (n == 0)
{
return;
}
// Valid Parentheses checker
boolean[] check = new boolean[n];
for (int i = 0; i < n; ++i)
{
check[i] = true;
}
// Create an empty record
Stack < Integer > record = new Stack < Integer > ();
String result = "";
// Execute loop through by size of n
for (int i = 0; i < n; ++i)
{
if (expression.charAt(i) == ')')
{
if (record.isEmpty())
{
// Expression are not valid
return;
}
else if (expression.charAt(record.peek()) == '(')
{
check[i] = false;
check[record.peek()] = false;
// Remove top element of stacks
record.pop();
}
else
{
while (record.isEmpty() == false &&
expression.charAt(record.peek()) != '(')
{
// Remove element until not get open parentheses
record.pop();
}
if (record.isEmpty())
{
// Expression are not valid
return;
}
record.pop();
}
}
else
{
// Insert position of expression character
record.push(i);
}
}
// This is collects resultant expression
for (int j = 0; j < n; ++j)
{
if (check[j])
{
result = result + expression.charAt(j);
}
}
// Display given expression
System.out.print("\n Expression : " + expression);
// Display result
System.out.print("\n Result     : " + result);
}
public static void main(String[] args)
{
// Test
}
}``````

#### Output

`````` Expression : (((x+y)))
Result     : (x+y)
Expression : (((a-d))+(b)-(c/((a*b))))
Result     : ((a-d)+(b)-(c/(a*b)))
Expression : ((((a+b))) / ((c+g)))
Result     : ((a+b) / (c+g))``````
``````// Include header file
#include <iostream>
#include <stack>
#include <string>

using namespace std;
/*
C++ program for
Remove the redundant parentheses from valid expression
*/
class Redundant
{
public: void removeRedundantParentheses(string expression)
{
// Assume given expres
int n = expression.length();
if (n == 0)
{
return;
}
// Valid Parentheses checker
bool check[n];
for (int i = 0; i < n; ++i)
{
check[i] = true;
}
// Create an empty record
stack < int > record;
string result = "";
// Execute loop through by size of n
for (int i = 0; i < n; ++i)
{
if (expression[i] == ')')
{
if (record.empty())
{
// Expression are not valid
return;
}
else if (expression[record.top()] == '(')
{
check[i] = false;
check[record.top()] = false;
// Remove top element of stacks
record.pop();
}
else
{
while (record.empty() == false &&
expression[record.top()] != '(')
{
// Remove element until not get open parentheses
record.pop();
}
if (record.empty())
{
// Expression are not valid
return;
}
record.pop();
}
}
else
{
// Insert position of expression character
record.push(i);
}
}
// This is collects resultant expression
for (int j = 0; j < n; ++j)
{
if (check[j])
{
result = result  +  (expression[j]);
}
}
// Display given expression
cout << "\n Expression : " << expression;
// Display result
cout << "\n Result     : " << result;
}
};
int main()
{
// Test
return 0;
}``````

#### Output

`````` Expression : (((x+y)))
Result     : (x+y)
Expression : (((a-d))+(b)-(c/((a*b))))
Result     : ((a-d)+(b)-(c/(a*b)))
Expression : ((((a+b))) / ((c+g)))
Result     : ((a+b) / (c+g))``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp program for
Remove the redundant parentheses from valid expression
*/
public class Redundant
{
public void removeRedundantParentheses(String expression)
{
// Assume given expres
int n = expression.Length;
if (n == 0)
{
return;
}
// Valid Parentheses checker
Boolean[] check = new Boolean[n];
for (int i = 0; i < n; ++i)
{
check[i] = true;
}
// Create an empty record
Stack < int > record = new Stack < int > ();
String result = "";
// Execute loop through by size of n
for (int i = 0; i < n; ++i)
{
if (expression[i] == ')')
{
if ((record.Count == 0))
{
// Expression are not valid
return;
}
else if (expression[record.Peek()] == '(')
{
check[i] = false;
check[record.Peek()] = false;
// Remove top element of stacks
record.Pop();
}
else
{
while ((record.Count == 0) == false &&
expression[record.Peek()] != '(')
{
// Remove element until not get open parentheses
record.Pop();
}
if ((record.Count == 0))
{
// Expression are not valid
return;
}
record.Pop();
}
}
else
{
// Insert position of expression character
record.Push(i);
}
}
// This is collects resultant expression
for (int j = 0; j < n; ++j)
{
if (check[j])
{
result = result + expression[j];
}
}
// Display given expression
Console.Write("\n Expression : " + expression);
// Display result
Console.Write("\n Result     : " + result);
}
public static void Main(String[] args)
{
// Test
}
}``````

#### Output

`````` Expression : (((x+y)))
Result     : (x+y)
Expression : (((a-d))+(b)-(c/((a*b))))
Result     : ((a-d)+(b)-(c/(a*b)))
Expression : ((((a+b))) / ((c+g)))
Result     : ((a+b) / (c+g))``````
``````package main
import "fmt"
/*
Go program for
Remove the redundant parentheses from valid expression
*/

func removeRedundantParentheses(expression string) {
// Assume given expres
var n int = len(expression)
if n == 0 {
return
}
// Valid Parentheses checker
var check = make([]bool,n)
for i := 0; i < n; i++ {
check[i] = true
}
// Create an empty record
var record = make([]int,0)
var result string = ""
// Execute loop through by size of n
for i := 0 ; i < n ; i++ {
if expression[i] == ')' {
if len(record)==0 {
// Expression are not valid
return
} else if expression[record[len(record) - 1]] == '(' {
check[i] = false
check[record[len(record) - 1]] = false
// Remove top element of stacks
record = record[: len(record) - 1]
} else {
for (len(record) > 0  && expression[record[len(record) - 1]] != '(') {
// Remove element until not get open parentheses
record = record[: len(record) - 1]
}
if len(record) == 0 {
// Expression are not valid
return
}
record = record[: len(record) - 1]
}
} else {
// Insert position of expression character
record = append(record, i)
}
}
// This is collects resultant expression
for j := 0 ; j < n ; j++ {
if check[j] {
result = result + string(expression[j])
}
}
// Display given expression
fmt.Print("\n Expression : ", expression)
// Display result
fmt.Print("\n Result     : ", result)
}
func main() {

// Test
removeRedundantParentheses("(((x+y)))")
removeRedundantParentheses("(((a-d))+(b)-(c/((a*b))))")
removeRedundantParentheses("((((a+b))) / ((c+g)))")
}``````

#### Output

`````` Expression : (((x+y)))
Result     : (x+y)
Expression : (((a-d))+(b)-(c/((a*b))))
Result     : ((a-d)+(b)-(c/(a*b)))
Expression : ((((a+b))) / ((c+g)))
Result     : ((a+b) / (c+g))``````
``````<?php
/*
Php program for
Remove the redundant parentheses from valid expression
*/
class Redundant
{
public	function removeRedundantParentheses(\$expression)
{
// Assume given expres
\$n = strlen(\$expression);
if (\$n == 0)
{
return;
}
// Valid Parentheses checker
\$check = array_fill(0, \$n, true);
// Create an empty record
\$record = array();
\$result = "";
// Execute loop through by size of n
for (\$i = 0; \$i < \$n; ++\$i)
{
if (\$expression[\$i] == ')')
{
if (empty(\$record))
{
// Expression are not valid
return;
}
else if (\$expression[end(\$record)] == '(')
{
\$check[\$i] = false;
\$check[end(\$record)] = false;
// Remove top element of stacks
array_pop(\$record);
}
else
{
while (empty(\$record) == false &&
\$expression[end(\$record)] != '(')
{
// Remove element until not get open parentheses
array_pop(\$record);
}
if (empty(\$record))
{
// Expression are not valid
return;
}
array_pop(\$record);
}
}
else
{
// Insert position of expression character
array_push(\$record, \$i);
}
}
// This is collects resultant expression
for (\$j = 0; \$j < \$n; ++\$j)
{
if (\$check[\$j])
{
\$result = \$result.strval(\$expression[\$j]);
}
}
// Display given expression
echo("\n Expression : ".\$expression);
// Display result
echo("\n Result     : ".\$result);
}
}

function main()
{
// Test
}
main();``````

#### Output

`````` Expression : (((x+y)))
Result     : (x+y)
Expression : (((a-d))+(b)-(c/((a*b))))
Result     : ((a-d)+(b)-(c/(a*b)))
Expression : ((((a+b))) / ((c+g)))
Result     : ((a+b) / (c+g))``````
``````/*
Node JS program for
Remove the redundant parentheses from valid expression
*/
class Redundant
{
removeRedundantParentheses(expression)
{
// Assume given expres
var n = expression.length;
if (n == 0)
{
return;
}
// Valid Parentheses checker
var check = Array(n).fill(true);
// Create an empty record
var record = [];
var result = "";
// Execute loop through by size of n
for (var i = 0; i < n; ++i)
{
if (expression.charAt(i) == ')')
{
if ((record.length == 0))
{
// Expression are not valid
return;
}
else if (expression.charAt(record[record.length - 1]) == '(')
{
check[i] = false;
check[record[record.length - 1]] = false;
// Remove top element of stacks
record.pop();
}
else
{
while ((record.length == 0) == false &&
expression.charAt(record[record.length - 1]) != '(')
{
// Remove element until not get open parentheses
record.pop();
}
if ((record.length == 0))
{
// Expression are not valid
return;
}
record.pop();
}
}
else
{
// Insert position of expression character
record.push(i);
}
}
// This is collects resultant expression
for (var j = 0; j < n; ++j)
{
if (check[j])
{
result = result + expression.charAt(j);
}
}
// Display given expression
process.stdout.write("\n Expression : " + expression);
// Display result
process.stdout.write("\n Result     : " + result);
}
}

function main()
{
// Test
}
main();``````

#### Output

`````` Expression : (((x+y)))
Result     : (x+y)
Expression : (((a-d))+(b)-(c/((a*b))))
Result     : ((a-d)+(b)-(c/(a*b)))
Expression : ((((a+b))) / ((c+g)))
Result     : ((a+b) / (c+g))``````
``````#    Python 3 program for
#    Remove the redundant parentheses from valid expression
class Redundant :
def removeRedundantParentheses(self, expression) :
#  Assume given expres
n = len(expression)
if (n == 0) :
return

#  Valid Parentheses checker
check = [True] * (n)
#  Create an empty record
record = []
result = ""
i = 0
#  Execute loop through by size of n
while (i < n) :
if (expression[i] == ')') :
if ((len(record) == 0)) :
#  Expression are not valid
return
elif (expression[record[-1]] == '(') :
check[i] = False
check[record[-1]] = False
#  Remove top element of stacks
record.pop()
else :
while ((len(record) == 0) == False and
expression[record[-1]] != '(') :
#  Remove element until not get open parentheses
record.pop()

if ((len(record) == 0)) :
#  Expression are not valid
return

record.pop()

else :
#  Insert position of expression character
record.append(i)

i += 1

j = 0
#  This is collects resultant expression
while (j < n) :
if (check[j]) :
result = result + str(expression[j])

j += 1

#  Display given expression
print("\n Expression : ", expression, end = "")
#  Display result
print("\n Result     : ", result, end = "")

def main() :
#  Test

if __name__ == "__main__": main()``````

#### Output

`````` Expression :  (((x+y)))
Result     :  (x+y)
Expression :  (((a-d))+(b)-(c/((a*b))))
Result     :  ((a-d)+(b)-(c/(a*b)))
Expression :  ((((a+b))) / ((c+g)))
Result     :  ((a+b) / (c+g))``````
``````#    Ruby program for
#    Remove the redundant parentheses from valid expression
class Redundant
def removeRedundantParentheses(expression)
#  Assume given expres
n = expression.length
if (n == 0)
return
end

#  Valid Parentheses checker
check = Array.new(n) {true}
#  Create an empty record
record = []
result = ""
i = 0
#  Execute loop through by size of n
while (i < n)
if (expression[i] == ')')
if ((record.length == 0))
#  Expression are not valid
return
elsif (expression[record.last] == '(')
check[i] = false
check[record.last] = false
#  Remove top element of stacks
record.pop()
else

while ((record.length == 0) == false &&
expression[record.last] != '(')
#  Remove element until not get open parentheses
record.pop()
end

if ((record.length == 0))
#  Expression are not valid
return
end

record.pop()
end

else

#  Insert position of expression character
record.push(i)
end

i += 1
end

j = 0
#  This is collects resultant expression
while (j < n)
if (check[j])
result = result + expression[j].to_s
end

j += 1
end

#  Display given expression
print("\n Expression : ", expression)
#  Display result
print("\n Result     : ", result)
end

end

def main()
#  Test
end

main()``````

#### Output

`````` Expression : (((x+y)))
Result     : (x+y)
Expression : (((a-d))+(b)-(c/((a*b))))
Result     : ((a-d)+(b)-(c/(a*b)))
Expression : ((((a+b))) / ((c+g)))
Result     : ((a+b) / (c+g))``````
``````import scala.collection.mutable._;
/*
Scala program for
Remove the redundant parentheses from valid expression
*/
class Redundant()
{
def removeRedundantParentheses(expression: String): Unit = {
// Assume given expres
var n: Int = expression.length();
if (n == 0)
{
return;
}
// Valid Parentheses checker
var check: Array[Boolean] = Array.fill[Boolean](n)(true);
// Create an empty record
var record: Stack[Int] = new Stack[Int]();
var result: String = "";
var i: Int = 0;
// Execute loop through by size of n
while (i < n)
{
if (expression.charAt(i) == ')')
{
if (record.isEmpty)
{
// Expression are not valid
return;
}
else if (expression.charAt(record.top) == '(')
{
check(i) = false;
check(record.top) = false;
// Remove top element of stacks
record.pop;
}
else
{
while (record.isEmpty == false &&
expression.charAt(record.top) != '(')
{
// Remove element until not get open parentheses
record.pop;
}
if (record.isEmpty)
{
// Expression are not valid
return;
}
record.pop;
}
}
else
{
// Insert position of expression character
record.push(i);
}
i += 1;
}
var j: Int = 0;
// This is collects resultant expression
while (j < n)
{
if (check(j))
{
result = result + expression.charAt(j).toString();
}
j += 1;
}
// Display given expression
print("\n Expression : " + expression);
// Display result
print("\n Result     : " + result);
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Redundant = new Redundant();
// Test
}
}``````

#### Output

`````` Expression : (((x+y)))
Result     : (x+y)
Expression : (((a-d))+(b)-(c/((a*b))))
Result     : ((a-d)+(b)-(c/(a*b)))
Expression : ((((a+b))) / ((c+g)))
Result     : ((a+b) / (c+g))``````
``````import Foundation;
/*
Swift 4 program for
Remove the redundant parentheses from valid expression
*/
struct Stack
{
private
var items: [Int] = []
func peek()->Int
{
if (self.isEmpty()==false)
{
return items.first!
}
else
{
fatalError("This stack is empty.")
}
}
func isEmpty()->Bool
{
return items.count == 0
}
mutating func pop()
{
items.removeFirst()
}
mutating func push(_ data: Int)
{
items.insert(data, at: 0)
}
}
class Redundant
{
func removeRedundantParentheses(_ exp: String)
{
let expression = Array(exp);
// Assume given expres
let n: Int = expression.count;
if (n == 0)
{
return;
}
// Valid Parentheses checker
var check: [Bool] = Array(repeating: true, count: n);
// Create an empty record
var record = Stack();
var result: String = "";
var i: Int = 0;
// Execute loop through by size of n
while (i < n)
{
if (expression[i] == ")")
{
if (record.isEmpty())
{
// Expression are not valid
return;
}
else if (expression[record.peek()] == "(")
{
check[i] = false;
check[record.peek()] = false;
// Remove top element of stacks
record.pop();
}
else
{
while (record.isEmpty() == false &&
expression[record.peek()]  != "(")
{
// Remove element until not get open parentheses
record.pop();
}
if (record.isEmpty())
{
// Expression are not valid
return;
}
record.pop();
}
}
else
{
// Insert position of expression character
record.push(i);
}
i += 1;
}
var j: Int = 0;
// This is collects resultant expression
while (j < n)
{
if (check[j])
{
result = result + String(expression[j]);
}
j += 1;
}
// Display given expression
print("\n Expression : ", exp, terminator: "");
// Display result
print("\n Result     : ", result, terminator: "");
}
}
func main()
{
// Test
}
main();``````

#### Output

`````` Expression :  (((x+y)))
Result     :  (x+y)
Expression :  (((a-d))+(b)-(c/((a*b))))
Result     :  ((a-d)+(b)-(c/(a*b)))
Expression :  ((((a+b))) / ((c+g)))
Result     :  ((a+b) / (c+g))``````
``````import java.util.Stack;
/*
Kotlin program for
Remove the redundant parentheses from valid expression
*/
class Redundant
{
fun removeRedundantParentheses(expression: String): Unit
{
// Assume given expres
val n: Int = expression.length;
if (n == 0)
{
return;
}
// Valid Parentheses checker
val check: Array < Boolean > = Array(n)
{
true
};
// Create an empty record
val record: Stack < Int > = Stack < Int > ();
var result: String = "";
var i: Int = 0;
// Execute loop through by size of n
while (i < n)
{
if (expression.get(i) == ')')
{
if (record.empty())
{
// Expression are not valid
return;
}
else if (expression.get(record.peek()) == '(')
{
check[i] = false;
check[record.peek()] = false;
// Remove top element of stacks
record.pop();
}
else
{
while (record.empty() == false &&
expression.get(record.peek()) != '(')
{
// Remove element until not get open parentheses
record.pop();
}
if (record.empty())
{
// Expression are not valid
return;
}
record.pop();
}
}
else
{
// Insert position of expression character
record.push(i);
}
i += 1;
}
var j: Int = 0;
// This is collects resultant expression
while (j < n)
{
if (check[j])
{
result = result + expression.get(j).toString();
}
j += 1;
}
// Display given expression
print("\n Expression : " + expression);
// Display result
print("\n Result     : " + result);
}
}
fun main(args: Array < String > ): Unit
{
// Test
}``````

#### Output

`````` Expression : (((x+y)))
Result     : (x+y)
Expression : (((a-d))+(b)-(c/((a*b))))
Result     : ((a-d)+(b)-(c/(a*b)))
Expression : ((((a+b))) / ((c+g)))
Result     : ((a+b) / (c+g))``````

## Time Complexity

The time complexity of the algorithm is O(n), where n is the number of characters in the expression. This is because we perform a single pass through the expression to identify and remove redundant parentheses. The use of the stack and the boolean array does not significantly affect the overall time complexity.

## Comment

Please share your knowledge to improve code and content standard. Also submit your doubts, and test case. We improve by your feedback. We will try to resolve your query as soon as possible.