# Check if expression contains extra brackets or not

The problem is to check if the given expression contains any extra brackets or not. An expression is considered to have extra brackets if there are brackets that do not contain any operators (+, -, *, /) inside them. For example, "(a+b)" does not have extra brackets as it contains the addition operator inside the brackets. On the other hand, "(a+b-(c+((a+b))))" has extra brackets as the innermost brackets "(a+b)" do not contain any operators.

## Problem Statement

Given an expression as a string, check if it contains any extra brackets and print the result.

## Example

Consider the following examples:

1. Input: "(a+b-(c+((a+b))))" Output: Extra brackets exist Explanation: The expression contains the extra brackets "((a+b))" which do not contain any operators.

2. Input: "((a+b)-(b-(c*d)))" Output: Extra brackets do not exist Explanation: The expression does not contain any extra brackets as all the brackets have operators inside them.

## Idea to Solve the Problem

To check if the given expression contains any extra brackets, we can use a stack to keep track of the opening brackets. As we encounter closing brackets, we can pop elements from the stack until we find the corresponding opening bracket. If we encounter any operators during this process, it means that the brackets do not have any extra brackets.

## Pseudocode

``````Function isExtraBracket(exp):
Create an empty stack called record
Create a boolean variable called result and set it to false
Create a boolean variable called check and set it to true

for each character ch in exp:
if ch is ')':
If record is empty:
Return (invalid expression)
Pop the top element from record and store it in top
Set check to true
While top is not '(':
If top is an operator (+, -, *, /):
Set check to false
Pop the top element from record and store it in top
If check is true:
Set result to true

Else:
Push ch onto record

Print "Expression: " + exp
If result is true:
Print "Extra brackets exist"
Else:
Print "Extra brackets do not exist"
``````

## Algorithm

1. Create a class called `Expression`.
2. Define a function called `isExtraBracket` that takes a string `exp` as a parameter.
3. Create an empty stack called `record`.
4. Create a boolean variable called `result` and set it to false. This variable will be used to store the result of whether extra brackets exist or not.
5. Create a boolean variable called `check` and set it to true. This variable will be used to check if brackets contain operators or not.
6. Iterate through each character `ch` in the input expression `exp`.
7. For each character, do the following: a. If the character is ')', it indicates the end of a bracket pair. Check if the stack `record` is empty, if it is, return as the expression is invalid. Otherwise, pop the top element from the stack `record` and store it in the variable `top`. b. Set `check` to true. c. While `top` is not '(', do the following: i. If `top` is an operator (+, -, *, /), set `check` to false, indicating that the bracket does not contain any operators. ii. Pop the top element from the stack `record` and store it in the variable `top`. d. If `check` is true, it means that the current bracket pair does not contain any operators, so set `result` to true. e. Otherwise, continue to the next character.
8. After processing all characters, print the original expression and the result based on the value of `result`.

## Code Solution

``````import java.util.Stack;
/*
Java program for
Check if expression contains extra brackets or not
*/
public class Expression
{
public void isExtraBracket(String exp)
{
// Get the length of given expression
int n = exp.length();
// Create an empty record
Stack < Character > record = new Stack < Character > ();
// Result indicator
boolean result = false;
boolean check = true;
// Iterate through the given expression
for (int i = 0; i < n; ++i)
{
if (exp.charAt(i) == ')')
{
if (record.isEmpty())
{
// Invalid expression
return;
}
char top = record.peek();
record.pop();
check = true;
while (top != '(')
{
if (top == '+' || top == '-' || top == '*' || top == '/')
{
check = false;
}
top = record.peek();
record.pop();
}
if (check == true)
{
// When operator not exist inside brackets
result = true;
}
}
else
{
record.push(exp.charAt(i));
}
}
// Display given expression
System.out.print("\n Expression : " + exp);
if (result == true)
{
System.out.print("\n Extra brackets exists");
}
else
{
System.out.print("\n Extra brackets not exists");
}
}
public static void main(String[] args)
{
String exp = "";
// Test
}
}``````

#### Output

`````` Expression : (a+b-(c + ((a+b))))
Extra brackets exists
Expression : ((a+b) -(b-(c*d)))
Extra brackets not exists
Expression : ((a+b) + (c+a))
Extra brackets not exists
Expression : (a+b) + ((c))
Extra brackets exists``````
``````// Include header file
#include <iostream>
#include <stack>
#include <string>

using namespace std;
/*
C++ program for
Check if expression contains extra brackets or not
*/
class Expression
{
public: void isExtraBracket(string exp)
{
// Get the length of given expression
int n = exp.length();
// Create an empty record
stack < char > record;
// Result indicator
bool result = false;
bool check = true;
// Iterate through the given expression
for (int i = 0; i < n; ++i)
{
if (exp[i] == ')')
{
if (record.empty())
{
// Invalid expression
return;
}
char top = record.top();
record.pop();
check = true;
while (top != '(')
{
if (top == '+' || top == '-' ||
top == '*' || top == '/')
{
check = false;
}
top = record.top();
record.pop();
}
if (check == true)
{
// When operator not exist inside brackets
result = true;
}
}
else
{
record.push(exp[i]);
}
}
// Display given expression
cout << "\n Expression : " << exp;
if (result == true)
{
cout << "\n Extra brackets exists";
}
else
{
cout << "\n Extra brackets not exists";
}
}
};
int main()
{
string exp = "";
// Test
return 0;
}``````

#### Output

`````` Expression : (a+b-(c + ((a+b))))
Extra brackets exists
Expression : ((a+b) -(b-(c*d)))
Extra brackets not exists
Expression : ((a+b) + (c+a))
Extra brackets not exists
Expression : (a+b) + ((c))
Extra brackets exists``````
``````// Include namespace system
using System;
using System.Collections.Generic;
/*
Csharp program for
Check if expression contains extra brackets or not
*/
public class Expression
{
public void isExtraBracket(String exp)
{
// Get the length of given expression
int n = exp.Length;
// Create an empty record
Stack < char > record = new Stack < char > ();
// Result indicator
Boolean result = false;
Boolean check = true;
// Iterate through the given expression
for (int i = 0; i < n; ++i)
{
if (exp[i] == ')')
{
if ((record.Count == 0))
{
// Invalid expression
return;
}
char top = record.Peek();
record.Pop();
check = true;
while (top != '(')
{
if (top == '+' || top == '-' || top == '*' || top == '/')
{
check = false;
}
top = record.Peek();
record.Pop();
}
if (check == true)
{
// When operator not exist inside brackets
result = true;
}
}
else
{
record.Push(exp[i]);
}
}
// Display given expression
Console.Write("\n Expression : " + exp);
if (result == true)
{
Console.Write("\n Extra brackets exists");
}
else
{
Console.Write("\n Extra brackets not exists");
}
}
public static void Main(String[] args)
{
// Test
}
}``````

#### Output

`````` Expression : (a+b-(c + ((a+b))))
Extra brackets exists
Expression : ((a+b) -(b-(c*d)))
Extra brackets not exists
Expression : ((a+b) + (c+a))
Extra brackets not exists
Expression : (a+b) + ((c))
Extra brackets exists``````
``````package main
import "fmt"
/*
Go program for
Check if expression contains extra brackets or not
*/

func isExtraBracket(exp string) {
// Get the length of given expression
var n int = len(exp)
// Create an empty record
var record = make([] byte, 0)
// Result indicator
var result bool = false
var check bool = true
// Iterate through the given expression
for i := 0 ; i < n ; i++ {
if exp[i] == ')' {
if len(record) == 0 {
// Invalid expression
return
}
var top byte = record[len(record) - 1]
record = record[: len(record) - 1]
check = true
for (top != '(') {
if top == '+' || top == '-' ||
top == '*' || top == '/' {
check = false
}
top = record[len(record) - 1]
record = record[: len(record) - 1]
}
if check == true {
// When operator not exist inside brackets
result = true
}
} else {
record = append(record, exp[i])
}
}
// Display given expression
fmt.Print("\n Expression : ", exp)
if result == true {
fmt.Print("\n Extra brackets exists")
} else {
fmt.Print("\n Extra brackets not exists")
}
}
func main() {

// Test
isExtraBracket("(a+b-(c + ((a+b))))")
isExtraBracket("((a+b) -(b-(c*d)))")
isExtraBracket("((a+b) + (c+a))")
isExtraBracket("(a+b) + ((c))")
}``````

#### Output

`````` Expression : (a+b-(c + ((a+b))))
Extra brackets exists
Expression : ((a+b) -(b-(c*d)))
Extra brackets not exists
Expression : ((a+b) + (c+a))
Extra brackets not exists
Expression : (a+b) + ((c))
Extra brackets exists``````
``````<?php
/*
Php program for
Check if expression contains extra brackets or not
*/
class Expression
{
public	function isExtraBracket(\$exp)
{
// Get the length of given expression
\$n = strlen(\$exp);
// Create an empty record
\$record = array();
// Result indicator
\$result = false;
\$check = true;
// Iterate through the given expression
for (\$i = 0; \$i < \$n; ++\$i)
{
if (\$exp[\$i] == ')')
{
if (empty(\$record))
{
// Invalid expression
return;
}
\$top = end(\$record);
array_pop(\$record);
\$check = true;
while (\$top != '(')
{
if (\$top == '+' || \$top == '-' ||
\$top == '*' || \$top == '/')
{
\$check = false;
}
\$top = end(\$record);
array_pop(\$record);
}
if (\$check == true)
{
// When operator not exist inside brackets
\$result = true;
}
}
else
{
array_push(\$record, \$exp[\$i]);
}
}
// Display given expression
echo("\n Expression : ".\$exp);
if (\$result == true)
{
echo("\n Extra brackets exists");
}
else
{
echo("\n Extra brackets not exists");
}
}
}

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

#### Output

`````` Expression : (a+b-(c + ((a+b))))
Extra brackets exists
Expression : ((a+b) -(b-(c*d)))
Extra brackets not exists
Expression : ((a+b) + (c+a))
Extra brackets not exists
Expression : (a+b) + ((c))
Extra brackets exists``````
``````/*
Node JS program for
Check if expression contains extra brackets or not
*/
class Expression
{
isExtraBracket(exp)
{
// Get the length of given expression
var n = exp.length;
// Create an empty record
var record = [];
// Result indicator
var result = false;
var check = true;
// Iterate through the given expression
for (var i = 0; i < n; ++i)
{
if (exp.charAt(i) == ')')
{
if ((record.length == 0))
{
// Invalid expression
return;
}
var top = record[record.length - 1];
record.pop();
check = true;
while (top != '(')
{
if (top == '+' || top == '-' ||
top == '*' || top == '/')
{
check = false;
}
top = record[record.length - 1];
record.pop();
}
if (check == true)
{
// When operator not exist inside brackets
result = true;
}
}
else
{
record.push(exp.charAt(i));
}
}
// Display given expression
process.stdout.write("\n Expression : " + exp);
if (result == true)
{
process.stdout.write("\n Extra brackets exists");
}
else
{
process.stdout.write("\n Extra brackets not exists");
}
}
}

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

#### Output

`````` Expression : (a+b-(c + ((a+b))))
Extra brackets exists
Expression : ((a+b) -(b-(c*d)))
Extra brackets not exists
Expression : ((a+b) + (c+a))
Extra brackets not exists
Expression : (a+b) + ((c))
Extra brackets exists``````
``````#    Python 3 program for
#    Check if expression contains extra brackets or not
class Expression :
def isExtraBracket(self, exp) :
#  Get the length of given expression
n = len(exp)
#  Create an empty record
record = []
#  Result indicator
result = False
check = True
i = 0
#  Iterate through the given expression
while (i < n) :
if (exp[i] == ')') :
if ((len(record) == 0)) :
#  Invalid expression
return

top = record[-1]
record.pop()
check = True
while (top != '(') :
if (top == '+'
or top == '-'
or top == '*'
or top == '/') :
check = False

top = record[-1]
record.pop()

if (check == True) :
#  When operator not exist inside brackets
result = True

else :
record.append(exp[i])

i += 1

#  Display given expression
print("\n Expression : ", exp, end = "")
if (result == True) :
print("\n Extra brackets exists", end = "")
else :
print("\n Extra brackets not exists", end = "")

def main() :
#  Test

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

#### Output

`````` Expression :  (a+b-(c + ((a+b))))
Extra brackets exists
Expression :  ((a+b) -(b-(c*d)))
Extra brackets not exists
Expression :  ((a+b) + (c+a))
Extra brackets not exists
Expression :  (a+b) + ((c))
Extra brackets exists``````
``````#    Ruby program for
#    Check if expression contains extra brackets or not
class Expression
def isExtraBracket(exp)
#  Get the length of given expression
n = exp.length
#  Create an empty record
record = []
#  Result indicator
result = false
check = true
i = 0
#  Iterate through the given expression
while (i < n)
if (exp[i] == ')')
if ((record.length == 0))
#  Invalid expression
return
end

top = record.last
record.pop()
check = true
while (top != '(')
if (top == '+' || top == '-' ||
top == '*' || top == '/')
check = false
end

top = record.last
record.pop()
end

if (check == true)
#  When operator not exist inside brackets
result = true
end

else

record.push(exp[i])
end

i += 1
end

#  Display given expression
print("\n Expression : ", exp)
if (result == true)
print("\n Extra brackets exists")
else

print("\n Extra brackets not exists")
end

end

end

def main()
#  Test
end

main()``````

#### Output

`````` Expression : (a+b-(c + ((a+b))))
Extra brackets exists
Expression : ((a+b) -(b-(c*d)))
Extra brackets not exists
Expression : ((a+b) + (c+a))
Extra brackets not exists
Expression : (a+b) + ((c))
Extra brackets exists``````
``````import scala.collection.mutable._;
/*
Scala program for
Check if expression contains extra brackets or not
*/
class Expression()
{
def isExtraBracket(exp: String): Unit = {
// Get the length of given expression
var n: Int = exp.length();
// Create an empty record
var record: Stack[Character] = new Stack[Character]();
// Result indicator
var result: Boolean = false;
var check: Boolean = true;
var i: Int = 0;
// Iterate through the given expression
while (i < n)
{
if (exp.charAt(i) == ')')
{
if (record.isEmpty)
{
// Invalid expression
return;
}
var top: Char = record.top;
record.pop;
check = true;
while (top != '(')
{
if (top == '+' || top == '-' ||
top == '*' || top == '/')
{
check = false;
}
top = record.top;
record.pop;
}
if (check == true)
{
// When operator not exist inside brackets
result = true;
}
}
else
{
record.push(exp.charAt(i));
}
i += 1;
}
// Display given expression
print("\n Expression : " + exp);
if (result == true)
{
print("\n Extra brackets exists");
}
else
{
print("\n Extra brackets not exists");
}
}
}
object Main
{
def main(args: Array[String]): Unit = {
var task: Expression = new Expression();
// Test
}
}``````

#### Output

`````` Expression : (a+b-(c + ((a+b))))
Extra brackets exists
Expression : ((a+b) -(b-(c*d)))
Extra brackets not exists
Expression : ((a+b) + (c+a))
Extra brackets not exists
Expression : (a+b) + ((c))
Extra brackets exists``````
``````import Foundation;
/*
Swift 4 program for
Check if expression contains extra brackets or not
*/
struct Stack
{
private
var items: [Character] = []
func peek()->Character
{
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: Character)
{
items.insert(data, at: 0)
}
}
class Expression
{
func isExtraBracket(_ e: String)
{
let exp = Array(e);
// Get the length of given expression
let n: Int = exp.count;
// Create an empty record
var record = Stack();
// Result indicator
var result: Bool = false;
var check: Bool = true;
var i: Int = 0;
// Iterate through the given expression
while (i < n)
{
if (exp[i] == ")")
{
if (record.isEmpty())
{
// Invalid expression
return;
}
var top: Character = record.peek();
record.pop();
check = true;
while (top  != "(")
{
if (top == "+" || top == "-" ||
top == "*" || top == "/")
{
check = false;
}
top = record.peek();
record.pop();
}
if (check == true)
{
// When operator not exist inside brackets
result = true;
}
}
else
{
record.push(exp[i]);
}
i += 1;
}
// Display given expression
print("\n Expression : ", e, terminator: "");
if (result == true)
{
print("\n Extra brackets exists", terminator: "");
}
else
{
print("\n Extra brackets not exists", terminator: "");
}
}
}
func main()
{
// Test
}
main();``````

#### Output

`````` Expression :  (a+b-(c + ((a+b))))
Extra brackets exists
Expression :  ((a+b) -(b-(c*d)))
Extra brackets not exists
Expression :  ((a+b) + (c+a))
Extra brackets not exists
Expression :  (a+b) + ((c))
Extra brackets exists``````
``````import java.util.Stack;
/*
Kotlin program for
Check if expression contains extra brackets or not
*/
class Expression
{
fun isExtraBracket(exp: String): Unit
{
// Get the length of given expression
val n: Int = exp.length;
// Create an empty record
val record: Stack < Char > = Stack < Char > ();
// Result indicator
var result: Boolean = false;
var check: Boolean ;
var i: Int = 0;
// Iterate through the given expression
while (i < n)
{
if (exp.get(i) == ')')
{
if (record.empty())
{
// Invalid expression
return;
}
var top: Char = record.peek();
record.pop();
check = true;
while (top != '(')
{
if (top == '+' || top == '-' ||
top == '*' || top == '/')
{
check = false;
}
top = record.peek();
record.pop();
}
if (check == true)
{
// When operator not exist inside brackets
result = true;
}
}
else
{
record.push(exp.get(i));
}
i += 1;
}
// Display given expression
print("\n Expression : " + exp);
if (result == true)
{
print("\n Extra brackets exists");
}
else
{
print("\n Extra brackets not exists");
}
}
}
fun main(args: Array < String > ): Unit
{
// Test
}``````

#### Output

`````` Expression : (a+b-(c + ((a+b))))
Extra brackets exists
Expression : ((a+b) -(b-(c*d)))
Extra brackets not exists
Expression : ((a+b) + (c+a))
Extra brackets not exists
Expression : (a+b) + ((c))
Extra brackets exists``````

## Time Complexity

The time complexity of the algorithm is O(n), where n is the number of characters in the input expression `exp`. This is because we perform a single pass through the input expression, and each character is processed once. The use of the stack does not significantly affect the overall time complexity.

## Comment

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