TREAP ( Binary Search Tree + Heap )

Getting back to Data Structures after quite a long time :P ( Hope this makes a good read )

Useful links to understand TREAP :
http://faculty.cs.niu.edu/~freedman/340/340notes/340treap.htm
http://www.cs.cornell.edu/Courses/cs312/2003sp/lectures/lec26.html
http://electures.informatik.uni-freiburg.de/portal/download/7/8207/04_Treaps_4up.pdf
http://ieng6.ucsd.edu/~cs100s/Exams/TreapExamples.pdf

Input :
i n      // to insert n
d n    // to delete n
s n    // to search for n
p      // to print the current situation of treap

Binary Search Tree ( Finding the height and diameter of a BST )

Passing over to Binary Search Tree , this one is an easy problem .
One should have a basic knowledge about BST and also know how to insert data into it . i am really not sure of whether it is a standard for BST or not but here i am going to use LDR to insert data in the tree , i.e ( if the value to be inserted is smaller than root it goes to left and if it is greater then it goes to right ) . Ok without taking much time i discuss the problem with u .

Problem :

The diameter of a tree is the number of nodes on the longest path between two leaves in the tree. The

diameter of a tree T is the largest of the following quantities:
• The diameter of T’s left subtree
• The diameter of T’s right subtree
• The longest path between leaves that goes through the root of T(this can be computed from the
heights of the subtrees of T)
The Fig  below shows a tree with diameter nine, the leaves that form the ends of a
longest path are shaded (note that there is more than one path in the tree of length nine, but no path
longer than nine nodes).

                                       

Input Format:
Sequence of Numbers(without repetition), terminated by newline character.

Output Format:
Height of tree T. Diameter of tree T.

Sample Input
10 15 5 7 4 3 12 6 17

Sample Output:
3
6

Solution:

The diameter of a tree is clearly explained in the question , the diameter of a tree can be entirely on the left hand side of the root , it can be entirely on the right side or it can stretch from left leaf node to the right leaf node , actually its the longest of these three , and height is the 

( no. of nodes in the longest path  - 1 ) and the longest path here stands for  the path from root to the leaf node.

so here i am giving a recursive code to find the height of the tree and also the diameter of tree , and this code is written for taking the inputs till EOF also since the test cases can be very large there is a separate  function to FREE the nodes after each test case.

Stack...( Largest Rectangle in a Histogram )

Another classical problem which involves use of stack is to find the area of the largest rectangle in a histogram.

Problem:
A histogram is a polygon composed of a sequence of rectangles aligned at a common base line. The rectangles have equal widths but may have different heights. For example, the figure on the left shows the histogram that consists of rectangles with the heights 2, 1, 4, 5, 1, 3, 3, measured in units where 1 is the width of the rectangles:



Usually, histograms are used to represent discrete distributions, e.g., the frequencies of characters in texts. Note that the order of the rectangles, i.e., their heights, is important. Calculate the area of the largest rectangle in a histogram that is aligned at the common base line, too. The figure on the right shows the largest aligned rectangle for the depicted histogram.

Input Specification

The input contains several test cases. Each test case describes a histogram and starts with an integer n, denoting the number of rectangles it is composed of. You may assume that 1<=n<=100000. Then follow n integers h1,...,hn, where 0<=hi<=1000000000. These numbers denote the heights of the rectangles of the histogram in left-to-right order. The width of each rectangle is 1. A zero follows the input for the last test case.

Output Specification

For each test case output on a single line the area of the largest rectangle in the specified histogram. Remember that this rectangle must be aligned at the common base line.

Sample Input

7 2 1 4 5 1 3 3
4 1000 1000 1000 1000
0

Sample Output

8
4000

Solution:

                                         

For every bar ‘x’, we calculate the area with ‘x’ as the smallest bar in the rectangle. If we calculate such area for every bar ‘x’ and find the maximum of all areas, our task is done. How to calculate area with ‘x’ as smallest bar? We need to know index of the first smaller (smaller than ‘x’) bar on left of ‘x’ and index of first smaller bar on right of ‘x’. Let us call these indexes as ‘left index’ and ‘right index’ respectively.

We traverse all bars from left to right, maintain a stack of bars. Every bar is pushed to stack once. A bar is popped from stack when a bar of smaller height is seen. When a bar is popped, we calculate the area with the popped bar as smallest bar. How do we get left and right indexes of the popped bar – the current index tells us the ‘right index’ and index of previous item in stack is the ‘left index’. Following is the complete algorithm.

1) Create an empty stack.
2) Start from first bar, and do following for every bar ‘hist[i]‘ where ‘i’ varies from 0 to n-1.
……a) If stack is empty or hist[i] is higher than the bar at top of stack, then push ‘i’ to stack.
……b) If this bar is smaller than the top of stack, then keep removing the top of stack while top of the stack is greater. Let the removed bar be hist[tp]. Calculate area of rectangle with hist[tp] as smallest bar. For hist[tp], the ‘left index’ is previous (previous to tp) item in stack and ‘right index’ is ‘i’ (current index).
3) If the stack is not empty, then one by one remove all bars from stack and do step 2.b for every removed bar.

Stack... ( Reverse Polish Notation or Infix To Post Fix)

A very common and classical problem which involves use of stack is to convert a given infix expression to a post fix expression or Reverse Polish Notation .

 Transform the Expression:

Transform the algebraic expression with brackets into RPN form (Reverse Polish Notation). Two-argument operators: +, -, *, /, ^ (priority from the lowest to the highest), brackets ( ). Operands: only letters: a,b,...,z. Assume that there is only one RPN form (no expressions like a*b*c).

Input

t [the number of expressions <= 100]
expression [length <= 400]
[other expressions]

Text grouped in [ ] does not appear in the input file.

Output

The expressions in RPN form, one per line.

Example

Input:
3
(a+(b*c))
((a+b)*(z+x))
((a+t)*((b+(a+c))^(c+d)))

Output:
abc*+
ab+zx+*
at+bac++cd+^*

Solution: