Welcome to Software Development on Codidact!
Will you help us build our independent community of developers helping developers? We're small and trying to grow. We welcome questions about all aspects of software development, from design to code to QA and more. Got questions? Got answers? Got code you'd like someone to review? Please join us.
Post History
Use a stack while just scanning your string once from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at...
Answer
#12: Post edited
by
elgonzo
·
2021-06-16T00:57:15Z (almost 3 years ago)
- Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s)/2` elements.
- The algorithm is rather straightforward:
- Check first whether the string is of odd or even length. If the string is of odd length, it must be an unbalanced string (Your code already does this part, i just mentioned it here again simply for having a full description of the stack-based alogrithm.)
- For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of this opening bracket onto the stack (that can be the opening bracket characters themselves, the associated closing brackets, or some other identifying values such as from an enum). If before doing a push the count of elements in the stack is already `len(s)/2` you know the string must be unbalanced and the routine can abort now.
- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- When the stack is empty after completing the scan of the text string, you know the string was balanced (or the string was empty).
- I leave it to you as an exercise to translate this algorithm into concrete Python code.
P.S.: As a further exercise, you might try implementing the same stack-based algorithm while avoiding using an explicit stack data structure. This can be achieved by implementing the algorithm in a recursive manner, with the call stack taking the role of the stack for keeping track of the (nested) bracket pairs.
- Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s)/2` elements.
- The algorithm is rather straightforward:
- Check first whether the string is of odd or even length. If the string is of odd length, it must be an unbalanced string (Your code already does this part, i just mentioned it here again simply for having a full description of the stack-based alogrithm.)
- For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of this opening bracket onto the stack (that can be the opening bracket characters themselves, the associated closing brackets, or some other identifying values such as from an enum). If before doing a push the count of elements in the stack is already `len(s)/2` you know the string must be unbalanced and the routine can abort now.
- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- When the stack is empty after completing the scan of the text string, you know the string was balanced (or the string was empty).
- I leave it to you as an exercise to translate this algorithm into concrete Python code.
- P.S.: As a further exercise, you might try implementing the same stack-based algorithm while avoiding using an explicit stack data structure. This can be achieved by implementing the algorithm in a recursive manner, with the call stack conceptually taking the role of the stack that's keeping track of the (nested) bracket pairs.
#11: Post edited
by
elgonzo
·
2021-06-16T00:55:54Z (almost 3 years ago)
- Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s)/2` elements.
- The algorithm is rather straightforward:
- Check first whether the string is of odd or even length. If the string is of odd length, it must be an unbalanced string (Your code already does this part, i just mentioned it here again simply for having a full description of the stack-based alogrithm.)
- For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of this opening bracket onto the stack (that can be the opening bracket characters themselves, the associated closing brackets, or some other identifying values such as from an enum). If before doing a push the count of elements in the stack is already `len(s)/2` you know the string must be unbalanced and the routine can abort now.
- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- When the stack is empty after completing the scan of the text string, you know the string was balanced (or the string was empty).
I leave it to you as an exercise to translate this algorithm into concrete Python code.
- Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s)/2` elements.
- The algorithm is rather straightforward:
- Check first whether the string is of odd or even length. If the string is of odd length, it must be an unbalanced string (Your code already does this part, i just mentioned it here again simply for having a full description of the stack-based alogrithm.)
- For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of this opening bracket onto the stack (that can be the opening bracket characters themselves, the associated closing brackets, or some other identifying values such as from an enum). If before doing a push the count of elements in the stack is already `len(s)/2` you know the string must be unbalanced and the routine can abort now.
- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- When the stack is empty after completing the scan of the text string, you know the string was balanced (or the string was empty).
- I leave it to you as an exercise to translate this algorithm into concrete Python code.
- P.S.: As a further exercise, you might try implementing the same stack-based algorithm while avoiding using an explicit stack data structure. This can be achieved by implementing the algorithm in a recursive manner, with the call stack taking the role of the stack for keeping track of the (nested) bracket pairs.
#10: Post undeleted
by
elgonzo
·
2021-06-16T00:29:45Z (almost 3 years ago)
#9: Post deleted
by
elgonzo
·
2021-06-16T00:28:58Z (almost 3 years ago)
#8: Post edited
by
elgonzo
·
2021-06-16T00:25:28Z (almost 3 years ago)
- Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s)/2` elements.
- The algorithm is rather straightforward:
- For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of this opening bracket onto the stack (that can be the opening bracket characters themselves, the associated closing brackets, or some other identifying values such as from an enum). If before doing a push the count of elements in the stack is already `len(s)/2` you know the string must be unbalanced and the routine can abort now.
- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- When the stack is empty after completing the scan of the text string, you know the string was balanced (or the string was empty).
- I leave it to you as an exercise to translate this algorithm into concrete Python code.
- Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s)/2` elements.
- The algorithm is rather straightforward:
- Check first whether the string is of odd or even length. If the string is of odd length, it must be an unbalanced string (Your code already does this part, i just mentioned it here again simply for having a full description of the stack-based alogrithm.)
- For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of this opening bracket onto the stack (that can be the opening bracket characters themselves, the associated closing brackets, or some other identifying values such as from an enum). If before doing a push the count of elements in the stack is already `len(s)/2` you know the string must be unbalanced and the routine can abort now.
- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- When the stack is empty after completing the scan of the text string, you know the string was balanced (or the string was empty).
- I leave it to you as an exercise to translate this algorithm into concrete Python code.
#7: Post edited
by
elgonzo
·
2021-06-16T00:20:11Z (almost 3 years ago)
- Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s)/2` elements.
- The algorithm is rather straightforward:
For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of this opening bracket onto the stack (that can be the opening bracket characters themselves, the equivalent closing braces, or some other identifying values such as an enum). If before doing a push the count of elements in the stack is already `len(s)/2` you know the string must be unbalanced and the routine can abort now.- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- When the stack is empty after completing the scan of the text string, you know the string was balanced (or the string was empty).
- I leave it to you as an exercise to translate this algorithm into concrete Python code.
- Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s)/2` elements.
- The algorithm is rather straightforward:
- For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of this opening bracket onto the stack (that can be the opening bracket characters themselves, the associated closing brackets, or some other identifying values such as from an enum). If before doing a push the count of elements in the stack is already `len(s)/2` you know the string must be unbalanced and the routine can abort now.
- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- When the stack is empty after completing the scan of the text string, you know the string was balanced (or the string was empty).
- I leave it to you as an exercise to translate this algorithm into concrete Python code.
#6: Post edited
by
elgonzo
·
2021-06-16T00:19:27Z (almost 3 years ago)
Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s)/2` characters.- The algorithm is rather straightforward:
- For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of this opening bracket onto the stack (that can be the opening bracket characters themselves, the equivalent closing braces, or some other identifying values such as an enum). If before doing a push the count of elements in the stack is already `len(s)/2` you know the string must be unbalanced and the routine can abort now.
- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- When the stack is empty after completing the scan of the text string, you know the string was balanced (or the string was empty).
- I leave it to you as an exercise to translate this algorithm into concrete Python code.
- Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s)/2` elements.
- The algorithm is rather straightforward:
- For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of this opening bracket onto the stack (that can be the opening bracket characters themselves, the equivalent closing braces, or some other identifying values such as an enum). If before doing a push the count of elements in the stack is already `len(s)/2` you know the string must be unbalanced and the routine can abort now.
- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- When the stack is empty after completing the scan of the text string, you know the string was balanced (or the string was empty).
- I leave it to you as an exercise to translate this algorithm into concrete Python code.
#5: Post edited
by
elgonzo
·
2021-06-16T00:17:49Z (almost 3 years ago)
Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s) / 2` characters.- The algorithm is rather straightforward:
For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of this opening bracket onto the stack (that can be the opening bracket characters themselves, the equivalent closing braces, or some other identifying values such as an enum). If before doing a push the count of elements in the stack is already `len(s) / 2` you know the string must be unbalanced and the routine can abort now.- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- When the stack is empty after completing the scan of the text string, you know the string was balanced (or the string was empty).
- I leave it to you as an exercise to translate this algorithm into concrete Python code.
- Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s)/2` characters.
- The algorithm is rather straightforward:
- For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of this opening bracket onto the stack (that can be the opening bracket characters themselves, the equivalent closing braces, or some other identifying values such as an enum). If before doing a push the count of elements in the stack is already `len(s)/2` you know the string must be unbalanced and the routine can abort now.
- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- When the stack is empty after completing the scan of the text string, you know the string was balanced (or the string was empty).
- I leave it to you as an exercise to translate this algorithm into concrete Python code.
#4: Post edited
by
elgonzo
·
2021-06-16T00:17:17Z (almost 3 years ago)
- Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s) / 2` characters.
- The algorithm is rather straightforward:
For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of this opening bracket onto the stack (that can be the opening bracket characters themselves, the equivalent closing braces, or some other identifying values such as an enum). If before doing a push the stack size is already `len(s) / 2` you know the string must be unbalanced and the routine can abort now.- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- When the stack is empty after completing the scan of the text string, you know the string was balanced (or the string was empty).
- I leave it to you as an exercise to translate this algorithm into concrete Python code.
- Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s) / 2` characters.
- The algorithm is rather straightforward:
- For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of this opening bracket onto the stack (that can be the opening bracket characters themselves, the equivalent closing braces, or some other identifying values such as an enum). If before doing a push the count of elements in the stack is already `len(s) / 2` you know the string must be unbalanced and the routine can abort now.
- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- When the stack is empty after completing the scan of the text string, you know the string was balanced (or the string was empty).
- I leave it to you as an exercise to translate this algorithm into concrete Python code.
#3: Post edited
by
elgonzo
·
2021-06-16T00:13:13Z (almost 3 years ago)
- Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s) / 2` characters.
- The algorithm is rather straightforward:
- For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of this opening bracket onto the stack (that can be the opening bracket characters themselves, the equivalent closing braces, or some other identifying values such as an enum). If before doing a push the stack size is already `len(s) / 2` you know the string must be unbalanced and the routine can abort now.
- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- I leave it to you as an exercise to translate this algorithm into concrete Python code.
- Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s) / 2` characters.
- The algorithm is rather straightforward:
- For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of this opening bracket onto the stack (that can be the opening bracket characters themselves, the equivalent closing braces, or some other identifying values such as an enum). If before doing a push the stack size is already `len(s) / 2` you know the string must be unbalanced and the routine can abort now.
- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- When the stack is empty after completing the scan of the text string, you know the string was balanced (or the string was empty).
- I leave it to you as an exercise to translate this algorithm into concrete Python code.
#2: Post edited
by
elgonzo
·
2021-06-16T00:10:55Z (almost 3 years ago)
- Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s) / 2` characters.
- The algorithm is rather straightforward:
For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of the brackets onto the stack (that can be the opening bracket characters themselves, the equivalent closing braces, or some other identifying values such as an enum). If before doing a push the stack size is already `len(s) / 2` you know the string must be unbalanced and the routine can abort now.- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- I leave it to you as an exercise to translate this algorithm into concrete Python code.
- Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s) / 2` characters.
- The algorithm is rather straightforward:
- For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of this opening bracket onto the stack (that can be the opening bracket characters themselves, the equivalent closing braces, or some other identifying values such as an enum). If before doing a push the stack size is already `len(s) / 2` you know the string must be unbalanced and the routine can abort now.
- For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now.
- When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced.
- I leave it to you as an exercise to translate this algorithm into concrete Python code.
#1: Initial revision
by
elgonzo
·
2021-06-16T00:10:25Z (almost 3 years ago)
Use a stack while just scanning your string **once** from left to right. No need for multiple (performance-wise) expensive string replacements. If implemented right, the stack will only ever contain at maximum `len(s) / 2` characters. The algorithm is rather straightforward: For any opening paranthesis/bracket/brace in the string, push some value/token that represents the type of the brackets onto the stack (that can be the opening bracket characters themselves, the equivalent closing braces, or some other identifying values such as an enum). If before doing a push the stack size is already `len(s) / 2` you know the string must be unbalanced and the routine can abort now. For any closing bracket in the string, pop a value/token from the stack and check whether that value/token represents the same bracket type as the closing bracket. If the stack is empty before attempting to pop, or the popped value/token mismatches the type of the closing bracket in the string, you know the string must be unbalanced and the routine can abort now. When you finished scanning the string from left to right and the stack is not empty, you again know that the string must be unbalanced. I leave it to you as an exercise to translate this algorithm into concrete Python code.