hw2-1

1.a). Stack is most appropriate. Rule (iii) is an obvious LIFO matching.
   b).
    while (ch!=EOF)
    {
        switch(ch){
        case '{': if (stack.top()==NULL || stack.top()=='{')
                        stack.push(ch);
                   else error iv;
                   break;
        case '(':
        case '[': stack.push(ch);
                  break;
        case ')':
        case ']':
        case '}': ch_top = stack.pop();
                   if (!ch_top)
                      error ii;
                   else if ch_top!= the opposite symbol of ch
                      error iii;

    }
    if (!stack.isEmpty())
        error i;

c). as shown in the pseudocode, rules 1,2,3,5 are upholded. rule 4 is upholded because when two symbols match, it's legal so the opener will be poped off the stack and we'll be able to continue to look at the next closer to see if it matches with the previous opener that is now on top of the stack.

3. postorder:    GHDILMJEBKFCA
    inorder:        GDHBIELJMACFK
    preoder:       ABDGHEILMJCFK

6.                 chaining                                    linear probing                            quadratic probing
    0
    1
    2            --> 3102                                   3102                                            7113
    3            --> 7113->9283                       9283                                            9283
    4            --> 6294->2004                       2004                                            2004
    5                                                             7113                                            6294
    6                                                             6294                                            3102
    7            --> 5907                                   5907                                            5907
    8
    9