46
You get the job done in 30 minutes and the use of a stack is the way to go, so that's a good start. In my opinion you're writing a little too much (repetitive) code and it could be a lot easier to read if you use a switch-statement instead:
public bool IsValidReview(string s)
{
Stack<char> endings = new Stack<char>();
foreach (var curr in s)...
34
This is almost all style suggestions; the code itself looks great.
Personally, I prefer the brace-on-same-line style for everything in JS, and I prefer proper blocks instead of inlining expressions. But those are just preferences. I've also skipped the bitwise trick, added some strict comparisons instead of !stack.length etc., moved the i++ over to its "...
33
From a pure Python standpoint, a list is already a stack if you narrow its methods down to only pop and append.
l.append(x) will put x at the end of the list, and l.pop() will remove the last element of the list and return it.
So generally speaking, when you need a stack in Python, you'll just make a list and use append and pop.
The same goes for queues, ...
31
May I suggest a simpler solution:
You need only a counter. it is incremented by 1 whenever you encounter an openning parenthesis "(" and is decreased by 1 whenever you encounter a closing parenthesis ")"
The input is invalid if the counter drops below zero or is not zero by the end of scanning.
EDIT
since OP specified they must use a stack, we can follow @...
27
Let's start with some general remarks:
Swift does not require semicolons after statements (but they are allowed). From what I have seen since Swift was introduced last year,
most people do not write semicolons in Swift.
Classes are reference types, and the properties of an instance of a class
can be modified even if the instance is declares as a constant ...
23
Readability
Please put a space after the include and before the <
#include<iostream>
#include<string>
#include<memory>
Don't do this
You can read any other C++ revue on this site.
using namespace std;
See: Why is “using namespace std” considered bad practice?
Don't add useless comments
// Template Node
template <typename T>
...
21
Unicode is hard to get right, especially in Java as it has a more or less broken concept of a “character”. An Unicode code point is a 21-bit number. These code points are encoded to bytes with the UTF-8 or UTF-16 encodings (well, there are a couple more…). But when Java was created, Unicode only had characters in a 16-bit range, and code points were encoded ...
20
Algorithmic complexity for combined operations
Containers are interesting elements in most programming languages: they have an internal state, namely their elements and therefore their size.
This introduces an additional state compared to usual algorithmic asymptotical complexity analysis. For example, a naive implemented std::vector::push_back will yield \...
19
Avoid using namespace std; - it's a large namespace, and growing as new C++ standards appear. Bringing all its names into the global namespace completely obviates the benefits of namespaces, and in the worst case, can silently change the meaning of a program. Get used to using the (very short) namespace prefix std::.
When we call checkParentheses(), we ...
18
A stack should not know about the first element. A stack only know about the last element that was pushed, so the Stack object itself should only have one Node called last. Because of this, the constructor should be changed as well to only take one Node ex: public Stack(Node node).
Edit: As @vnp says, Node is private, so it cannot be created outside this ...
18
Time complexity
The time complexity of push and pop operations should be \$O(1)\$, and so it is in your case too. It doesn't matter how many elements you have, these operations should take constant time. (UPDATE: you've edited your original post, and made pop wipe out the entire stack. That's not normal! Normally, the pop operation on a stack should return ...
18
Other answers correctly point out that using primitive types and not mixing them with Objects (=int instead of Integer), reducing visibility wherever possible (=adding private modifier to position and list) and preventing popping from empty stack are good practices. There are a few more subtleties which can be improved:
Rename INCREMENTSIZE to ...
17
This question provides a really good example of how learning 'tools' is important, but understanding efficiency is better.
The purpose of the task was probably to teach you to use a stack, but there are properties of this challenge which are not well suited to an actual stack solution, and, more importantly, there are other ways of implementing a stack than ...
16
Program defensively and use option 1.
Since the Stack class provides the ability to check whether it contains anything before trying to Pop a value from it, you should do the check and avoid using the exception for flow control.
If you want to avoid doing the if check throughout your application, you could create a TryPop extension.
public static class ...
16
This is a follow up of @Henrik Hansen. Instead, of a switch I would use a Dictionary<T, K>. A Dictionary offers two main advantages: an increase readibility and the suppression of every magic string from your function.
public static readonly Dictionary<char, char> brackets = new Dictionary<char, char>
{
{'(', ')'},
{'[', ']'},
{...
15
I just wanted to write that the code looks completely fine to me, until...
assertEquals(false, isBalanced("[["));
I''m sure you'll find the error :-)
Otherwise two small remarks:
Personally I'd have the function return true for an empty string instead of throwing an exception.
Stack is outdated. I'd use a Deque implementation instead.
EDIT: I'm sorry, ...
15
Please fix your indentation all over the header. It should be consistent with everything else.
You don't need the return 0 at the end of main(). Reaching this point implies successful termination, and the compiler will just insert it for you.
In common stack implementations, pop() is void (merely pops off the top element). This is useful as it'll be much ...
14
First of all, I will start with one of the most common remarks: please, do not use using namespace std;. It is especially bad if you write it in a header file since it leads to namespace pollution and name clashes.
Instead of a method named traverse, it would be better to overload operator<< to print your list. Here is how you could adapt your ...
14
sscanf is not safe
It's not part of your stack but part of your driver code, but scanf() is not a good function to use. There are many reasons for this, but the basic problem in this case is that if the user enters a letter rather than a digit for input in push() for example, the program will loop forever.
Better, in this case, would be to use something ...
14
As usual, revewing a design rather than code.
As coded, pop takes time proportional to the current stack size. It could and should take constant time. Hint: reverse the semantics of node.next (BTW, first becomes redundant).
I don't think that pop/peek returning -1 on empty stack is a good idea. A value of -1 is a valid result of popping from a stack of ...
14
I see a number of things that may help you improve your code.
Use a stack pointer as a parameter
Right now, one can only have one stack at a time. Worse, if one calls stack_init after some items have already been pushed onto the stack, there will be a memory leak. An alternative scheme would be to have stack_init() return a pointer to a Stack and then ...
14
Bugs
The loop header is wrong:
for(i=0;line[i]!=NULL;i++){
Here, you want to scan until you find a byte with ASCII value 0 (also called an ASCII NUL, and written in C as '\0'). However, you wrote NULL, which is supposed to represent a null pointer (a pointer to memory address 0).
In practice, you might get away with confounding the two, since they are ...
14
The methods named emptyCheck() and fullCheck() are ambiguous. They should be named isEmpty() and isFull() respectively.
Good luck!
14
On the whole the code is good, but I would look for three improvements:
Information-hiding: I would change self.stack to self._stack to indicate to readers of the code that this is an implementation detail that should not be accessed directly. Reasons:
Mutating self.stack directly, for example self.stack.insert(2, 42) could break the expectations a client ...
13
@amon wrote a great answer. With Java 8, handling of surrogate pairs is even easier. There is a codePoints() method on the CharSequence interface.
public static String reverseString(String originalString) {
Stack<Integer> stack = new Stack<>();
StringBuilder reversed = new StringBuilder();
originalString.codePoints().forEach(cp -&...
13
Performance
I'll get to a bit of a review, but first, since you're most interested in performance, I've done some benchmarking. In short, all evidence points towards maaartinus' theory being the cause.
Benchmark.java:
public class Benchmark {
private static class Stored {
private final int[] big = new int[250];
public Stored() { }
...
13
Issues
public void Push(T item)
{
_stackList.Insert(0, item);
}
The hurts the stack list.
It would be much easier if you just added new items at the end of the list. The Insert needs to rebuild the entire list:
This method is an O(n) operation, where n is Count.
For an addition this is a real bottleneck.
The same applies to the Pop method which ...
13
The idea is correct, the implementation is not.
Upon exiting the loop you need to test for pilepointer == -1. Otherwise, the strings like "(" are considered valid.
A string beginning with the closing parenthesis accesses pile[-1], invoking UB.
Never use gets.
Don't put everything in main. Separate business logic into a function:
int main() {
......
13
The code is clean. My major concern with how it looks is that your naming doesn't follow PEP8. Names should be snake_case, not camelCase. So isEmpty should be is_empty.
With how it works, I'd work on giving it consistent behavior with other collections.
Right now, you have a sizeStack method for returning the size. This should really be __len__ instead:
...
12
This code is simply incorrect. It is even not a stack (because it lacks
pop operation and it is impossible to implement it in a type-safe way).
Here is an example:
runStack $ do
newStackRef (5:: Int)
newStackRef False
newStackRef 'x'
according to the definition of the newStackRef it just pokes Storable
representation of the value into the memory ...
Only top voted, non community-wiki answers of a minimum length are eligible
