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.

/* * infixetr - input string of infix expression ^ compute and return the postfix expression represented in QUEUE */ QUEUE infix_to_postfix(char *infixstr); /* * evaluate the postfix expression passed by queue, and returns the value. */ 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

command: gcc common.c queue.c stack.c expression.c expression_main.c -o q3 command: q3 infix expression:10-((3*4)+8)/4 postfix expression:10 3 4 * 8 + 4 / - postfix evaluation:5 infix evaluation:5

expression_main.c

#include #include "queue.h" #include "expression.h"

int main(int argc, 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)); 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

expression.h

#ifndef EXPRESSION_H #define EXPRESSION_H #include "common.h" #include "queue.h" QUEUE infix_to_postfix(char *infixstr); int evaluate_postfix(QUEUE queue); int evaluate_infix(char *infixstr); #endif

common.h

#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

queue.h

#ifndef QUEUE_H #define QUEUE_H #include "common.h" typedef struct queue { int length; NODE *front; NODE *rear; } QUEUE; void enqueue(QUEUE *qp, NODE *np); NODE *dequeue(QUEUE *qp); void clean_queue(QUEUE *qp); #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 <= '9' ) 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_infix(char *infixstr) { // your implementation }