Problem

Given a valid arithmetic expression as a string, check if it contains any redundant braces. A set of braces is redundant if the subexpression inside it does not require the braces (i.e., there are no operators inside the braces).

Return:

  • 1 if redundant braces are present
  • 0 if not

The expression will only contain +, -, *, /, parentheses, and lowercase letters.

Examples

Example 1

1
2
3

Input: ((a + b))
Output: 1
Explanation: The outer braces are redundant.

Example 2

1
2
3

Input: (a + (a + b))
Output: 0
Explanation: No redundant braces present.

Solution

Method 1 – Stack-Based Scan

Intuition

Use a stack to track parentheses and operators. If a closing parenthesis is found and there are no operators between the matching opening and closing parenthesis, the braces are redundant.

Approach

  1. Traverse the string character by character.
  2. Push opening braces and operators onto the stack.
  3. On encountering a closing brace:
    • If the top of the stack is an opening brace, braces are redundant.
    • Otherwise, pop until an opening brace is found, then pop the opening brace.
  4. If any redundant braces are found, return 1. Otherwise, return 0.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
public:
	int braces(string A) {
		stack<char> st;
		for (char c : A) {
			if (c == '(' || c == '+' || c == '-' || c == '*' || c == '/') {
				st.push(c);
			} else if (c == ')') {
				if (st.top() == '(') return 1;
				while (!st.empty() && st.top() != '(') st.pop();
				st.pop();
			}
		}
		return 0;
	}
};
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution {
	public int braces(String A) {
		Stack<Character> stack = new Stack<>();
		for (int i = 0; i < A.length(); i++) {
			char c = A.charAt(i);
			if (c == '(' || c == '+' || c == '-' || c == '*' || c == '/') {
				stack.push(c);
			} else if (c == ')') {
				if (stack.peek() == '(') return 1;
				while (!stack.isEmpty() && stack.peek() != '(') stack.pop();
				stack.pop();
			}
		}
		return 0;
	}
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

class Solution:
	def braces(self, A: str) -> int:
		st = []
		for c in A:
			if c in '()+-*/':
				st.append(c)
			elif c == ')':
				if st and st[-1] == '(': return 1
				while st and st[-1] != '(': st.pop()
				if st: st.pop()
		return 0

Complexity

  • ⏰ Time complexity: O(n), where n is the length of the string. Each character is processed once.
  • 🧺 Space complexity: O(n), for the stack in the worst case.
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

public static int braces(String A) {
	Stack<Character> stack = new Stack<>(); 
	int index = 0; 
	while(index < A.length()) { 
		char c = A.charAt(index); 
		if(c == '(' || c == '+' || c == '-' || c == '*' || c == '/') { 
			stack.push(c); 
		} 
		else if(c == ')') { 
			if(stack.peek() == '(') { 
				return 1; 
			} else { 
				while(!stack.isEmpty() && stack.peek() != '(') { 
					stack.pop(); 
				} 
				stack.pop(); 
			} 
		} 
		index++; 
	} 
	return 0; 
}