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:
-
Input: "(((x+y)))" Output: "(x+y)"
-
Input: "(((a-d))+(b)-(c/((ab))))" Output: "((a-d)+(b)-(c/(ab)))"
-
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
- Create a class called
Redundant
. - Define a function called
removeRedundantParentheses
that takes the input expression as a parameter. - Get the length of the expression
n
. - If the expression is empty (n == 0), return without further processing.
- Create a boolean array
check
of size n and initialize all its elements totrue
. This array will be used to mark redundant parentheses. - Create an empty stack called
record
to store the indices of opening parentheses. - Create an empty string
result
to store the modified expression. - Iterate through the expression from index 0 to n - 1 using a loop.
- 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 stackrecord
contains the index of an opening parenthesis, mark both the opening and closing parentheses as not redundant by settingcheck[i]
andcheck[top of record]
tofalse
. Pop the top element from the stackrecord
. c. If the top of the stackrecord
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. - If the current character is not a closing parenthesis, it must be an opening parenthesis. Push the index
i
onto the stackrecord
. - 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
toresult
ifcheck[j]
istrue
. - 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)
{
Redundant task = new Redundant();
// Test
task.removeRedundantParentheses("(((x+y)))");
task.removeRedundantParentheses("(((a-d))+(b)-(c/((a*b))))");
task.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))
// 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()
{
Redundant *task = new Redundant();
// Test
task->removeRedundantParentheses("(((x+y)))");
task->removeRedundantParentheses("(((a-d))+(b)-(c/((a*b))))");
task->removeRedundantParentheses("((((a+b))) / ((c+g)))");
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)
{
Redundant task = new Redundant();
// Test
task.removeRedundantParentheses("(((x+y)))");
task.removeRedundantParentheses("(((a-d))+(b)-(c/((a*b))))");
task.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))
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()
{
$task = new Redundant();
// Test
$task->removeRedundantParentheses("(((x+y)))");
$task->removeRedundantParentheses("(((a-d))+(b)-(c/((a*b))))");
$task->removeRedundantParentheses("((((a+b))) / ((c+g)))");
}
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()
{
var task = new Redundant();
// Test
task.removeRedundantParentheses("(((x+y)))");
task.removeRedundantParentheses("(((a-d))+(b)-(c/((a*b))))");
task.removeRedundantParentheses("((((a+b))) / ((c+g)))");
}
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() :
task = Redundant()
# Test
task.removeRedundantParentheses("(((x+y)))")
task.removeRedundantParentheses("(((a-d))+(b)-(c/((a*b))))")
task.removeRedundantParentheses("((((a+b))) / ((c+g)))")
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()
task = Redundant.new()
# Test
task.removeRedundantParentheses("(((x+y)))")
task.removeRedundantParentheses("(((a-d))+(b)-(c/((a*b))))")
task.removeRedundantParentheses("((((a+b))) / ((c+g)))")
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
task.removeRedundantParentheses("(((x+y)))");
task.removeRedundantParentheses("(((a-d))+(b)-(c/((a*b))))");
task.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))
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()
{
let task: Redundant = Redundant();
// Test
task.removeRedundantParentheses("(((x+y)))");
task.removeRedundantParentheses("(((a-d))+(b)-(c/((a*b))))");
task.removeRedundantParentheses("((((a+b))) / ((c+g)))");
}
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
{
val task: Redundant = Redundant();
// Test
task.removeRedundantParentheses("(((x+y)))");
task.removeRedundantParentheses("(((a-d))+(b)-(c/((a*b))))");
task.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))
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.
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.
New Comment