/**
 *   Løsning til eksamen i AlgMet, august 2025, oppgave 1.
 *
 *   @file     EX_S25_1.TXT
 *   @author   Frode Haug, NTNU
 */



OPPGAVE A:
==========
          
   Infix-uttrykket:        (((( 4 * 5 ) + 6 ) * ( 4 + ( 2 * 3 ))) + 8 )


   skrevet POSTFIX blir:   4  5  *  6  +  4  2  3  *  +  *  8  +


                                                *
                                             +  +  +
   Stakken underveis:      _  *  _  +  _  *  *  *  *  *  _  +  _
 
                               ('_' betyr at stakken er tom)





OPPGAVE B:
==========

    "STRUTSEKLO" satt inn i:

    1)  Heap:      U T S S T R E K L O


    2)  Binært søketre:        S
                             /   \
                           R       T
                          /       / \ 
                         E       S   U
                          \         /
                           K       T
                            \
                             L
                              \
                               O

 
    3)  2-3-4 tre:             S
                           /       \
                         K           T
                       /   \       /   \
                      E    LOR    ST    U
      


    4)  Red-Black tre:         S
                           /       \
                         K           T
                       /   \       /   \
                      E     O     S     U        (eller ST rotert andre veien)
                          // \\    \\
                          L   R     T





OPPGAVE C:
==========

    H: 4   I:  5    strutseklo             (ingenting skjer)
    H: 4   I:  6    sSrutTeklo    'S' vandrer forbi 'T'
    H: 4   I:  7    ssEuttRklo    'E' vandrer forbi 'R'
    H: 4   I:  8    sseKttrUlo    'K' vandrer forbi 'U'
    H: 4   I:  9    LsekStruTo    'L' vandrer forbi 'T' og 'S'
    H: 4   I: 10    lOeksSrutT    'O' vandrer forbi 'T' og 'S'

    H: 1   I:  2    loekssrutt             (ingenting skjer)
    H: 1   I:  3    ELOkssrutt    'E' vandrer forbi "LO"
    H: 1   I:  4    eKLOssrutt    'K' vandrer forbi "LO"
    H: 1   I:  5    eklossrutt             (ingenting skjer)
    H: 1   I:  6    eklossrutt             (ingenting skjer)
    H: 1   I:  7    ekloRSSutt    'R' vandrer forbi "SS"
    H: 1   I:  8    eklorssutt             (ingenting skjer)
    H: 1   I:  9    eklorssTUt    'T' vandrer forbi 'U'
    H: 1   I: 10    eklorsstTU    'T' vandrer forbi 'U'