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