Stack

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 string exp 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 expression exp.
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.
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.

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

Name