I need a C++ program that takes a binary arithmetic expression as input, builds
ID: 669268 • Letter: I
Question
I need a C++ program that takes a binary arithmetic expression as input, builds a binary expression tree for the input and then calculates the value of the input. A binary expression is composed of double type operands, binary arithmetic operators +, -, *, and /, and parentheses ( and ). Your program shall detect whether there are any syntactic errors in the input expression. Once the binary expression tree is built for the input expression that has no syntactic errors, your program shall print prefix and postfix expressions of the input expression. You shall use stack data structures to help build the binary expression tree.
Your program shall read input expressions from a text file.
Use the following examples to test your program:
1. (10.24 + 5.4 * 2.5) / 6.7 + (12.5 * 20.67 + 10) * 25
2. (10.24 + 5.4 * 2.5) / 6.7 + (12.5 * 20.67 + 10) * 25)
3. (10.24 + 5.4 * 2.5) / 6.7 + (12.5 * 20.67 + ) * 25
Note:
Expression 1 has no syntactic errors.
Expressions 2 and 3 have one error each.
Explanation / Answer
working c program
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
using namespace std;
/** class TreeNode **/
class TreeNode
{
public:
char data;
TreeNode *left, *right;
/** constructor **/
TreeNode(char data)
{
this->data = data;
this->left = NULL;
this->right = NULL;
}
};
/** class StackNode **/
class StackNode
{
public:
TreeNode *treeNode;
StackNode *next;
/** constructor **/
StackNode(TreeNode *treeNode)
{
this->treeNode = treeNode;
next = NULL;
}
};
class ExpressionTree
{
private:
StackNode *top;
public:
/** constructor **/
ExpressionTree()
{
top = NULL;
}
/** function to clear tree **/
void clear()
{
top = NULL;
}
/** function to push a node **/
void push(TreeNode *ptr)
{
if (top == NULL)
top = new StackNode(ptr);
else
{
StackNode *nptr = new StackNode(ptr);
nptr->next = top;
top = nptr;
}
}
/** function to pop a node **/
TreeNode *pop()
{
if (top == NULL)
{
cout<<"Underflow"<<endl;
}
else
{
TreeNode *ptr = top->treeNode;
top = top->next;
return ptr;
}
}
/** function to get top node **/
TreeNode *peek()
{
return top->treeNode;
}
/** function to insert character **/
void insert(char val)
{
if (isDigit(val))
{
TreeNode *nptr = new TreeNode(val);
push(nptr);
}
else if (isOperator(val))
{
TreeNode *nptr = new TreeNode(val);
nptr->left = pop();
nptr->right = pop();
push(nptr);
}
else
{
cout<<"Invalid Expression"<<endl;
return;
}
}
/** function to check if digit **/
bool isDigit(char ch)
{
return ch >= '0' && ch <= '9';
}
/** function to check if operator **/
bool isOperator(char ch)
{
return ch == '+' || ch == '-' || ch == '*' || ch == '/';
}
/** function to convert character to digit **/
int toDigit(char ch)
{
return ch - '0';
}
/** function to build tree from input */
void buildTree(string eqn)
{
for (int i = eqn.length() - 1; i >= 0; i--)
insert(eqn[i]);
}
/** function to evaluate tree */
double evaluate()
{
return evaluate(peek());
}
/** function to evaluate tree */
double evaluate(TreeNode *ptr)
{
if (ptr->left == NULL && ptr->right == NULL)
return toDigit(ptr->data);
else
{
double result = 0.0;
double left = evaluate(ptr->left);
double right = evaluate(ptr->right);
char op = ptr->data;
switch (op)
{
case '+':
result = left + right;
break;
case '-':
result = left - right;
break;
case '*':
result = left * right;
break;
case '/':
result = left / right;
break;
default:
result = left + right;
break;
}
return result;
}
}
/** function to get postfix expression */
void postfix()
{
postOrder(peek());
}
/** post order traversal */
void postOrder(TreeNode *ptr)
{
if (ptr != NULL)
{
postOrder(ptr->left);
postOrder(ptr->right);
cout<<ptr->data;
}
}
/** function to get infix expression */
void infix()
{
inOrder(peek());
}
/** in order traversal */
void inOrder(TreeNode *ptr)
{
if (ptr != NULL)
{
inOrder(ptr->left);
cout<<ptr->data;
inOrder(ptr->right);
}
}
/** function to get prefix expression */
void prefix()
{
preOrder(peek());
}
/** pre order traversal */
void preOrder(TreeNode *ptr)
{
if (ptr != NULL)
{
cout<<ptr->data;
preOrder(ptr->left);
preOrder(ptr->right);
}
}
};
/** Main Contains menu **/
int main()
{
string s;
cout<<"Expression Tree Test"<<endl;
ExpressionTree et;
cout<<" Enter equation in Prefix form: ";
cin>>s;
et.buildTree(s);
cout<<" Prefix : ";
et.prefix();
cout<<" Infix : ";
et.infix();
cout<<" Postfix : ";
et.postfix();
cout<<" Evaluated Result : "<<et.evaluate();
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.