Question

Create a Binary Expressions Tree Class and create a menu driven programyour program should be able to read multiple expressions from a file and create expression trees for each expression, one at a timethe expression in the file must be in "math" notation, for example x+y*a/b.display the preorder traversal of a binary tree as a sequence of strings each separated by a tabdisplay the postorder traversal of a binary tree in the same form as aboveWrite a function to display the inorder traversal of a binary tree and place a (before each subtree and a )after each subtree. Don’t display anything for an empty subtree. For example, the expression tree should would be represented as ( (x) + ( ( (y)*(a) )/(b) ) )

Answer 1

Step-by-step explanation:

Program:

#include<iostream>

#include <bits/stdc++.h>

using namespace std;

//check for operator

bool isOperator(char c)

{

switch(c)

{

case '+': case '-': case '/': case '*': case '^':

return true;

}

return false;

}

//Converter class

class Converter

{

private:

string str;

public:

//constructor

Converter(string s):str(s){}

//convert from infix to postfix expression

string toPostFix(string str)

{

stack <char> as;

int i, pre1, pre2;

string result="";

as.push('(');

str = str + ")";

for (i = 0; i < str.size(); i++)

{

char ch = str[i];

if(ch==' ') continue;

if (ch == '(')

as.push(ch);

else if (ch == ')')

{

while (as.size() != 0 && as.top() != '('){

result = result + as.top() + " ";

as.pop();

}

as.pop();

}

else if(isOperator(ch))

{

while (as.size() != 0 && as.top() != '(')

{

pre1 = precedence(ch);

pre2 = precedence(as.top());

if (pre2 >= pre1){

result = result + as.top() + " ";

as.pop();

}

else break;

}

as.push(ch);

}

else

{

result = result + ch;

}

}

while(as.size() != 0 && as.top() != '(') {

result += as.top() + " ";

as.pop();

}

return result;

}

//return the precedence of an operator

int precedence(char ch)

{

int choice = 0;

switch (ch) {

case '+':

choice = 0;

break;

case '-':

choice = 0;

break;

case '*':

choice = 1;

break;

case '/':

choice = 1;

break;

case '^':

choice = 2;

default:

choice = -999;

}

return choice;

}

};

//Node class

class Node

{

public:

string element;

Node *leftChild;

Node *rightChild;

//constructors

Node (string s):element(s),leftChild(nullptr),rightChild(nullptr) {}

Node (string s, Node* l, Node* r):element(s),leftChild(l),rightChild(r) {}

};

//ExpressionTree class

class ExpressionTree

{

public:

//expression tree construction

Node* covert(string postfix)

{

stack <Node*> stk;

Node *t = nullptr;

for(int i=0; i<postfix.size(); i++)

{

if(postfix[i]==' ') continue;

string s(1, postfix[i]);

t = new Node(s);

if(!isOperator(postfix[i]))

{

stk.push(t);

}

else

{

Node *r = nullptr, *l = nullptr;

if(!stk.empty()){

r = stk.top();

stk.pop();

}

if(!stk.empty()){

l = stk.top();

stk.pop();

}

t->leftChild = l;

t->rightChild = r;

stk.push(t);

}

}

return stk.top();

}

//inorder traversal

void infix(Node *root)

{

if(root!=nullptr)

{

cout<< "(";

infix(root->leftChild);

cout<<root->element;

infix(root->rightChild);

cout<<")";

}

}

//postorder traversal

void postfix(Node *root)

{

if(root!=nullptr)

{

postfix(root->leftChild);

postfix(root->rightChild);

cout << root->element << " ";

}

}

//preorder traversal

void prefix(Node *root)

{

if(root!=nullptr)

{

cout<< root->element << " ";

prefix(root->leftChild);

prefix(root->rightChild);

}

}

};

//main method

int main()

{

string infix;

cout<<"Enter the expression: ";

cin >> infix;

Converter conv(infix);

string postfix = conv.toPostFix(infix);

cout<<"Postfix Expression: " << postfix<<endl;

if(postfix == "")

{

cout<<"Invalid expression";

return 1;

}

ExpressionTree etree;

Node *root = etree.covert(postfix);

cout<<"Infix: ";

etree.infix(root);

cout<<endl;

cout<<"Prefix: ";

etree.prefix(root);

cout<<endl;

cout<< "Postfix: ";

etree.postfix(root);

cout<<endl;

return 0;

}