Evaluating postfix expression using stack

 Posted on September 10, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

We have seen the conversion of infix to postfix expression here. Now lets see how to evaluate it. Algorithm Scan input expression from left to right If scanned input is an operand, push it into the stack If scanned input is an operator, pop out two values from stack. Then, perform operation between popped values and then push back the result into the stack. Repeat above two steps till all the characters are scanned. [Read More]
kodeknight  Data Structure  application  stack 

Converting an Infix Expression to Postfix expression using a stack

 Posted on September 10, 2013  (Last modified on August 7, 2020)  |  4 minutes  |  Kinshuk Chandra

Pre-requisite - What is infix, postfix and prefix? Infix, Postfix and Prefix notations are three different but equivalent ways of writing expressions. Postfix is also known as Reverse Polish Notation or RPN , and prefix expression is also known as Polish notation. Infix - Operators are written in-between their operands. eg. A+B Postfix - Operators are written after their operands. eg. AB+ Prefix - Operators are written before their operands. eg. [Read More]
conversion  kodeknight  stack 

Checking whether the paranthesis are balanced in the expression

 Posted on September 10, 2013  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

Problem  Checking whether the paranthesis are balanced in the expression Solution Method 1 - Using stacks Stacks can be used to compare the paranthesis. Whenever we find the opening paranthesis we push it in the stack, and whenever we find closing paranthesis, we pop it out from stack. When the expression finishes and stack is not empty, then it means that paranthesis are not balanced otherwise they are. [Read More]
kodeknight  application  parentheses  stack 

Resizing Array implementation of stack

 Posted on September 10, 2013  (Last modified on August 7, 2020)  |  2 minutes  |  Kinshuk Chandra

We have already seen the array implementation of stack, which had one limitation of what happens if data size is bigger than array size, i.e. over flow occurs. To solve this we have to grow our array. But how? Growing the Array Approach 1 - Repeated Doubling i.e. Doubling the array every time it is full We can grow the array by doubling it size, and copying the elements in older array to newer one. [Read More]
kodeknight  time complexity  Amortize  stack 

Circular Stack

 Posted on July 29, 2013  (Last modified on August 12, 2020)  |  1 minutes  |  Kinshuk Chandra

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)? [Read More]
kodeknight  incomplete  circular stack  stack 

Maximum Area Rectangle in Histogram

 Posted on January 1, 2012  (Last modified on August 7, 2020)  |  7 minutes  |  Kinshuk Chandra

Question: Find the maximum rectangle (in terms of area) under a histogram in linear time. I mean the area of largest rectangle that fits entirely in the Histogram. (Please refer figures before code section for clarity. If I include bar i completely, those figure will tell how much maximum area rectangle I can get.) Consider the histogram below: Max area of the rectangle: Max area = 4 * 3 = 12 [Read More]
kodeknight  rectangle  hard  stack  histogram 

Some Stack Question

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  5 minutes  |  Kinshuk Chandra

1)How do you implement 2 stacks using only one array.Your stack routines should not indicate an overflow unless every slot in the array is used? **Solution:**given an Array,start the first stack S1 from left end and other stack S2 from the right end.while S1 gets grows towards right ,S2 grows towards left. (By the way we can implement n stacks in 1 array, eg. of 3 stacks in 1 array is given in question 3 below) [Read More]
kodeknight  String  catalan  Data Structures  DS  stack 

Implement 3 stacks in 1 array

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  3 minutes  |  Kinshuk Chandra

Problem - Implement 3 stacks in 1 array Solutions 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) Here is the code : [Read More]
kodeknight  array  CrackingTheCodingInterview  stack 

Implement a queue in which push_rear(), pop_front() and get_min() are all constant time operations.

 Posted on December 29, 2011  (Last modified on August 7, 2020)  |  1 minutes  |  Kinshuk Chandra

You can implement a stack with O(1) pop(), push() and get_min(): just store the current minimum together with each element. So, for example, the stack [4,2,5,1] (1 on top) becomes [(4,4), (2,2), (5,2), (1,1)]. See here for the full implementation. Then you can use two stacks to implement the queue. Push to one stack, pop from another one; if the second stack is empty during the pop, move all elements from the first stack to the second one. [Read More]
kodeknight  queue  stack