10467 - Parse Tree

All about problems in Volume 104. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

10467 - Parse Tree

Post by ditrix » Tue Mar 11, 2003 4:26 am

What about the case F->(E)?
What means "A string of
@+!
DitriX

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan » Tue Mar 11, 2003 4:50 am

I think you're asking for cases like:
(i+i*i)
The judge solution says:

Code: Select all

      E
      |
      T
      |
      F
======|============
(     E           )
   ===|======
   E  +     T
   |     ===|===
   T     T  *  F
   |     |     |
   F     F     i
   |     |
   i     i
The statement "A string of

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

Post by ditrix » Wed Mar 12, 2003 5:52 pm

so, the right way is to print the '='s over the all subtree of "F->(E)", isn't it? And in worst case when F->(E) is the root of the tree, '='s will fill the width of picture?

And why in your exemple the root is "E->T" and not "F->(E)"? Is it the rule, that the root must be "E->"?
@+!
DitriX

Adil
Learning poster
Posts: 57
Joined: Sun Sep 29, 2002 12:00 pm
Location: in front of the monitor :-)
Contact:

Post by Adil » Thu Mar 13, 2003 2:35 am

if you notice carefully, the problem-statement and your statement imply the same format. if you print "="s over the immediate children, it will automatically cover the whole subtree expanding from it. and the problem also requires the leaves to be printed in specific columns (where no two leaves can be printed in the same column). so the second-tree you provided in your first post is not right-formatted.

yes, the root of the parse-tree must always be E. i guess it should've been stated explicitly. sorry about that.

hope there is no more confusion.

[ problemsetter for this problem ]
Last edited by Adil on Thu Mar 13, 2003 2:58 pm, edited 1 time in total.

ditrix
New poster
Posts: 33
Joined: Sat Mar 01, 2003 12:38 am
Location: Paris

Post by ditrix » Thu Mar 13, 2003 11:03 am

Thank you. now it's more clear for me.
@+!
DitriX

Post Reply

Return to “Volume 104 (10400-10499)”