ME 6

GeneralizedListNode * readInput()
{
  char symbol;
  Stack S;
  InitStack(&S);
  while(scanf("%c", &symbol) != EOF)
  {
      //    if symbol is left parenthesis
    if(symbol == '(')
    {
    //  push to stack S
    StackElemType x;
    x.character = symbol;
    x.generalizedListNode = NULL;
    PUSH(&S,x);
    }
    //  else if symbol is an atom
    else if(isAtom(symbol))
    {
        //      push to stack S
        StackElemType x;
        x.character = symbol;
        x.generalizedListNode = NULL;
        PUSH(&S,x);
    }
    //  else if symbol is right parenthesis
    else if(symbol == ')')
    {
        StackElemType x;
        if(!IsEmptyStack(&S))
        {
            // pop a stack element,say top, from S (make sure stack is not empty before doing so)
            POP(&S,&x); // x = top
        }
        //      set prevNode to null
        GeneralizedListNode *prevnode = NULL;
        //      while stack S is not empty
        while(!IsEmptyStack(&S))
        {
            //          if top is an atom
            if(isAtom(x.character) == 1)
            {
                //              create a corresponding GeneralizedListNode, say node
                //                  with tag=0;atom=top.character;list=null;link=prevNode
                GeneralizedListNode *node = (GeneralizedListNode*) malloc(sizeof(GeneralizedListNode));
                node->tag = 0;
                node->dataAtom = x.character;
                node->dataList = NULL;
                node->link = prevnode;
                //              update prevNode with node
                prevnode = node;
            }
            //          else if top is a left parenthesis
            else if(x.character == '(')
            {
                //              create a corresponding GeneralizedListNode
                //                  with tag=1;atom=0;list=prevNode;link=null
                GeneralizedListNode *node = (GeneralizedListNode*) malloc(sizeof(GeneralizedListNode));
                node->tag = 1;
                // node->dataAtom = 0;
                node->dataList = prevnode;
                node->link = NULL;
                //              update prevNode with node
                prevnode = node;
                //              push node to stack S
                StackElemType y;
                // y.character = 0;
                y.generalizedListNode = node;
                PUSH(&S,y);
                //              break
                break;
            }
            //          else if top is a GeneralizedListNode
            else if(x.generalizedListNode != NULL)
            {
                //              update value of the link of top with prevNode
                x.generalizedListNode->link = prevnode;
                //              update prevNode with value of top
                prevnode = x.generalizedListNode;

            }
            //          pop a stack element from S and store to top
            POP(&S,&x);
        }
        //      if stack is empty
        if(IsEmptyStack(&S))
        {
            //            return prevNode;
            return prevnode;
        }
    }
  }

}

void traverse_generalized_list(GeneralizedListNode *root)
{
    Stack S;
    InitStack(&S);
    GeneralizedListNode *t = root;
    if(t == NULL) return;
    while(1)
    {
        if(t == NULL)
        {
            if(!IsEmptyStack(&S))
            {
                StackElemType stk_elem;
                POP(&S,&stk_elem);
                t = stk_elem.generalizedListNode->link;
                continue;
            }
            else
            {
                return;
            }
        }
        if(t->tag == 0)
        {
            VISIT(t);
            t = t->link;
        }
        else
        {
            t = t->dataList;
        }

    }
}