Instructions
Objective
Write a program to Parse expressions in the expression tree in C.
Requirements and Specifications
Write a C assignment that takes as input a fully parenthesized, arithmetic expression of binary operators +, −, ∗, /, and converts the expression into a binary expression tree. Your program should take input from the command line. The entire expression should be in a character string without any space in it.
An input string only includes floating numbers in the format of Y.YY, that is, one digit to the left of the decimal point and two digits to the right of the decimal point, and variables of the form of x1, x2, ....
Your program shall allow for the leaves in the expression tree not only to store floating values but also to store variables of the form x1, x2, x3, ..., which are initially 0.00
Your program should then show a menu with the following options:
- Preorder
- Inorder (Not required)
- Postorder
- Update (Not required)
- Calculate (Not required)
- Exit
Screenshots of output
Source Code
Makefile
CC=gcc
CFLAGS=-g -Wall
all: q1
q1: q1.o
$(CC) $(CFLAGS) -o q1 q1.o
q1.o: q1.c
$(CC) $(CFLAGS) -o q1.o -c q1.c
clean:
rm -f *.o q1
Question 1
#include
#include
#include
typedef enum {OPERATOR, NUMBER, VARIABLE} type_t;
/* definition of the node of an expression tree */
typedef struct expr_s
{
type_t type; /* type of this expression */
char op; /* operator */
float num; /* floating value */
int var; /* variable x */
struct expr_s *left;
struct expr_s *right;
}expr_t;
/* create a new expression of the given type */
expr_t *new_expr(type_t type)
{
expr_t *expr = (expr_t *) malloc(sizeof (expr_t));
expr->type = type;
expr->left = NULL;
expr->right = NULL;
return expr;
}
/* get a variable from the string */
expr_t *parse_var(char **str)
{
expr_t *expr;
char *p = *str;
int num;
if (*p == 'x')
{
p++;
num = 0;
while (isdigit(*p)) /* get x number */
{
num = num*10 + (*p - '0'); /* add digit to number */
p++;
}
if (num == 0) /* only variables >= 1 are supported */
{
printf("Error: invalid variable number\n");
exit(1);
}
*str = p; /* advance string pointer after variable */
expr = new_expr(VARIABLE);
expr->var = num; /* save variable number */
expr->num = 0.0; /* variable value */
return expr;
}
return NULL;
}
/* get a floating point number from the string */
expr_t *parse_num(char **str)
{
expr_t *expr;
char *p = *str;
int i;
int whole;
int dec;
if (isdigit(*p))
{
whole = *p - '0';
p++;
if (*p != '.') /* should be a decimal point */
{
printf("Error: expected decimal point\n");
exit(1);
}
i = 0;
dec = 0;
p++;
while (isdigit(*p)) /* get numbers after point */
{
dec = dec*10 + (*p - '0'); /* add digit to number */
i++;
p++;
}
if (i != 2) /* only 2 decimals supported */
{
printf("Error: too many decimals\n");
exit(1);
}
*str = p; /* advance string pointer after number */
expr = new_expr(NUMBER);
expr->num = whole * 1.0 + dec/100.0; /* variable value */
return expr;
}
return NULL;
}
/* returns 1 if it's an operator, 0 otherwise */
int is_operator(char c)
{
return (c == '+' || c == '-' || c == '*' || c == '/');
}
expr_t *parse_expr(char **str);
/* parses an operand */
expr_t *parse_operand(char **str)
{
expr_t *expr;
/* if first part was a parenthesized expression */
if ((expr = parse_expr(str)) != NULL)
return expr;
else if ((expr = parse_var(str)) != NULL)
return expr;
else if ((expr = parse_num(str)) != NULL)
return expr;
return NULL;
}
/* parse a fully parenthesized expression and build an expression tree */
expr_t *parse_expr(char **str)
{
expr_t *expr, *expr1, *expr2;
char op;
if (*str[0] == '(')
{
(*str)++; /* advance string pointer after ( */
if ((expr1 = parse_operand(str)) == NULL)
{
printf("Error: invalid expression\n");
exit(1);
}
if (!is_operator(*str[0]))
{
printf("Error: expected an operator\n");
exit(1);
}
op = *str[0];
(*str)++; /* advance string pointer after operator */
if ((expr2 = parse_operand(str)) == NULL)
{
printf("Error: invalid expression\n");
exit(1);
}
if (*str[0] != ')')
{
printf("Error: expected a closing parenthesis\n");
exit(1);
}
(*str)++; /* advance string pointer after ) */
expr = new_expr(OPERATOR);
expr->op = op;
expr->left = expr1;
expr->right = expr2;
return expr;
}
return NULL;
}
/* free the expression tree */
void free_expr(expr_t *expr)
{
if (expr->left != NULL)
free_expr(expr->left);
if (expr->right != NULL)
free_expr(expr->right);
free(expr);
}
/* print the expression node */
void print_expr(expr_t *expr)
{
switch (expr->type)
{
case OPERATOR:
printf(" %c ", expr->op);
break;
case NUMBER:
printf("%1.2f ", expr->num);
break;
case VARIABLE:
printf("x%d[%1.2f] ", expr->var, expr->num);
break;
}
}
/* print expression tree in preorder */
void print_preorder(expr_t *expr)
{
if (expr == NULL)
return;
print_expr(expr);
print_preorder(expr->left);
print_preorder(expr->right);
}
/* print expression tree in postorder */
void print_postorder(expr_t *expr)
{
if (expr == NULL)
return;
print_postorder(expr->left);
print_postorder(expr->right);
print_expr(expr);
}
int main(int argc, char **argv)
{
expr_t *expr;
char *ptr;
int terminate;
int option;
if (argc != 2)
{
printf("Usage: %s expression\n", argv[0]);
return 0;
}
ptr = argv[1]; /* point to input expression */
expr = parse_expr(&ptr);
if (expr == NULL || *ptr != 0) /* if invalid expression or chars after input */
{
printf("Error: invalid expression\n");
return 1;
}
terminate = 0;
while (!terminate) /* repeat until user selects exit */
{
printf("Please select from the following options:\n");
printf("1. Preorder\n");
printf("2. Postorder\n");
printf("3. Exit\n");
printf("> ");
scanf("%d", &option); /* read option */
switch (option)
{
case 1: /* preorder */
print_preorder(expr);
printf("\n");
break;
case 2: /* postorder */
print_postorder(expr);
printf("\n");
break;
case 3: /* exit */
terminate = 1;
break;
default:
printf("Invalid option\n");
}
}
/* free memory used by the expression tree */
free_expr(expr);
return 0;
}