Question

(1) (50%) Write a C program 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 xl, 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 xl, x2, x3, ..., which are initially 0.0 and can be updated interactively by the user. For example, expression ((rl +5.12) (r2 7.68))/r3) will be converted into a binary expression tree like: 5.12 x2 7.68 Your program should then show a menu with the following options 1. Display 2. Preorder 3. Inorder 4. Postorder 5. Update 6. Calculate 7. Exit Description: . When option 1 is selected, your program should display the tree in some way so that the tree can be visualized, and also print the name and value of each variable, like "x1:0.0" when x1 initially has value 0.0

Answer 1

#include<stdio.h>

#include<iostream.h>

using namespace std;

#define SIZE 10

// An expression tree node

struct et1

{

char value;

et1* left, *right;

};

typedef struct et1 et;

et stack[SIZE];

int top = -1;

void push(et *data){

if(top == SIZE-1)

printf("\nStack is Full!!! Insertion is not possible!!!");

else{

top++;

stack[top]->value = data->value;

printf("\nInsertion success!!!");

}

}

et* pop(){

if(top == -1)

printf("\nStack is Empty!!! Deletion is not possible!!!");

else{

printf("\nDeleted : %d", stack[top]->value);

top--;

return stack[top+1];

}

}

// A utility function to check if 'c'

// is an operator

bool isOperator(char c)

{

if (c == '+' || c == '-' ||

c == '*' || c == '/' ||

c == '^')

return true;

return false;

}

// Utility function to do inorder traversal

void inorder(et *t)

{

if(t)

{

inorder(t->left);

printf("%c ", t->value);

inorder(t->right);

}

}

// A utility function to create a new node

et* newNode(int v)

{

et *temp = new et;

temp->left = temp->right = NULL;

temp->value = v;

return temp;

};

// Returns root of constructed tree for given

// postfix expression

et* constructTree(char postfix[])

{  

et *t, *t1, *t2;

// Traverse through every character of

// input expression

for (int i=0; i<strlen(postfix); i++)

{

// If operand, simply push into stack

if (!isOperator(postfix[i]))

{

t = newNode(postfix[i]);

push(t);

}

else // operator

{

t = newNode(postfix[i]);

// Pop two top nodes

t1 = pop(); // Store top

// Remove top

t2 = pop();

// make them children

t->right = t1;

t->left = t2;

// Add this subexpression to stack

push(t);

}

}

// only element will be root of expression

// tree

t = pop();

return t;

}

// Driver program to test above

int main()

{

char postfix[] = "ab+ef*g*-";

et* r = constructTree(postfix);

for(int i=0;i<10;i++)

{

et *temp=new stack[i];

stack[i]->value='/n';

stack[i]->left=NULL;

stack[i]->right=NULL;

}

printf("infix expression is \n");

inorder(r);

return 0;

}