Hot answers tagged

45

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)...


32

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 "...


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!


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() { ......


12

First main problem is the code does not compile: When you implement template classes. The compiler instantiates the templates on use. This means the compilation unit that is instantiating the class must have already seen the source for the template (if it has not then it marks it as unresolved) and then tries to resolve them at link time. In your case this ...


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 ...


12

Things you did well: Overall the code looks very nice and well organized. You used comments well. Things you could improve: Syntax: typedef your structs. struct Stack { int value; int is_empty; struct Stack *next; }; The typedef means you no longer have to write struct all over the place. That not only saves some space, it also can make the code ...


12

This code is basically perfect (save for that little bug found by RoToRa): Map initialization in a static initializer block constructor is made inaccessible the code does what the documentation says clever short circuiting implementation using explicit stack However, there are a few points which we can talk about: The JavaDoc doesn't mention that the ...


Only top voted, non community-wiki answers of a minimum length are eligible