You are required to write a C program to carry out a strict-left-to-right evalua
ID: 3676009 • Letter: Y
Question
You are required to write a C program to carry out a strict-left-to-right evaluation of an arithmetic expression consisting of integer constants and the operators +, -, * and /. Here, the operator / denotes integer division; that is, the remainder is discarded. In a strict-left-to-right evaluation, there is no notion of precedence. For example, the value of the expression 6+4*3 when evaluated in a strict-left-to-right fashion is 30. (Under usual precedence rules, where multiplication has higher precedence than addition, the value of the above expression would be 18.) Similarly, the value of the expression 6+4*3/7-9 when evaluated in a strict-left-to-right fashion is = -5.
Here is some additional information about the input.
1. Each input expression is terminated by the newline (' ') character.
2. There may be zero or more spaces between successive non-blank characters of an expression.
3. You may assume that the given expression is valid; that is, it satisfies all of the following conditions.
a. The expression consists only of integer constants, the operators +, -, * and / and spaces. In particular, the expression won't contain parentheses.
b. Each integer constant in the expression consists of only one decimal digit.
c. The expression begins with an integer constant, without any preceding sign.
d. In the expression, integer constants and operators alternate.
Note that an expression consisting of a single digit integer constant, without any operators, is a valid expression.
The outline of your C program is as follows.
1) Prompt the user for an expression.
2) Read the expression character by character and carry out a strict-left-to-right evaluation of the expression.
3) Print the value of the result obtained in Step 2 and stop.
Explanation / Answer
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
/* maximum length of input string (including newline character) */
#define INPUT_MAX 2048
/* enable (1) or disable (0) parentheses checking in parsing strings */
/* leave disabled for part (a); enable for part (b) */
#define PARSE_PARENS 0
/* type of token */
enum token_type {
OPERAND, /* number */
OPERATOR, /* operator: +, -, *, / */
#if PARSE_PARENS
LPARENS, /* left parentheses ( */
RPARENS /* right parentheses ) */
#endif
};
/* operator identifiers (opcodes) */
enum op {
ADD, /* a+b */
SUBTRACT, /* a-b (binary) */
MULTIPLY, /* a*b */
DIVIDE, /* a/b */
NEGATE /* -a (unary) */
};
/* direction of evaluation (associativity) */
enum assoc {
LEFT, /* left-to-right (+, binary -, *, /) */
RIGHT /* right-to-left (unary -) */
};
/* number of operands for each operator type */
const unsigned int op_operands[] = {2, 2, 2, 2, 1};
/* order-of-operations (precedence) (0 = evaluated last) */
const unsigned int op_precedences[] = {0, 0, 1, 1, 2};
/* evaluation direction (associativity) for each precedence level */
const enum assoc op_associativity[] = {LEFT, LEFT, RIGHT};
/* contains value of token */
union token_value {
double operand; /* numeric value for operand */
enum op op_code; /* opcode for operators */
};
/* data structure for token */
typedef struct s_expr_token {
union token_value value; /* numeric value or opcode */
enum token_type type; /* type of token */
struct s_expr_token * linked_token; /* linked token in stack/queue */
} * p_expr_token; /* p_expr_token is shorthand for "struct s_expr_token *" */
/* data structure for queue */
struct token_queue {
p_expr_token front; /* front of queue, where tokens are dequeued */
p_expr_token back; /* back of queue, where tokens are added */
};
/* queue functions - enqueue and dequeue */
void enqueue(struct token_queue * pqueue, const p_expr_token ptoken);
p_expr_token dequeue(struct token_queue * pqueue);
/* stack functions - push and pop */
void push(p_expr_token * ptop, const p_expr_token ptoken);
p_expr_token pop(p_expr_token * ptop);
/* creates a new token in dynamic memory (using malloc()) */
p_expr_token new_token(const enum token_type type, const union token_value value);
/* constructs a queue of tokens in infix order from a space-delimited string */
struct token_queue expr_to_infix(char * str);
/* creates a queue of tokens in postfix order from a queue of tokens in infix order */
/* postcondition: returned queue contains all the tokens, and pqueue_infix should be
empty */
struct token_queue infix_to_postfix(struct token_queue * pqueue_infix);
/* evalutes the postfix expression stored in the queue */
/* postcondition: returned value is final answer, and pqueue_postfix should be empty */
double evaluate_postfix(struct token_queue * pqueue_postfix);
/* handles evaluation process (calls above functions) for expression string str */
double evaluate(const char * str);
int main(void) {
char input[INPUT_MAX];
double ans;
unsigned int len;
do {
printf("Enter an expression to evaluate: ");
fflush(stdout);
if (!fgets(input, INPUT_MAX, stdin))
abort(); /* failed to read stdin */
len = strlen(input);
/* remove trailing newline character */
if (len > 0 && input[len-1] == ' ') {
input[len-1] = '';
--len;
}
if (len == 0) /* empty expression signals exit */
break;
/* call evaluation functions */
ans = evaluate(input);
/* write result to stdout */
printf("%s => %g ", input, ans);
} while (1);
return 0;
}
/* enqueue (add) token to end of queue
input: pqueue - pointer to queue
ptoken - token pointer to add
postcondition: token added to end of queue */
void enqueue(struct token_queue * pqueue, const p_expr_token ptoken) {
ptoken->linked_token = NULL;
if (pqueue->back)
pqueue->back->linked_token = ptoken;
else /* empty */
pqueue->front = ptoken;
pqueue->back = ptoken;
}
/* dequeue (remove) token from front of queue
input: pointer to queue
output: front token pointer (or NULL, if queue was empty)
postcondition: token removed from queue */
p_expr_token dequeue(struct token_queue * pqueue) {
p_expr_token ptoken = pqueue->front;
if (pqueue->front) {
pqueue->front = ptoken->linked_token;
if (ptoken == pqueue->back) /* at end */
pqueue->back = NULL;
ptoken->linked_token = NULL;
}
return ptoken;
}
/* push (add) token to top of stack
input: ptop - pointer to top token pointer of stack
ptoken - token pointer to add
postcondition: ptop points to the added token */
void push(p_expr_token * ptop, const p_expr_token ptoken) {
ptoken->linked_token = *ptop;
*ptop = ptoken;
}
/* pop (remove) token from top of stack
input: pointer to top token pointer of stack
output: top token pointer (or NULL, if stack was empty)
postcondition: ptop points to next token in stack */
p_expr_token pop(p_expr_token * ptop) {
p_expr_token ptoken;
if ( (ptoken = *ptop) ) {
*ptop = ptoken->linked_token;
ptoken->linked_token = NULL;
}
return ptoken;
}
/* allocate new token on heap, with specified type and value; the token is initially
un-linked (field "linked_token" == NULL)
note: token must be freed using free() after use */
p_expr_token new_token(const enum token_type type, const union token_value value) {
p_expr_token ptoken = (p_expr_token)malloc(sizeof(struct s_expr_token));
ptoken->type = type;
ptoken->value = value;
ptoken->linked_token = NULL;
return ptoken;
}
/* handles evaluation process (calls above functions) for expression string str */
/* returns the final answer */
double evaluate(const char * str) {
char * strbuffer; /* mutable buffer for string (modified in calls to strtok()) */
double ans; /* answer to return */
struct token_queue queue_infix, queue_postfix;
/* copy str into mutable buffer */
strbuffer = strcpy((char *)malloc(strlen(str)+1),str);
/* get queue of tokens in infix order from string buffer */
queue_infix = expr_to_infix(strbuffer);
/* get queue of tokens in postfix order from infix-ordered queue */
queue_postfix = infix_to_postfix(&queue_infix);
/* get answer from postfix-ordered queue */
ans = evaluate_postfix(&queue_postfix);
free(strbuffer); /* free memory from heap */
return ans;
}
/* constructs a queue of tokens in infix order from a space-delimited string */
struct token_queue expr_to_infix(char * str) {
struct token_queue queue_infix; /* queue with infix ordering */
enum token_type type = OPERATOR;
union token_value value;
/* initialize the queue to empty */
queue_infix.front = NULL;
queue_infix.back = NULL;
/* delimiter string for strtok() -- contains whitespace characters */
#define DELIMS_STR " "
for (str = strtok(str, DELIMS_STR); str; str = strtok(NULL, DELIMS_STR)) {
/* parse token */
if (strlen(str) == 1) { /* operators are all 1 character */
switch (str[0]) {
case '+':
type = OPERATOR;
value.op_code = ADD;
break;
case '-':
/* check previous token to distinguish between
negate (unary) and subtract (binary) */
if (type == OPERATOR)
value.op_code = NEGATE; /* unary */
#if PARSE_PARENS
else if (type == LPARENS)
value.op_code = NEGATE; /* unary */
#endif
else
value.op_code = SUBTRACT; /* binary */
type = OPERATOR;
break;
case '*':
type = OPERATOR;
value.op_code = MULTIPLY;
break;
case '/':
type = OPERATOR;
value.op_code = DIVIDE;
break;
#if PARSE_PARENS
case '(':
type = LPARENS;
break;
case ')':
type = RPARENS;
break;
#endif
default:
/* not an operator */
type = OPERAND;
value.operand = strtod(str, NULL);
}
} else {
type = OPERAND;
value.operand = strtod(str, NULL);
}
/* add token with parsed type and value to end of queue */
enqueue(&queue_infix, new_token(type, value));
}
return queue_infix;
}
/* creates a queue of tokens in postfix order from a queue of tokens in infix order */
/* postcondition: returned queue contains all the tokens, and pqueue_infix should be
empty */
struct token_queue infix_to_postfix(struct token_queue * pqueue_infix) {
/* TODO: construct postfix-ordered queue from infix-ordered queue;
all tokens from infix queue should be added to postfix queue or freed */
struct token_queue queue_postfix;
p_expr_token p_op_top = NULL;
p_expr_token token = NULL;
p_expr_token op_token = NULL;
enum op stack_top_op_code;
enum op curr_op_code;
queue_postfix.front = NULL;
queue_postfix.back = NULL;
while(pqueue_infix->front) {
token = dequeue(pqueue_infix);
if (token->type == OPERAND) {
enqueue(&queue_postfix, token);
}
else {//if <token> is an operator
if (p_op_top) {//if the operator stack is not empty
stack_top_op_code = (p_op_top->value).op_code;
curr_op_code = token->value.op_code;
if ((op_precedences[curr_op_code] < op_precedences[stack_top_op_code]) || ((op_precedences[curr_op_code] == op_precedences[stack_top_op_code]) && (op_associativity[stack_top_op_code] == LEFT))) {
op_token = pop(&p_op_top);
enqueue(&queue_postfix, op_token);
}
}
else {
push(&p_op_top, token);
}
}
}
while(p_op_top) {
op_token = pop(&p_op_top);
enqueue(&queue_postfix, op_token);
}
}
/* evalutes the postfix expression stored in the queue */
/* postcondition: returned value is final answer, and pqueue_postfix should be empty */
double evaluate_postfix(struct token_queue * pqueue_postfix) {
/* TODO: process postfix-ordered queue and return final answer;
all tokens from postfix-ordered queue is freed */
p_expr_token pstack = NULL;
p_expr_token d1;
p_expr_token d2;
p_expr_token curr;
union token_value my_tv;
double val1;
double val2;
double res;
while (pqueue_postfix->front) {
curr = dequeue(pqueue_postfix);
if(curr->type == OPERAND) {
push(&pstack, curr);
}
else {
d1 = dequeue(pqueue_postfix);
d2 = dequeue(pqueue_postfix);
val1 = (d1->value).operand;
val2 = (d2->value).operand;
switch((curr->value).op_code) {
case ADD:
res = val1 + val2;
break;
case SUBTRACT:
res = val1 - val2;
break;
case MULTIPLY:
res = val1 * val2;
break;
case DIVIDE:
res = val1 / val2;
break;
default:
break;
}
my_tv.operand = res;
curr = new_token(OPERAND, my_tv);
push(&pstack, curr);
}
}
curr = pop(&pstack);
return (curr->value).operand;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.