Check if an expression has redundant brackets

Medium

Problem

Return true if the expression contains a pair of parentheses with no operator directly inside it, such as "((a+b))" or "(a)".

Example 1

Input:  "((a+b))"
Output: true

Example 2

Input:  "(a+(b)/c)"
Output: true

"(b)" is redundant.

Example 3

Input:  "(a+b*(c-d))"
Output: false

Also asked as: Expression contains redundant bracket or not

Test cases

Case 1

Input:    "((a+b))"
Expected: true

Case 2

Input:    "(a+(b)/c)"
Expected: true

Case 3

Input:    "(a+b*(c-d))"
Expected: false

Case 4

Input:    "a+b"
Expected: false

Your solution ✓ Solved

Ctrl/⌘ + Enter to run
View solutionHide solution1 approach

1. Stack — a ")" with no operator since its "(" is redundant

Time O(n)Space O(n)

Push everything except ")". On ")", pop until "("; if you saw no operator in between, the brackets were redundant.

function hasRedundantBrackets(expr) {
const st = [];
for (const c of expr) {
if (c === ')') {
let hasOp = false;
while (st.length && st[st.length - 1] !== '(') {
if ('+-*/'.includes(st.pop())) hasOp = true;
}
st.pop(); // '('
if (!hasOp) return true;
} else st.push(c);
}
return false;
}