Write C programs stack.h, stack.c to implement the stack data structure using the NODE list using the node structure of above question.

/* * STACK - an interface structure represents the height and accessing points of linked list stack data structure. */ 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. * do not free the removed node in the function. */ NODE *pop(STACK *sp); /* * delete and free all nodes of the stack, and reset the top and height. . */ void clean_stack(STACK *sp);

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

Public test

command: gcc common.c stack.c stack_main.c -o q2 command: 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_main.c:

#include #include #include "common.h" #include "stack.h"

int main(int argc, char* args[]) { char *str = "12 34 56 78 90 + - * /"; if (argc>1) str = args[1]; printf("str:%s ", str); // parse STACK stack = {0}; int sign = 1; int num = 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; } else if (*p >= '0' && *p <= '9'){ num = *p-'0'; while ((*(p+1) >= '0' && *(p+1) <= '9')) { num = num*10 + *(p+1)-'0'; p++; } push(&stack, new_node(num, 0)); sign = 1; } else if (*p == '+' || *p == '-' || *p == '*' || *p == '/' || *p == '%') push(&stack, new_node(*p, 1)); else if (*p == '(') push(&stack, new_node(*p, 2)); else if (*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); return 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 

common.c

#ifndef COMMON_H #define COMMON_H

/** NODE - a structure represents the element of an arithmetic expression * data - represents operand, operator ASCII code, or parenthesis ASCII code * type - 0 for operand; 1 for operator; 2 for left parenthesis 3 for right parenthesis */ typedef struct node { int data; int type; struct node *next; } NODE;

NODE *new_node(int data, int type); void clean(NODE **startp); void display(NODE *start);

#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, }