Skip to main content

Remove the redundant parentheses from valid expression

Here given code implementation process.

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))
Last updated on by Kalkicode




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.

New Comment