Postfix and infix expression evaluation Write C programs expression.h, expression.c to evaluate arithmetic infix expression. Use the queue data structure of Q1 to represent postfix expression. Use the stack data structure of Q2 to represent the stack for postfix expression evaluation. /* * convert infix expression in string to postfix expression

*infixstr); /* * evaluate and returns the value postfix expression passed by queue. */ int evaluate_postfix(QUEUE queue); * Evaluate and return the value of infix expression passed by string infixstr, * using infix_to_postfix() and evaluate_postfix() functions. */ int

evaluate_infix(char *infixstr); Public test gec common.c queue.c stack.c expression.c expression_main.c -o 93 93 infix expression: 10-((3*4)+8)/4 postfix expression:10 3 4 * 8 + 4 / - postfix evaluation:5 infix evaluation: 5 93 \"12 + 24*3\" * + infix expression:12 + 24*3 postfix expression: 12 24 3 postfix evaluation: 84 infix evaluation: 84 A6 problem: Design application specific linked list queue and stack data structures for prefix and postfix evaluation. Idea of the solution: The basic entity of an expression is operand, operator, parenthesis. Use linked list queue to represent postfix expression Use linked list stack to represent stack for prefix to postfix conversion and postfix evaluation Use the same node structure for both queue and stack . Data structure design and dependency common.h (linked list data structure) typedef struct node { int

struct queue {int length; NODE *front, *rear;} QUEUE; void enqueue(QUEUE *qp, NODE *np); NODE * dequeue(QUEUE *qp); void clean_queue(QUEUE *qp); #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); expression.h #include \"common.h\" #include \"stack.h\" #include \"queue.h\" QUEUE infix_to_postfix(char *infixstr); int evaluate_postfix(QUEUE queue); expression.c #include \"common.h\" #include \"queue.h\" #include \"stack.h\" #include \"expression.h\" QUEUE infix_to_postfix(char *infixstr) { char *p = infixstr; QUEUE queue = {0}; // result postfix expression in queue STACK stack = {0}; // auxiliary stack int sign = 1, num = 0; = = while (*p) { // expression str traversal if ( *p == '-' && (p == infixstr || *(p-1) == '(') ) {// get the sign of an operand sign = -1; } else if (*p >= '0' && *p = 'O' && *(p+1) =>=>