I recently started to learn C++ and came across this problem in a book "Object Oriented Programming in C++" by Robert Lafore. The author has a program in the book which creates a Parser. I found a problem with the original program in the book which breaks at one of the input expressions I am providing. Therefore I tried to make changes and made it recursive. It works fine with the inputs I am providing. I am more concerned about correctness and programming style of the program I have written. I believe I have made many mistakes. Any comments would be very helpful. ``` #include using namespace std; const char SIZE = 40; class Stack { private: char array[SIZE]; char top; public: Stack():top(-1) { } void push(char v) { if (!is_full()) { array[++top] = v; } } char pop() { if (!is_empty()) { return array[top--]; } throw "Stack is empty. Pop failed"; } bool is_full() { return top >= SIZE ? true : false; } bool is_empty() { return top == -1; } char get_top() { return top; } }; bool is_operator(char c) { return (c == '*' || c == '/' || c == '+' || c == '-'); } bool is_dm_operator(char c) { return (c == '*' || c == '/'); } bool is_value(char c) { return (c >= '0' && c (result) (expected_result) ("5 / 5 + 3 - 6 * 2"), // why static_cast here? what is const_cast static_cast("3 * 7 - 1 + 5 / 3"), static_cast("3 * 5 - 4"), static_cast("3 + 5 - 4"), static_cast("2 / 6 * 3 / 2"), static_cast("3 + 6 * 9 / 3 - 7"), static_cast("9 - 5 / 5 * 2 + 6"), static_cast("7 + 3 * 4 / 2 - 5 * 6"), static_cast("4 * 5 + 3 - 4 / 2"),

I'm relatively new to C as a language, but I wouldn't call myself a beginner. That being said, I don't believe my C "coding style," so to speak, is particularly developed. Also, I'm new to error handling in C as well. stack.c ``` #include #include typedef struct node { int val; struct node* next; } node_t; typedef struct stack { struct node* head; } stack_t; stack_t* create_list(void) { stack_t* stack = malloc(sizeof *stack); if (stack != NULL) { stack->head = NULL; } return stack; } void push(stack_t* list, int val) { node_t* newnode = malloc(sizeof *newnode); if (newnode != NULL) { newnode->val = val; newnode->next = list->head; } list->head = newnode; } int pop(stack_t* list) { int val = list->head->val; node_t* next = list->head->next; free(list->head); list->head = next; return val; } void destroy_list(stack_t* list) { do { node_t* head = list->head; node_t* next = head->next; free(head); list->head = next; } while (list->head); free(list); } void foreach(stack_t* list, int (*func)(const int)) { node_t* curr = list->head; do { curr->val = func(curr->val); curr = curr->next; } while(curr); } int print_val(const int val) { printf("value: %d\n", val); return val; } int main(int argc, char* argv[]) { printf("creating list\n"); stack_t* list = create_list(); printf("pushing value 2\n"); push(list, 2); printf("top value: %d\n", list->head->val); printf("pushing value 5\n"); push(list, 5); printf("top value: %d\n", list->head->val); printf("iterating top-down\n"); foreach(list, print_val); printf("popping top value\n"); int popped = pop(list); printf("popped: %d\n", popped); printf("top value: %d\n", list->head->val); destroy_list(list); return 0; } ``` queue.c ``` #include #include type

I have started learning data structures and have implemented my own stack implementation: ``` package com.algo.stack; import java.io.Serializable; import java.lang.reflect.Array; public class MyStack { private T[] myArray = null; // the array is the stack content private int arraySize = 0; // holds the size counter /* * Initialize stack for its size and generic type */ public MyStack(Class c,int stackSize){ @SuppressWarnings("unchecked") final T[] a = (T[]) Array.newInstance(c , stackSize); this.myArray = a; } /** * The push method, which adds * numbers in internal array * @param obj * @throws Exception */ public void push(T obj) throws Exception{ if(this.arraySize stack1 = null; MyStack stack2 = null; try{ stack1 = new MyStack(Integer.class, 3); stack1.push(12); stack1.push(24); stack1.push(36); while(stack1.size() > 0){ System.out.println(stack1.pop()); } System.out.println("\n"); stack2 = new MyStack(String.class, 4); stack2.push("Leo"); stack2.push("Tom"); stack2.push("Nancy"); stack2.push("Julean"); while(stack2.size() > 0){ System.out.println(stack2.pop()); } }catch(Exception e){ e.printStackTrace(); } } } ``` It's working fine and the output is: `36 24 12 Julean Nancy Tom Leo ` Please review my rough implementation and let me know of any flaws and how I can improve.

I have implemented in C# a stack data structure, without using any existing C#/.NET containers (data structures). I have used TDD technique to implement this requirements, so you can find tests, too. All my tests are passing, so I guess stack is behaving correctly. I would be very pleased to have a code review for this implementation. Please do not recommend a generic implementation :-) ``` using System; using Microsoft.VisualStudio.TestTools.UnitTesting; using StackDataStructure; namespace StackTesting { [TestClass] public class Tests { [TestMethod] public void TestEmptyStackSize() { var stack = new Stack(); Assert.IsTrue(stack.IsEmpty()); } [TestMethod] [ExpectedException(typeof(InvalidOperationException))] public void EmptyStackPopException() { var stack = new Stack(); stack.Pop(); } [TestMethod] public void PushingAndPoppintItemsToStack() { var stack = new Stack(); stack.Push(1); Assert.AreEqual(1, stack.Size); stack.Push(2); Assert.AreEqual(2, stack.Size); Assert.AreEqual(2, stack.Pop()); Assert.AreEqual(1, stack.Size); Assert.AreEqual(1, stack.Pop()); Assert.IsTrue(stack.IsEmpty()); Assert.IsTrue(stack.Size == 0); stack.Push(10); Assert.IsTrue(stack.Size == 1); Assert.IsTrue(10 == stack.Pop()); Assert.IsTrue(stack.IsEmpty()); } } } ``` ``` using System; namespace StackDataStructure { internal class Node { internal int value; internal Node underTop; } public class Stack { private int size; private Node top; public int Size { get { return size; } } public bool IsEmpty() { return top == null; } public int Pop()

Recently, I've solved the "Valid Parenthesis" problem on LeetCode: Given a string containing just the characters `'('`, `')'`, `'{'`, `'}'`, `'['` and `']'`, determine if the input string is valid. The brackets must close in the correct order, `"()"` and `"()[]{}"` are all valid but `"(]"` and `"([)]"` are not. I've decided to iterate over every character in the string and push it on stack if it is an opening bracket. If not, pop from the stack and check if the closing bracket matches the opening bracket. Here is my implementation: ``` OPENING_BRACKETS = {"{", "[", "("} BRACKETS_MAP = {"]": "[", "}": "{", ")": "("} class Solution(object): def isValid(self, s): if not s: # empty string is a valid string return True if s[0] not in OPENING_BRACKETS: return False # early exit if string does not start with an opening bracket stack = [] for index, bracket in enumerate(s): if bracket in OPENING_BRACKETS: stack.append(bracket) else: try: last_opening_bracket = stack.pop() if last_opening_bracket != BRACKETS_MAP[bracket]: # last closing bracket does not match last opening bracket return False except IndexError: return False # pop from an empty stack means the brackets are not balanced return not stack # if something left on stack, brackets are unbalanced ``` Is it the most optimal approach to solving the problem Time- and Space- Complexity wise? What would you suggest to improve in the presented solution?

I have been solving this problem of Hackerrank recently .. https://www.hackerrank.com/challenges/maximum-element A little bit about the problem You have an empty sequence, and you will be given N queries. Each query is one of these three types: 1 x -Push the element x into the stack. 2 -Delete the element present at the top of the stack. 3 -Print the maximum element in the stack. And my code is here - which passes the first 12 test cases. ``` import java.util.*; public class Stackers { public static Stack stack; public static String output = ""; public static void main(String[] args) { stack = new Stack<>(); Scanner sc = new Scanner(System.in); int n = sc.nextInt(); for(int i = 0 ; i < n + 1; i++){ String op = sc.nextLine(); performOperation(op); } sc.close(); if(!output.isEmpty()){ System.out.println(output); } } public static void performOperation(String op) { if (op.startsWith("1")){ String remains = op.split(" ")[1]; int rem = Integer.valueOf(remains); stack.push(rem); }else if(op.equalsIgnoreCase("2")){ stack.pop(); }else if(op.equals("3")){ int max = (int) Collections.max(stack); output += (max + "\n"); } } } ``` But fails with "timeout" from the 13th test case. Most of the times, logic will be wrong, so I ran the 13th test case locally in my computer . I got the output in 1.3- 1.6 minutes tho:) How can I improve my code. Please guide me or if it is the wrong stack exchange community, please advise me.

I wrote a deque implementation in C for storing `char *`. It uses a doubly linked list, but I'm calling it a deque since it can only push/pop from the head and tail of the list. I don't have much experience writing C (I'm more of a Python guy) so please let me know what can be improved! I am already aware of the following: - there are no comments (I've tried to use self-explanatory names) - the testing isn't particularly rigorous linkedlist.h ``` #ifndef _LINKEDLIST_H #define _LINKEDLIST_H #include struct ll_node { struct ll_node *prev; struct ll_node *next; char *data; }; struct linkedlist { struct ll_node *head; struct ll_node *tail; size_t length; }; void ll_node_init(struct ll_node *node, char *data); void ll_init(struct linkedlist *ll); void ll_destroy(struct linkedlist *ll); void ll_push_head(struct linkedlist *ll, char *data); void ll_push_tail(struct linkedlist *ll, char *data); char *ll_pop_head(struct linkedlist *ll); char *ll_pop_tail(struct linkedlist *ll); #endif ``` linkedlist.c ``` #include #include "linkedlist.h" void ll_node_init(struct ll_node *node, char *data) { node->prev = NULL; node->next = NULL; node->data = data; } void ll_init(struct linkedlist *ll) { ll->head = NULL; ll->tail = NULL; ll->length = 0; } void ll_destroy(struct linkedlist *ll) { struct ll_node *node = ll->head; struct ll_node *next; while(node != NULL) { next = node->next; free(node); node = next; } } void ll_push_head(struct linkedlist *ll, char *data) { struct ll_node *node = malloc(sizeof(struct ll_node)); ll_node_init(node, data); if(ll->head != NULL) { ll->head->prev = node; } if(ll->tail == NULL) { ll->tail = node; } node->next = ll->head; ll->head = node; ll->length++; } void ll_push_tail(struct linkedlist *ll, char *data) { struct ll_node *node = malloc(sizeof(struct ll_node)); ll_no

I have a configuration engine that allows the user to specify a dictionary with text templates (read from a JSON file) where each placeholder like `{x}` can be substituted for a value found under a key with the same name e.g. `x`. ``` var constants = new Dictionary { { "x", "foo {y} baz" }, { "y", "bar {x} qux" }, }; ``` These are just two sample strings to show how it can look like. The real configuration contains connection strings, email lists, user names, sql etc. They are resolved at runtime with this method ``` public static string FormatAll(this string text, Dictionary values) { while (text.ToString() != (text = text.Format(values))) ; return text; } ``` where `Format` is a more advanced version of my question about string interpolation. As you can probably see in the example, there is a danger that someone creates a circular template path and the formatting runs forever. In order to prevent this from happening, I thought I validate the template dictionary before I let the formating method work with it. This is what I've come up with. The `ValidateIsNotCircular` extension runs over the reference dictionary and checks each path for recursiveness and as soon as it finds one that is circular, it throws an exception that contains the path. I wanted it to work without recursion so I used a `Stack`. Sidenote: This time I'm confined to C# < 6 so no fancy code here :-( ``` public static void ValidateIsNotCircular(this Dictionary> values) { var visitedKeys = new HashSet(); var stack = new Stack>>(); var currentRef = new Func(() => stack.Peek().Item2.Current); var currentRefs = new Func>(() => stack.Peek().Item2); foreach (var item in values) { if (!visitedKeys.Add(item.Key)) continue; stack.Push(Tuple.Create(item.Key, item.Value.GetEnumerator())); do { while (currentRefs().MoveNext()) { if (stack.Any(x => currentRef() == x.Item1))

I have written my own object pool class called `ObjectPool` which uses `SpinLock` and `Stack`: ``` public class ObjectPool where T : class { private int _size; private Func _factory; private SpinLock _spinLock; // storage for the pool objects. // the first item is expected to be most often case. private T _firstItem; private Stack _cache; //Use Queue for first-in-first-out (FIFO) public ObjectPool(Func factory) : this(factory, Environment.ProcessorCount * 2) { } public ObjectPool(Func factory, int size) { _factory = factory; _size = size; _cache = new Stack(); _spinLock = new SpinLock(false); } /// /// Produces an instance. /// public T Rent() { bool lockTaken = false; _spinLock.Enter(ref lockTaken); try { T instance = _firstItem; if (instance == null || instance != Interlocked.CompareExchange(ref _firstItem, null, instance)) { instance = RentFromCache(); } return instance; } finally { if (lockTaken) { _spinLock.Exit(false); } } } private T RentFromCache() { var cache = _cache; if (cache.Count > 0) { T instance = _cache.Pop(); if (instance != null) { return instance; } } return CreateInstance(); } private T CreateInstance() { var instance = _factory(); return instance; } /// /// Returns objects to the pool. /// public void Return(T obj) { bool lockTaken = false; _spinLock.Enter(ref lockTaken); try { if (_firstItem == null) { // worst case scenario: two objects may be stored into same slot. _firstItem = obj;

Introduction/Disclaimer This is a project for educational purposes. I'm not intending to replace the "award-winning" Collections Framework in `java.util`. I'm just looking for constructive criticism. For obvious reasons, I'm tagging it as reinventing-the-wheel. I'd like to see someone break my code. Preferably in a multi-threaded environment. (My code is not thread-safe) Overview The `Container` class defines the minimal skeletal structure for all Data Structures that I implement. Depending on the requirement, I'm providing two implementations: Fixed capacity implementations and implementations using Linked Lists. For this question, I'm limiting the discussion to `FixedStack` and all the related classes. `Container.java` ``` package astrobleme.core.datastructures; import java.util.Arrays; import java.util.StringJoiner; /** * This is the root of the Container hierarchy. This contains methods * that provide a common skeletal structure to all implementations. The * modifying methods will have different names, depending on the type of * data structure it is. * * @author Subhomoy Haldar * @version 2017.02.15 */ public abstract class Container { /** * Returns the number of elements currently in the Container. It is * guaranteed to be a non-negative number. * * NOTE: If the number of elements exceeds * {@link Long#MAX_VALUE Long#MAX_VALUE}, then it will return * {@code Long#MAX_VALUE}. * * @return The number of elements in this Container. */ abstract long size(); /** * Returns {@code true} if the number of elements in this Container is * within the allowed maximum size for arrays, and hopefully, it might * be able to create an array out of it. * * However, it depends on the amount of memory allocated by the VM and * even smaller sizes may cause a {@link OutOfMemoryError}. It is advised * to re-start the VM with different arguments to allow for allocation * of