Expression contains redundant bracket or not

Summary

Given a string expression, determine whether it contains any redundant brackets or not. A bracket is considered redundant if there is an unmatched opening or closing bracket. This problem involves working with strings and using stack-based approach to solve the problem.

Detailed Explanation

To solve this problem, we can use a stack data structure. The idea is to iterate through the string expression from left to right. For every opening bracket, push it onto the stack. For every closing bracket, check if the top of the stack contains an opening bracket that matches the current closing bracket. If there's no match or the stack is empty (which means there are unmatched opening brackets), return false.

Here's a step-by-step breakdown of the solution:

Initialize an empty stack.
Iterate through the string expression from left to right.
For every opening bracket, push it onto the stack.
For every closing bracket:
- Check if the top of the stack contains an opening bracket that matches the current closing bracket.
- If there's no match or the stack is empty (which means there are unmatched opening brackets), return false.
After iterating through the entire expression, check if the stack is empty. If it is not empty, there are unmatched opening brackets and the function should return false.

Time complexity: O(n) where n is the length of the input string. Space complexity: O(n) for storing the stack.

  +---+---+---+---+---+
  |   |   |   |   |
  +---+---+---+---+---+
  ^
  Stack

Optimized Solutions

Java

View GeeksforGeeks Problem

public boolean hasRedundantBrackets(String expression) {
    Stack<Character> stack = new Stack<>();
    for (char c : expression.toCharArray()) {
        if (c == '(') {
            stack.push(c);
        } else if (c == ')') {
            if (stack.isEmpty() || stack.pop() != '(') {
                return true;
            }
        }
    }
    return stack.isEmpty();
}

Code Editor (Testing phase)

Improve Your Solution

Use the editor below to refine the provided solution. Select a programming language and try the following:

Add import statement if required.
Optimize the code for better time or space complexity.
Add test cases to validate edge cases and common scenarios.
Handle error conditions or invalid inputs gracefully.
Experiment with alternative approaches to deepen your understanding.

Click "Run Code" to execute your solution and view the output. If errors occur, check the line numbers and debug accordingly. Resize the editor by dragging its bottom edge.