# Stacks: Balanced Brackets

# Stacks: Balanced Brackets

dgodfrey + 37 comments After writing several bad programs that barely passed the test cases, I was able to come up with this cool solution:

bool is_balanced(string expression) { stack<char> s; for (char c : expression) { if (c == '{') s.push('}'); else if (c == '[') s.push(']'); else if (c == '(') s.push(')'); else { if (s.empty() || c != s.top()) return false; s.pop(); } } return s.empty(); }

ryyanj + 0 comments Great Answer. I think this is what interviewers would be looking for. Clean and easy to understand.

lahouari + 10 comments Very cool solution, here is with java:

public static boolean isBalanced(String expression) { // Must be even if ((expression.length() & 1) == 1) return false; else { char[] brackets = expression.toCharArray(); Stack<Character> s = new Stack<>(); for (char bracket : brackets) switch (bracket) { case '{': s.push('}'); break; case '(': s.push(')'); break; case '[': s.push(']'); break; default : if (s.empty() || bracket != s.peek()) return false; s.pop(); } return s.empty(); } }

Good continuation.

sdo_semenov + 1 comment Deque is prefered over Stack

m4rkuz + 1 comment Why?

amangarg4804 + 0 comments "A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class." For example:

Deque stack = new ArrayDeque();

See java docs: http://docs.oracle.com/javase/7/docs/api/java/util/Stack.html

https://docs.oracle.com/javase/7/docs/api/java/util/Deque.html

njjnex + 0 comments Better to replace

bracket != s.peek()

with

bracket != s.pop()

so you dont need to .pop() it later

SruthiPotluri + 2 comments Please clarify, why should we have return stack.empty(); y not return true;

karan_08 + 0 comments nice approach man!

dharani + 1 comment *

*& 1) **This is not required .ajayr_ec07 + 1 comment *&1) is required because it does the "and" operation with the length and returns 1 if even and 0 if odd.

dharani + 0 comments thanks

behnam_azizi_13 + 0 comments Nice solution! Good job! I could not think of this

snatenkov + 0 comments Is there any reason to prefer the bitwise operation to the modulo one?

if (expression.length()%2 == 1) return false;

agas3005 + 0 comments after return false in default part,need to insert break,right?.....or return false means what is the effect of this.please explain me

ms_yalitan + 0 comments what does (expression.length() & 1) mean?

GeoMatt22 + 1 comment Nice solution.

For the even-length optimization at the beginning, you could apply this

*any*time the stack is cleared, no? (i.e. keeping track of the remaining length as you go)siebenschlaefer + 0 comments Everytime your stack becomes empty you have read an even number of characters. Therefore it's sufficient to check the length once.

SurajGalande + 1 comment C# Equivalent:

static string matchBrackets(char[] chars){ Stack s = new Stack(); foreach(char c in chars){ if(c== '{') s.Push('}'); else if(c== '(') s.Push(')'); else if(c== '[') s.Push(']'); else { if (s.Count == 0 || c != (char)s.Peek()) return "NO"; s.Pop(); } } return s.Count == 0 ? "YES": "NO"; }

rfahmed01 + 1 comment Could somebody explain what the following code is doing? c != (char)s.Peek())

I know that peek() retrieves the data of the item on the top of the stack.

lahouari + 1 comment Because the author of the C# code hasn't used the generic version of the Stack class

Stack s = new Stack();

used rather than

Stack<char> s = new Stack<char>();

so he must do an explicit cast when retrieving elements from the Stack.

rfahmed01 + 1 comment Oh yeah, I do understand the type casting part. What I'm confused on is what the following is doing? Why do we need to check that the current value c does not equal to s.Peek()? c != s.Peek())

lahouari + 0 comments If the current character is a closed bracket and he must be } but the last pushed character in stack is ) or ] so we can deduce that the expression is not balanced. Sample test case: {[()[}]}

WittyNotes + 3 comments Aha: THAT's the clever answer I should've gone for. Beats my straightforward approach:

public static boolean isBalanced(String expression) { Stack<Character> stack = new Stack<>(); for(char c : expression.toCharArray()){ switch (c){ case '{': case '[': case '(': stack.push(c); break; case '}': if (stack.isEmpty() || stack.pop() != '{') return false; break; case ']': if (stack.isEmpty() || stack.pop() != '[') return false; break; case ')': if (stack.isEmpty() || stack.pop() != '(') return false; break; }// end switch }// end for if (!stack.isEmpty()) return false; return true; }

amar_s1 + 0 comments try }}

phturakhia + 0 comments [deleted]anitakhare + 0 comments Your code will not work as stack.pop() returns a void. You need to check the character with top() and do a pop() after the return. Here is the correct code: case '}': if (stack.isEmpty() || stack.top() != '{') return false; stack.pop(); break;

tshrjn + 7 comments Python3 equivalent:

def is_matched(expression): stack = [] dicty = {'(':')', '[':']', '{':'}'} for x in expression: if dicty.get(x): stack.append(dicty[x]) else: if len(stack) == 0 or x != stack[len(stack)-1]: return False stack.pop() return len(stack) == 0

nyc3721 + 0 comments [deleted]nyc3721 + 4 comments More Pythonic:

def is_matched(expression): pairs = {'{' : '}', '[' : ']', '(' : ')'} sk = [] for c in expression: if c in pairs: sk.append(pairs[c]) elif sk and c == sk[-1]: sk.pop() else: return False return not sk

madhavsharma + 0 comments Yes ofc, but it's good to post versions that are as pythonic as possible. When you're not posting it's not really efficient to be that up tight.

jsjfuentesj + 1 comment Even more pythonic

def is_matched(expression): pairs = {'{' : '}', '[' : ']', '(' : ')'} sk = [] for c in expression: if c in pairs: sk.append(pairs[c]) elif not sk or c != sk.pop(): return False return not sk

chukwudumiebi + 0 comments Any performance gains by adding:

if(len(expression)%2)>0: return False

at the beginning of the function, just in case an input is uneven, so we don't bother doing any other thing.

hellomici + 0 comments Looks nice, but unfortunately this isn't passing, as mine either:

def is_matched(expression): d = {'{': '}', '[': ']', '(': ')'} if len(expression) % 2 != 0: return False for n, i in enumerate(expression): if i in d and n < (len(expression)/2): if d[i] != expression[len(expression)-n-1]: return False return True

I don't exactly understand why... Any help is appreciated :)

ghaderi_amin + 0 comments Can you explain the code?

madhavsharma + 0 comments slightly cleaner style:

def is_matched(expression): pairs_dict = {'}': '{', ']': '[', ')': '('} stack = [] for char in expression: if char in pairs_dict.values(): stack.append(char) elif char in pairs_dict: if not stack or pairs_dict[char] != stack.pop(): return False return not stack

MaxNRG + 0 comments Python 3 dictionary solution:

def is_matched(expression): brackets = {'{': 1, '}': -1, '[': 2, ']': -2, '(': 4, ')': -4} stack = [] for i in expression: if stack and stack[-1] + brackets[i] == 0: stack.pop() elif brackets[i] > 0: stack.append(brackets[i]) else: return False return not stack

nallam_rohith + 0 comments It is returning False for [{]}

maarichimitra + 0 comments This code fails if the input has variables in expression.

devlware + 0 comments Nice solution.

ken_caron + 0 comments JavaScript port for fun:

function is_balanced(expression) { let s = []; expression = expression.split(''); for (let c = 0; c < expression.length; c++) { if (expression[c] === '{') { s.push('}'); } else if (expression[c] === '[') { s.push(']'); } else if (expression[c] === '(') { s.push(')'); } else { if ((s.length === 0) || expression[c] !== s[s.length-1]) { return false; } s.pop(); } }; return (s.length === 0); }

sattujaiswal + 0 comments great

andremlsantos + 0 comments perfect, well done!

sethg13 + 1 comment I added some comments for those having some trouble understanding what's happening.

bool is_balanced(string expression) { stack<char> s; //stack of right bracket expectations for(char c : expression) { switch(c) { case '(': s.push(')'); break; case '[': s.push(']'); break; case '{': s.push('}'); break; default: // once you have iterated passed the left brackets // compare right bracket with the one expected if(s.empty() || c != s.top()) return false; s.pop(); // it matches, so remove it } } return s.empty(); // stack must be even // this checks for leftover right brackets in the stack // the s.empty() in default checks for excess left brackets }

lllapoklyak + 0 comments Thank you for comments!

tjeubaoit + 0 comments Nice solution

danique + 0 comments It is really a great solution, I just have few corrections to add: - Stack s = new Stack(); - for(char c: expression.toCharArray()) - if(s.empty() || c!=s.peek())

rajaryan1600 + 1 comment Can you explain why am I getting segmentation fault in this approach?

stack<char> s; int i, l = e.length(); char ch; for(i = 0;i<l;i++) { if(e[i] == '{' || e[i] == '[' || e[i] == '(') s.push(e[i]); else { if(e[i] == '}') { ch = s.top(); s.pop(); if(ch!='{') return false; } else if(e[i] == ']') { ch = s.top(); s.pop(); if(ch!='[') return false; } else if(e[i] == ')') { ch = s.top(); s.pop(); if(ch!='(') return false; } } } return (s.empty());

ningjinxiao + 0 comments Imagine that the first expression is simply '}'. What is the state of your stack the first time you try to top() or pop() a value from it?

Akshita_Sood + 0 comments What is the significance of returning s.empty() ? When will it return true ?

adwydman + 0 comments This is my JavaScript version of this solution:

function is_balanced(expression) { const stack = []; const brackets = { "{": "}", "[": "]", "(": ")" }; for (let i = 0; i < expression.length; i++) { const b = expression[i]; if (brackets[b] !== undefined) stack.push(brackets[b]); // it's an opening bracket, so push the corresponding closing one into the stack else { if (stack.length === 0 || b !== stack[stack.length-1]) return false; stack.pop(); } } return stack.length === 0; }

If you write a simple hash map like the

`brackets`

object, you don't need to explicitly check if a given bracket is a closing one by using`if`

s. Just see if the hash map has the desired key (in this case an opening bracket). If so, push the value into the stack (in this case a closing bracket). The rest is pretty much the same.flavius_deux + 0 comments If its length % 2 is not 0, then it cannot be balanced. Wouldnt you want to start with that first?

akshay_suryavan1 + 0 comments Awesome technique, here's a ruby implementation

def is_balanced(expression) exp_stack = [] # Stack in ruby can be created using an array # Related stack functions are Array#push, Array#pop, Array#last # Array#push appends an element to the array # Array#pop removes and returns last element in the array # Array#last returns the last element in the array expression.each do |char| if char == '{' exp_stack.push('}') elsif char == '[' exp_stack.push(']') elsif char == '(' exp_stack.push(')') else if (exp_stack.empty? || char != exp_stack.last) return false end exp_stack.pop end end return exp_stack.empty? end

daminiaglawe30 + 0 comments superb!!!

ArshbeerSingh + 0 comments I would also like to add-

if(expression.length() % 2 != 0) { return false; }

as if the number of brackets are balanced then the length of string will be even.

witalobenicio + 0 comments Really great and simple answer. Such a beautiful code.

gepeppe + 0 comments The problem is that it doesn't work if there are other character beyond brackets: {[aa(d)]}

awiwipapa + 0 comments beautiful

DevHoyops + 0 comments Wow, after looking at this it seems so simple. can't believe I didn't think to push the opposite brackets and pop if they match after the open brackets. Very sleek and clean. My program had atleast two helper functions haha. Nice job!

byte_me_bro + 0 comments this code is prettier than gal gadot

sumankalyan_52 + 0 comments Easy and simple. Nice Work.

keencontacts + 0 comments Nice, succinct solution. Would catch Testcase 4 which my solution struggled to catch (if string length is not even and ends with an opening bracket).

ArmadaNasar + 1 comment why do I got segfault for this simple code? The idea is to push the openings then if I found the closing one, pop and match. If it is not matching, then return false.

//this problem is simple, but why the heck I got segfault on this? stack<char> buka; for (int i = 0; i < expression.length(); i++) { if (c == '(' || c == '{' || c == '[') buka.push(c); else if (c == ')') { temp = buka.top(); if (temp != '(' || buka.empty()) { return false; } buka.pop(); } else if (c == '}') { temp = buka.top(); if (temp != '{' || buka.empty()) { return false; } buka.pop(); } else if (c == ']') { temp = buka.top(); if (temp != '[' || buka.empty()) { return false; } buka.pop(); } }

siebenschlaefer + 0 comments Looks good, except for two minor issues.

- You test
`c`

without assigning a value to it. - You call
`buka.top()`

before checking`buka.empty()`

.

- You test

PouyaBisadi + 0 comments Beautiful code. You can remove

*s.pop()*and use it instead of*s.top()*as you pop the last char anyway.agarwalrahul + 0 comments Does your code works properly?

nakar_tamir + 0 comments Beautiful.

123ss123 + 0 comments can u explain your code pls

khuatgia + 0 comments Hi. May I ask what language is this ? it looks like C or C++ for me. I wrote mine in Java but got runtime error. Thank you.

polad + 0 comments Cool!

stomatrix + 11 comments here's my pythonic solution

def is_matched(e): while( len(e) > 0): t = e e = e.replace('()','') e = e.replace('{}','') e = e.replace('[]','') if t == e: return False return True

androiditya + 0 comments paaji tusi great ho

raky_hacky + 0 comments very unique logic, good job stomatrix, it took some time for me to undertstand this logic :)

kalashnikova + 0 comments man, python solutions always blow.

is like

my python code:

def whatever gimme_result();

There, done.

LOL

salvatore_pj + 0 comments [deleted]Upadhyay_himansh + 0 comments This is best solution...

KabirKang + 1 comment Isn't this O(N^2)?

You go through and find pairs within the expression many times. Can someone help me with the complexity of this solution? It could be N+(N-1)+(N-2)+(N-3) which is O(N^2)

arturoangeles + 0 comments I think is N , you pass again, on the string but what is left of it , it was not inmutable , it would be visiting each chunk (e.g. '()' ) once. Being inmutable means N space.

awiwipapa + 0 comments awesome!

tianerb + 0 comments I tested it on leetcode and it was actually much slower than the dict and stack solution (30ms v.s. 100ms). Great idea though!

Watercycle + 0 comments I benchmarked the following against the stack version:

def rbalanced?(str) until str.empty? prev = str str = str.gsub /\(\)|\[\]|{}/, "" return false if str == prev end true end

On average input, the regex version was always within a factor of 2 of the stack version and appeared to be O(n). However, for large, unideal input (i.e. "(((((( ...") the regex solution is clearly O(n^2). Which makes sense of course. Both the while loop and replace regex are O(n)

BrownBatman + 0 comments Absolutely wonderful solution.

balasriharsha1 + 0 comments Awesome, Work dude

nevertoolate + 3 comments I initially misunderstand the problem. I thought you don't really need a stack. Just traverse the string in lock step from both ends. Return false when there is a mismatch. But looking at the failing tests I realized that the example and the explanation of the problem is incomplete.

carlyonj + 0 comments [deleted]petes40 + 0 comments Too be fair, it is quite a common coding problem (although often made more complex by having non-brackets in the string as well) and also it does mention stacks in the question. Nevertoolate to give it another go though, and sounds like you got there in the end ;-)

by424 + 2 comments Python solution using stack principle:

`def is_matched(expression): dic = {'{':'}','[':']','(':')'} lst =[] for i in expression: if i in dic.keys(): lst.append(dic[i]) elif len(lst)>0 and i==lst[-1]: lst.pop() else: return False return len(lst) == 0`

balasriharsha1 + 0 comments This is just awesome, I wish I can code like this

marcin_tustin + 2 comments Poor examples. For example, this is a case not alluded to in the description:

}][}}(}][))] => No {()} => Yes () => Yes ({}([][])) => Yes {))}(())(

SuomynonA + 0 comments Agreed. That really pissed me off.

cphayash + 0 comments Wow... No wonder a bunch of the tests kept failing for me... Agreed, the description is very misleading for cases like this.

I was simply splitting the expression in half, reversing the second set and comparing the characters... Glad you pointed this out. Thanks, Marcin!

Sort 402 Discussions, By:

Please Login in order to post a comment