dgodfrey 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 Great Answer. I think this is what interviewers would be looking for. Clean and easy to understand.
lahouari 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 Deque is prefered over Stack
m4rkuz Why?
amangarg4804 "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 Better to replace
bracket != s.peek()
with
bracket != s.pop()
so you dont need to .pop() it later
SruthiPotluri Please clarify, why should we have return stack.empty(); y not return true;
karan_08 nice approach man!
dharani *& 1) * This is not required .
ajayr_ec07 *&1) is required because it does the "and" operation with the length and returns 1 if even and 0 if odd.
dharani thanks
behnam_azizi_13 Nice solution! Good job! I could not think of this
snatenkov Is there any reason to prefer the bitwise operation to the modulo one?
if (expression.length()%2 == 1) return false;
agas3005 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 what does (expression.length() & 1) mean?
GeoMatt22 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 Everytime your stack becomes empty you have read an even number of characters. Therefore it's sufficient to check the length once.
SurajGalande 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 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 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 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 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 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 try }}
phturakhia [deleted]anitagov 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 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 [deleted]nyc3721 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 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 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 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 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 Can you explain the code?
madhavsharma 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 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 It is returning False for [{]}
maarichimitra This code fails if the input has variables in expression.
devlware Nice solution.
ken_caron 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 great
andremlsantos perfect, well done!
sethg13 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 Thank you for comments!
tjeubaoit Nice solution
danique 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 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 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 What is the significance of returning s.empty() ? When will it return true ?
adwydman 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
bracketsobject, you don't need to explicitly check if a given bracket is a closing one by usingifs. 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 If its length % 2 is not 0, then it cannot be balanced. Wouldnt you want to start with that first?
akshay_suryavan1 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 superb!!!
ArshbeerSingh 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 Really great and simple answer. Such a beautiful code.
gepeppe The problem is that it doesn't work if there are other character beyond brackets: {[aa(d)]}
awiwipapa beautiful
DevHoyops 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 this code is prettier than gal gadot
sumankalyan_52 Easy and simple. Nice Work.
keencontacts 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 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 Looks good, except for two minor issues.
- You test
cwithout assigning a value to it. - You call
buka.top()before checkingbuka.empty().
- You test
PouyaBisadi Beautiful code. You can remove s.pop() and use it instead of s.top() as you pop the last char anyway.
aggarwalrahul Does your code works properly?
nakar_tamir Beautiful.
123ss123 can u explain your code pls
stomatrix 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 paaji tusi great ho
raky_hacky very unique logic, good job stomatrix, it took some time for me to undertstand this logic :)
kalashnikova man, python solutions always blow.
is like
my python code:
def whatever gimme_result();
There, done.
LOL
salvatore_pj [deleted]
Upadhyay_himansh This is best solution...
KabirKang 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 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 awesome!
tianerb 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 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 Absolutely wonderful solution.
balasriharsha1 Awesome, Work dude
nevertoolate 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.
by424 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 This is just awesome, I wish I can code like this
marcin_tustin Poor examples. For example, this is a case not alluded to in the description:
}][}}(}][))] => No {()} => Yes () => Yes ({}([][])) => Yes {))}(())(
SuomynonA Agreed. That really pissed me off.
cphayash 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!
nishant_275 only one test case is not being passed, test case no. 9. Can Anyone help me out please. thanks in Advance
sashankaryal I have the same problem.
zenmasterchris Try a test case with only a single right bracket: "}"
alirafiq_01 so what's the solution? ... i tried putting in underflow condition but am unable to make it work.. can you help me.? here's my code:
class stck{ int top; char st[1001]; public: stck(){top=-1;} void push(char item){ top++; if(top<1001) st[top] = item; else top--; } char pop(){ top--; return st[top+1]; } }; bool is_balanced(string expression) { stck s; char c; int i=0; while(expression[i]){ if(expression[i]!='}' && expression[i]!=']' && expression[i]!=')' ) s.push(expression[i]); else{ c = s.pop(); switch (c){ case '{': if(expression[i]!='}') return 0; else break; case '[': if(expression[i]!=']') return 0; else break; case '(': if(expression[i]!=')') return 0; else break; } } i++; } return 1; }
krishnakeshav You only push the character if you have found it's counterpart. Try ro analyse soln given. You will get your mistake.
km2409 I have the same issue. Have you got any solution for it yet?
paul_coghlan Test case 9 always fails for me, too - but when I compile and run locally with the same test data there is no difference between my output and the desired output:
$ scala StackSolution.scala < ../input12.txt > test12.txt $ diff test12.txt ../output12.txtpawanagarwal_gr1 Check for following test cases - {{{{ - corrected by checking stack is empty when returning. { - corrected by checking input length the begginning of method.
alubin I had to test for "}()()()(())" before I realized what I was missing. To pass Test Case 9
km2409 For me it was just this expression: "))" that was failing in testcase 9. Finally got them all right.
chhikaradi [deleted]
mjordan0887 I made an assumption early one that proved to be a bad one, but from the description of the question and the sample test cases, I assumed that we only had to verify nested balanced expressions, not balanced expressions that were side-by-side.
For example, it was only obvious we had to test for situations like '()' and '(({{[[]]}}))', not '{()}'. Can we update the question to specify this? Or am I the only one that made this mistake?
hpineda83 did the same mistake, examples are misleading
prasadh_13 Java solution:
public static boolean isBalanced(String expression) { Stack<Character> expressionStack = new Stack<Character>(); if(expression.length() == 0) return false; for(int i = 0; i < expression.length(); i++) { char c = expression.charAt(i); switch(c) { case ')': if(expressionStack.empty() || (Character)expressionStack.pop() != '(') return false; break; case '}': if(expressionStack.empty() || (Character)expressionStack.pop() != '{') return false; break; case ']': if(expressionStack.empty() || (Character)expressionStack.pop() != '[') return false; break; default: expressionStack.push(c); } } if(!expressionStack.empty()) return false; return true; }
ejjhaynes The only thing I was missing was that last line about the stack not being empty! Thanks for your solution.
rgilbertpaul Checking
if(expression.length() == 0) return false;on line 3 is actually incorrect for this problem, but there is no test case for it. By the definition of the problem, empty string should be valid.alanchou And you don't really need that line, if length is 0 the code skips the loop and check if the new stack is empty(which it is) and returns true. You could just do return expressionStack.isEmpty(); to save some line
TWiStErRob Ah, the good old
if (cond) return true; else return false;:)Do you have a specific reason to do this? (The first time I wrote similar to this (at uni) I literally LOL'd at myself when noticed.)
if (!expressionStack.empty()) return false; return true;
which is the same as (inverted)
if (expressionStack.empty()) return true; /*else*/ return false;
which is the same as (simplified)
return expressionStack.empty();
(If you use an IDE like IntelliJ IDEA it should warn you about these with inspections and you can fix the via a quick fix.)
kalashnikova ha! this is so real. Very elegant!
snapdogfall How are you populating the expressionStack?
TWiStErRob Are you looking for
default: expressionStack.push(c);
amanmibra Here is an alternative Java solution:
public static boolean isBalanced(String s) { String left = "{[("; String right= "}])"; if(s.length()%2 != 0)return false; Stack<Character> stack = new Stack<>(); for(int i = 0; i < s.length(); i++){ if(left.indexOf(s.charAt(i)) > -1){ stack.push(s.charAt(i)); } else{ if(stack.isEmpty())return false; char pop = stack.pop(); int indexR = right.indexOf(s.charAt(i)); int indexL = left.indexOf(pop); if(indexR != indexL)return false; } } return stack.isEmpty(); }
Karbon Here's the same solution, but neatened up
public static boolean isBalanced(String expression) { Stack<Character> brackets = new Stack<Character>(); for(int i=0; i<expression.length(); i++){ char next = expression.charAt(i); if(next == '{') brackets.add('}'); else if(next == '[') brackets.add(']'); else if(next == '(') brackets.add(')'); else if(brackets.empty() || brackets.pop() != next) { return false; } } return brackets.empty(); }
congrtoss I like your java solution, it's way better than mine. Yours is shorter and neater.
stefan_calatean Seems like poor examples; one would immediately consider simetry, while in ({}([][])) for example, this is not the case.
anitaleung The specs is missing a clarification that the expression does not need to be symmetric to pass, and that the only requirement necessary is that brackets are closed in correct order.
As in "()[]{}" is valid but "([)]{}" isn't.
amanagarwal2189 It does... i guess you missed this: "The subset of brackets enclosed within the confines of a matched pair of brackets is also a matched pair of brackets."
Sort 400 Discussions, By:
Please Login in order to post a comment