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:
-
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.
-
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
- Create a class called
Expression
. - Define a function called
isExtraBracket
that takes a stringexp
as a parameter. - Create an empty stack called
record
. - 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. - Create a boolean variable called
check
and set it to true. This variable will be used to check if brackets contain operators or not. - Iterate through each character
ch
in the input expressionexp
. - 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 stackrecord
and store it in the variabletop
. b. Setcheck
to true. c. Whiletop
is not '(', do the following: i. Iftop
is an operator (+, -, *, /), setcheck
to false, indicating that the bracket does not contain any operators. ii. Pop the top element from the stackrecord
and store it in the variabletop
. d. Ifcheck
is true, it means that the current bracket pair does not contain any operators, so setresult
to true. e. Otherwise, continue to the next character. - 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)
{
Expression task = new Expression();
String exp = "";
// Test
task.isExtraBracket("(a+b-(c + ((a+b))))");
task.isExtraBracket("((a+b) -(b-(c*d)))");
task.isExtraBracket("((a+b) + (c+a))");
task.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
// 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()
{
Expression *task = new Expression();
string exp = "";
// Test
task->isExtraBracket("(a+b-(c + ((a+b))))");
task->isExtraBracket("((a+b) -(b-(c*d)))");
task->isExtraBracket("((a+b) + (c+a))");
task->isExtraBracket("(a+b) + ((c))");
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)
{
Expression task = new Expression();
// Test
task.isExtraBracket("(a+b-(c + ((a+b))))");
task.isExtraBracket("((a+b) -(b-(c*d)))");
task.isExtraBracket("((a+b) + (c+a))");
task.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
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()
{
$task = new Expression();
// Test
$task->isExtraBracket("(a+b-(c + ((a+b))))");
$task->isExtraBracket("((a+b) -(b-(c*d)))");
$task->isExtraBracket("((a+b) + (c+a))");
$task->isExtraBracket("(a+b) + ((c))");
}
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()
{
var task = new Expression();
// Test
task.isExtraBracket("(a+b-(c + ((a+b))))");
task.isExtraBracket("((a+b) -(b-(c*d)))");
task.isExtraBracket("((a+b) + (c+a))");
task.isExtraBracket("(a+b) + ((c))");
}
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() :
task = Expression()
# Test
task.isExtraBracket("(a+b-(c + ((a+b))))")
task.isExtraBracket("((a+b) -(b-(c*d)))")
task.isExtraBracket("((a+b) + (c+a))")
task.isExtraBracket("(a+b) + ((c))")
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()
task = Expression.new()
# Test
task.isExtraBracket("(a+b-(c + ((a+b))))")
task.isExtraBracket("((a+b) -(b-(c*d)))")
task.isExtraBracket("((a+b) + (c+a))")
task.isExtraBracket("(a+b) + ((c))")
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
task.isExtraBracket("(a+b-(c + ((a+b))))");
task.isExtraBracket("((a+b) -(b-(c*d)))");
task.isExtraBracket("((a+b) + (c+a))");
task.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
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()
{
let task: Expression = Expression();
// Test
task.isExtraBracket("(a+b-(c + ((a+b))))");
task.isExtraBracket("((a+b) -(b-(c*d)))");
task.isExtraBracket("((a+b) + (c+a))");
task.isExtraBracket("(a+b) + ((c))");
}
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
{
val task: Expression = Expression();
// Test
task.isExtraBracket("(a+b-(c + ((a+b))))");
task.isExtraBracket("((a+b) -(b-(c*d)))");
task.isExtraBracket("((a+b) + (c+a))");
task.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
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.
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