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 represented by QUEUE and return the postfix expression queue.

*/

QUEUE infix_to_postfix(char *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);

Use provided main program expression_main.c to test above functions.

Public test

gcc common.c queue.c stack.c expression.c expression_main.c -o q3

q3

infix expression:10-((3*4)+8)/4

postfix expression:10 3 4 * 8 + 4 / -

postfix evaluation:5

infix evaluation:5

q3 \"12 + 24*3\"

infix expression:12 + 24*3

postfix expression:12 24 3 * +

postfix evaluation:84

infix evaluation:84

expression.h

#ifndef EXPRESSION_H

#define EXPRESSION_H

#include \"common.h\"

#include \"queue.h\"

/*

* convert infix expression in string to postfix expression represented by QUEUE and return the postfix expression queue.

*/

QUEUE infix_to_postfix(char *infixstr);

/*

* evaluate and returns the value postfix expression passed by queue.

*/

int evaluate_postfix(QUEUE queue);

/*

* evaluate and return the value of prefix expression passed by string infixstr, using infix_to_postfix() and evaluate_postfix() functions.

*/

int evaluate_prefix(char *infixstr);

#endif

expression.c

#include

#include

#include \"common.h\"

#include \"queue.h\"

#include \"stack.h\"

#include \"expression.h\"

/*

* auxiliary function

*/

int get_priority(char op) {

if (op == '/' || op == '*' || op == '%')

return 1;

else if (op == '+' || op == '-')

return 0;

else

return -1;

}

/*

* auxiliary function

*/

int type(char c) {

if (c >= '0' && c =>

return 0;

else if (c == '/' || c == '*' || c == '%' || c == '+' || c == '-')

return 1;

else if (c == '(')

return 2;

else if ( c == ')')

return 3;

else

return 4;

}

QUEUE infix_to_postfix(char *infixstr) {

// your implementation

}

int evaluate_postfix(QUEUE queue) {

// your implementation

}

int evaluate_prefix(char *infixstr) {

// your implementation

}

#include

#include \"queue.h\"

#include \"expression.h\"

intmain(intargc,char*args[]) {

char*infixstr = \"10-((3*4)+8)/4\";

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

printf(\"infix expression:%s \", infixstr);

QUEUE postfix_queue = infix_to_postfix(infixstr);

printf(\"postfix expression:\");

display(postfix_queue.front);

printf(\" \");

printf(\"postfix evaluation:%d \", evaluate_postfix(postfix_queue));

clean_queue(&postfix_queue);

printf(\"infix evaluation:%d \", evaluate_infix(infixstr));

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