Electronic Design Automation

10.2.2. Normalized Polish expression for slicing floorplans

In Section 10.1.3, a binary tree is used to model a slicing floorplan. We can record the binary tree by use of a Polish expression E = e¹e² … e^2n-1 where eⁱ ∈ {1, 2, …, n, H, V}. Here, each number denotes a module and H (V) represents a horizontal (vertical) cut in the slicing floorplan. The Polish expression is the postfix ordering of a binary tree, which can be obtained from the post-order traversal on a binary tree given in Algorithm 10.2. The length of E is 2^n-1, where n is the number of modules.

Algorithm 10.2. PostOrderTraversal(T)

Because the Polish expression is the postfix ...