blob: 271615bf0524d32a2e9a1f619e28b92b98606cd7 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
|
#! /usr/bin/env gforth
\ Challenge 094
\
\ TASK #2 � Binary Tree to Linked List
\ Submitted by: Mohammad S Anwar
\ You are given a binary tree.
\
\ Write a script to represent the given binary tree as an object and flatten
\ it to a linked list object. Finally print the linked list object.
\
\ Example:
\ Input:
\
\ 1
\ / \
\ 2 3
\ / \
\ 4 5
\ / \
\ 6 7
\
\ Output:
\
\ 1 -> 2 -> 4 -> 5 -> 6 -> 7 -> 3
80 CONSTANT MAXLINE
10 CONSTANT '\n'
\ -----------------------------------------------------------------------------
\ read lines from stdin and store them in dictionary
0 VALUE num_lines
: ,line { src len -- }
HERE ( dest )
len ALLOT \ reserve space
src SWAP len CMOVE \ copy to space
'\n' C, \ append line terminator
;
: ,lines
BEGIN
PAD DUP MAXLINE STDIN READ-LINE THROW
WHILE
,line
num_lines 1+ TO num_lines
REPEAT
2DROP
;
CREATE lines ,lines
\ get start of row
: row[] ( row -- row-addr )
lines SWAP ( lines row )
0 ?DO \ loop for rows
BEGIN DUP C@ '\n' <> WHILE \ find end of each row
1+
REPEAT
1+
LOOP
;
\ advance from start of row to column
: col[] ( row-addr col -- char-addr )
0 ?DO
DUP C@ '\n' <> IF
1+ \ increment unless end of line
THEN
LOOP
;
\ get address of character at row, col
: lines[][] ( row col -- addr )
SWAP row[]
SWAP col[]
;
\ get character at row, col
: char[][] ( row col -- char )
lines[][] C@
;
: char[][]isdigit ( row col -- f )
char[][]
DUP '0' >= SWAP '9' <= AND
;
: char[][]isnewline ( row col -- f )
char[][]
'\n' =
;
\ -----------------------------------------------------------------------------
\ Representation of a tree
: new_node ( -- node )
HERE 0 , 0 , 0 ,
;
: node.value ( node-addr -- value-addr )
;
: node.left ( node-addr -- left-addr )
1 CELLS +
;
: node.right ( node-addr -- right-addr )
2 CELLS +
;
: parse_subtree { row col -- node }
new_node ( node )
row col char[][] '0' - ( node value )
OVER node.value ! \ store value
row 2 + num_lines < IF \ have children
row 1+ col 1- char[][] '/' = IF \ have left child
row 2 + col 2 - RECURSE ( node child-node )
OVER node.left ! \ store left subtree
THEN
row 1+ col 1+ char[][] '\' = IF \ have right child
row 2 + col 2 + RECURSE ( node child-node )
OVER node.right ! \ store right subtree
THEN
THEN
;
: parse_tree ( -- root )
0 ( col )
BEGIN
0 OVER ( col row col )
char[][]isdigit IF
0 SWAP ( row col )
parse_subtree
EXIT ( node )
THEN
0 OVER
char[][]isnewline IF
1 THROW \ root not found
THEN
1+ ( col++ )
AGAIN
;
\ -----------------------------------------------------------------------------
\ Flatten the tree
: flatten_tree { root -- }
root IF \ root not null
root node.left @ ( left )
DUP RECURSE \ flatten left sub-tree
root node.right @ ( left right )
DUP RECURSE \ flatten right sub-tree
0 root node.left ! \ left = 0
SWAP root node.right ! \ right = left; ( right )
root ( right node )
BEGIN DUP node.right @ WHILE
node.right @
REPEAT ( right rightmost-node )
node.right !
THEN
;
: print_tree ( root )
BEGIN ?DUP WHILE
DUP node.value @ .
DUP node.right @ IF ." -> " THEN
node.right @
REPEAT
CR
;
parse_tree VALUE tree \ parse tree, save root
tree flatten_tree \ flatten the tree
tree print_tree
BYE
|
