Problem Given a string s representing a valid expression, implement a basic calculator to evaluate it, and return the result of the evaluation. Note: You are not allowed to use any built-in function which evaluates strings as mathematical expressions, such as eval().%% %% Examples Example 1: Input: s = "1 + 1" Output: 2 ...
Problem Given an array, print the Next Smaller Element (NSR) for every element. The Next greater element for an element x is the first greater element on the right side of x in the array. The elements for which no greater element exist, print -1. Examples Example 1: Input: {1, 3, 2, 4} Output: {-1, 1, 1, 1} Element Next greater element on the right 1 -1 3 1 2 1 4 1 ...
Problem Given an array, print the Next Greater Element (NGE) for every element. The Next greater element for an element x is the first greater element on the right side of x in the array. The elements for which no greater element exist, print -1. Examples Example 1: Input: {1, 3, 2, 4} Output: {3, 4, 4, -1} Element Next greater element on the right 1 3 3 4 2 4 4 -1 ...
Problem Given a string s of '(' , ')' and lowercase English characters. Your task is to remove the minimum number of parentheses ( '(' or ')', in any positions ) so that the resulting parentheses string is valid and return any valid string. Formally, a parentheses string is valid if and only if: It is the empty string, contains only lowercase characters, or It can be written as AB (A concatenated with B), where A and B are valid strings, or It can be written as (A), where A is a valid string. Examples Example 1: ...
Problem Suppose we have a file system that stores both files and directories. An example of one system is represented in the following picture: ...
Problem Sort a Stack using standard operations push, pop, isEmpty and peek. Other ways of asking the question Write a program to sort a stack in ascending order You should not make any assumptions about how the stack is implemented The following are the only functions that should be used to write this program: push | pop | peek | isEmpty Note - peek is equivalent to top() function in java, where you don’t pop out the element but peek and see. ...
Problem Implement 3 stacks in 1 array Solution Method 1 - Create 3 Stacks with Fixed Max Size Divide the array in three equal parts and allow the individual stack to grow in that limited space (note: [ means inclusive, while ( means exclusive of the end point). for stack 1, we will use [0, n/3) for stack 2, we will use [n/3, 2n/3) for stack 3, we will use [2n/3, n) Code Java int stackSize = 300; int[] buffer = new int[stackSize * 3]; int[] stackPointer = {0,0,0}; // stack pointers to track top element void push(int stackNum, int value) { /* Find the index of the top element in the array + 1, and increment the stack pointer */ int index = stackNum * stackSize + stackPointer[stackNum] + 1; stackPointer[stackNum]++; buffer[index] = value; } int pop(int stackNum) { int index = stackNum * stackSize + stackPointer[stackNum]; stackPointer[stackNum]--; int value = buffer[index]; buffer[index] = 0; return value; } int peek(int stackNum) { int index = stackNum * stackSize + stackPointer[stackNum]; return buffer[index]; } boolean isEmpty(int stackNum) { return stackPointer[stackNum] == stackNum * stackSize; } ...
Problem Stack with find-min/find-max in O(1) time Solution Method 1 - using extra stacks for min and max The basic idea of the solution can be found here. Here instead of 2 stacks we will be using 3 stacks -1 stack with normal elements, 1 with only max elements and 1 with min element. Now the operations will be following : push: - If the element being pushed is less than the top element of ‘min_stack’ then push it on ‘min_stack’ as well. - Else, push the top element of ‘min_stack’ again on ‘min_stack’. Similarly for max_stacks ...
There is no diffeence in circular list stack and non circular list stack. The insertion, deletion operation takes place in the same place. So it won’t create any modification in the circular list. Here is the implementation of circular stack in CPP Program in cpp #include <iostream.h> #include <stdlib.h> using namespace std; struct node { int info; struct node \*next; }; int c=0; struct node \*top;int empty() { return((top == NULL)? 1:0); } void print() { int i =0; struct node \*temp; cout<<"\\n\\t\\t"; if(c==0) cout<<"\\n\\t\\tNo elements\\n"; else { temp = top->next; while(i!=c) { int info = temp->info; cout<<info<<" "; temp=temp->next; i++; } cout<<"END PRINT"; } } void push(int n) { struct node \*p; p=new node; if(p!=NULL) { c++; p->info=n; if(empty()) top=p; else p->next=top->next; top->next=p; } else cout<<"Not inserted,No memory available"; } int pop() { c--; struct node \*temp; int x; temp=top->next; x=temp->info; if(temp==top) top=NULL; else top->next=temp->next; free(temp); return(x); } int main() { int s,n; cout<<"\\n\\t\\tCIRCULAR STACK IMPLEMENTATION\\n"; while(1) { cout<<"\\n\\t\\t1>Push\\n"; cout<<"\\t\\t2>Pop\\n"; cout<<"\\t\\t3>Print\\n"; cout<<"\\t\\t4>Exit\\n"; cout<<"\\t\\tEnter your choice:"; cin>>s; switch(s) { case 1: cout<<"\\n\\t\\tEnter the number:"; cin>>n; push(n); break; case 2: if(empty()) { cout<<"\\n\\t\\tStack underflow\\n"; } else { n=pop(); cout<<"\\n\\t\\tThe pop value is:"<<n; } break; case 3: print(); break; case 4: exit(1); break; } } } ```Let us know your feedback. ...
Problem: You need to implement a stack data structure that can also report the minimum element in constant-time. Solution Method 1 - Using extra stack This is not all that difficult if you think about it. Regular stacks support push() and pop() functions. We need to add a new read-only property, Minimum. You can’t just add a new variable to track the minimum because when the stack is popped you wouldn’t be know how to update the minimum variable without scanning through all items in the stack which would require you to pop and re-push each item, which is downright ugly. So we need to keep some auxiliary list of the stack items so we can update the minimum variable after we pop items. ...