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 

Introduction of Array

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

This is the basic or simplest type of data structure. An array can be defined as, a list of a finite number “n” of similar data elements referenced respectively by a set of n consecutive numbers, usually 1, 2, 3, …, n. If A is chosen for the name of some array, then the elements of A are denoted as, a1, a2, a3, a4, …, an OR A(1), A(2), A(3), A(4), …, A(n) [Read More]
kodeknight  array 

find four elements in array whose sum equal to a given number X

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

This can be solved efficiently via using HashTables. We can have a hashtable sums sums will store all possible sums of two different elements. For each sum S it returns pair of indexes i and j such that a[i] + a[j] == S and i != j. But initially it’s empty, we’ll populate it on the way. So, this can be done in O(n^2) time. Pseudocode for (int i = 0; i < n; ++i) { // 'sums' hastable holds all possible sums a\[k\] + a\[l\] // where k and l are both less than i for (int j = i + 1; j < n; ++j) { int current = a\[i\] + a\[j\]; int rest = X - current; // Now we need to find if there're different numbers k and l // such that a\[k\] + a\[l\] == rest and k < i and l < i // but we have 'sums' hashtable prepared for that if (sums\[rest\] ! [Read More]
kodeknight  array  hashtable  sum 

AVL Tree Index

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

hell-o, im carloe distor, from the most beautiful … Anonymous - Mar 3, 2014hell-o, im carloe distor, from the most beautiful province in benguet, baguio city, i would like to ask if you can do me a favor, because im so tired in doing my homework , IN BINARY TREE (ARRAY REPRESENTATION), INFIXTOPOSTFIX USING STACK AND AVL , THANK YOU, Hi , I don’t think I will be able to help much. [Read More]
tree  kodeknight  balanced trees  avl 

BFS (Breadth first search) on Graph

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

Algorithm Starting at some arbitrarily chosen vertex s (s stands for start vertex) , we mark v so that we know we’ve visited it, process v, and  then visit i.e. mark the vertex as visited and process all of v’s neighbors.  Now that we’ve visited and processed all of v’s neighbors,  we need to visit and process all of v’s neighbors neighbors Pseudocode BFS(graph G, vertex s) \[all nodes initially unexplored\] \-mark s as explored let Q = queue data structure, initialized with s while (Q not empty) remove the first node of Q, call it v for each edge (v, w): if w is unexplored mark w as explored add w to Q (at the end) We visit each node only once and each edge at most twice (for edge(v, w), we might encounter it when we’re at node v and at node w). [Read More]
Graph  kodeknight  queue  BFS  graph-search  Undirected Graph