Write C programsstack.h, stack.cto implement the stack data structure using the NODE list using the node structure of above question.

typedef struct stack {

int height;

NODE *top;

} STACK;

/*

* push NODE *np onto STACK *sp, and maintain the height property

*/

void push(STACK *sp, NODE *np);

/*

* pop and return the pointer to the removed top node, maintain the height property.

*/

NODE *pop(STACK *sp);

void clean_stack(STACK *sp);

Use the provided main program stack_main.c to test the above functions.

Public test

gcc common.c stack.c stack_main.c -o q2

q2

str:12 34 56 78 90 + - * /

display stack:/ * + 90 78 56 34 12

stack height:8

pop:/ * + 90 78 56 34 12

stack-height:0

stack.h

#ifndef STACK_H

#define STACK_H

#include \"common.h\"

typedef struct stack {

int height;

NODE *top;

} STACK;

void push(STACK *sp, NODE *np);

NODE *pop(STACK *sp);

void clean_stack(STACK *sp);

#endif

stack.c

#include

#include \"stack.h\"

void push(STACK *sp, NODE *np) {

// your implementation

}

NODE *pop(STACK *sp) {

// your implementation

}

void clean_stack(STACK *sp) {

// your implementation,

// call clean() function in common.h

}

#include

#include

#include \"common.h\"

#include \"stack.h\"

intmain(intargc,char* args[]) {

char*str = \"12 34 56 78 90 + - * /\";

if(argc>1) str = args[1];

printf(\"str:%s \", str);

// parse

STACK stack = {0};

intsign = 1;

intnum = 0;

char*p = str;

while(*p) { // parse space separated string and push into stack

if( *p == '-' && (p == str || *(p-1) == ' ') ) { // determine negative sign

sign = -1;

}

elseif(*p >= '0' && *p =>

num = *p-'0';

while((*(p+1) >= '0' && *(p+1) =>

num = num*10 + *(p+1)-'0';

p++;

}

push(&stack, new_node(num, 0));

sign = 1;

}

elseif(*p == '+' || *p == '-' || *p == '*' || *p == '/' || *p == '%')

push(&stack, new_node(*p, 1));

elseif(*p == '(')

push(&stack, new_node(*p, 2));

elseif(*p == ')')

push(&stack, new_node(*p, 3));

else

; // ignore

p++;

}

printf(\"display stack:\");

display(stack.top);

printf(\" stack height:%d \",stack.height);

printf(\"pop:\");

NODE *np =NULL;

while(stack.top) {

np = pop(&stack);

if(np->type == 0)

printf(\"%d\", np->data);

else

printf(\"%c\", np->data);

free(np);

if(stack.top) printf(\" \");

}

clean_stack(&stack);

printf(\" stack-height:%d \",stack.height);

return0;

}

#include

#include

#include \"common.h\"

NODE *new_node(intdata,inttype) {

NODE *np = (NODE *) malloc(sizeof(NODE));

np->data = data;

np->type = type;

np->next =NULL;

returnnp;

}

voiddisplay(NODE *start) {

while(start) {

if(start->type == 0)

printf(\"%d\", start->data);

else

printf(\"%c\", start->data);

start = start->next;

if(start) printf(\" \");

}

}

voidclean(NODE **startp) {

NODE *p = *startp;

while(p) {

NODE *tmp = p;

p = p->next;

free(tmp);

}

*startp =NULL;

}

#ifndef COMMON_H

#define COMMON_H

/* node structure for postfix expression by queue and evaluation by stack */

typedefstructnode {

intdata; // int data is used for int operand, operator ascii code, or parenthesis assii code

inttype; // 0: int operand; 1:operator; 2: left parenthesis 3: right parenthesis

structnode *next;

} NODE;

NODE *new_node(intdata,inttype);

voiddisplay(NODE *start);

voidclean(NODE **startp);

#endif