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

• Java
• C++
• C#
• Go
• Php
• Node Js
• Python
• Ruby
• Scala
• Swift 4
• Kotlin

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)))");
	}
}

 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;
}

 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)))");
	}
}

 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)))")
}

 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();

 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();

 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()

 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()

 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)))");
	}
}

 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();

 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)))");
}

 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.