C++ Program to Construct an Expression Tree for an Infix Expression
Posted by Superadmin on December 07 2015 01:48:24

---

Here is source code of the C++ Program to Construct an Expression Tree for an Infix Expression. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

#include <cstdlib>
#include <iostream>
#include <sstream>
#include <string>
#include <stack>
#include <exception>

using namespace std;

class ExpressionElementNode
{
public:
virtual double value() = 0; // Return the value of this node.
};

class NumericElementNode: public ExpressionElementNode
{

private:
double number;
NumericElementNode(const NumericElementNode& n);
NumericElementNode();
NumericElementNode&operator=(const NumericElementNode& n);
public:

NumericElementNode(double val);
virtual double value();
};

inline NumericElementNode::NumericElementNode(double val) :
number(val)
{
}

inline double NumericElementNode::value()
{
return number;
}

class BinaryOperationNode: public ExpressionElementNode
{

private:

char binary_op;

ExpressionElementNode *left;
ExpressionElementNode *right;

BinaryOperationNode(const BinaryOperationNode& n);
BinaryOperationNode();
BinaryOperationNode &operator=(const BinaryOperationNode& n);

public:
BinaryOperationNode(char op, ExpressionElementNode *l,
ExpressionElementNode *r);

virtual double value();
};

inline BinaryOperationNode::BinaryOperationNode(char op,
ExpressionElementNode *l, ExpressionElementNode *r) :
binary_op(op), left(l), right(r)
{
}
double BinaryOperationNode::value()
{
// To get the value, compute the value of the left and
// right operands, and combine them with the operator.
double leftVal = left->value();

double rightVal = right->value();

double result;

switch (binary_op)
{

case '+':
result = leftVal + rightVal;
break;

case '-':
result = leftVal - rightVal;
break;

case '*':
result = leftVal * rightVal;
break;

case '/':
result = leftVal / rightVal;
break;
}

return result;
}
class ExpressionElementNode;
class BinaryOperationNode;

class BinaryExpressionBuilder
{

private:
// holds either (, +, -, /, or *
std::stack operatorStack;

// operandStack is made up of BinaryOperationNodes and NumericElementNode
std::stack operandStack;

void processOperator(char op);
void processRightParenthesis();

void doBinary(char op);

int precedence(char op);

public:

class NotWellFormed: public std::exception
{

public:
virtual const char* what() const throw ()
{
return "The expression is not valid";
}
};

BinaryOperationNode *parse(std::string& istr) throw (NotWellFormed);
};
int BinaryExpressionBuilder::precedence(char op)
{
enum
{
lowest, mid, highest
};

switch (op)
{

case '+':
case '-':
return mid;

case '/':
case '*':
return highest;

default:
return lowest;
}
}

// Input: +, -, /, or *
// creates BinaryOperationNode's from all preceding
BinaryOperationNode *BinaryExpressionBuilder::parse(std::string& str)
throw (NotWellFormed)
{
istringstream istr(str);
char token;

while (istr >> token)
{

switch (token)
{

case '+':
case '-':
case '*':
case '/':
processOperator(token);
break;

case ')':
processRightParenthesis();
break;

case '(':
operatorStack.push(token);
break;

default:
// If it is not an operator, it must be a number.
// Since token is only a char in width, we put it back,
// and get the complete number as a double.
istr.putback(token);
double number;

istr >> number;

NumericElementNode *newNode = new NumericElementNode(number);
operandStack.push(newNode);

continue;
} // end switch
} // end while

while (!operatorStack.empty())
{

doBinary(operatorStack.top());
operatorStack.pop();
}

// Invariant: At this point the operandStack should have only one element
// operandStack.size() == 1
// otherwise, the expression is not well formed.
if (operandStack.size() != 1)
{

throw NotWellFormed();
}

ExpressionElementNode *p = operandStack.top();

return static_cast (p);
}

void BinaryExpressionBuilder::processOperator(char op)
{
// pop operators with higher precedence and create their BinaryOperationNode
int opPrecedence = precedence(op);

while ((!operatorStack.empty()) && (opPrecedence <= precedence(
operatorStack.top())))
{

doBinary(operatorStack.top());
operatorStack.pop();
}

// lastly push the operator passed onto the operatorStack
operatorStack.push(op);
}

void BinaryExpressionBuilder::processRightParenthesis()
{
while (!operatorStack.empty() && operatorStack.top() != '(')
{

doBinary(operatorStack.top());
operatorStack.pop();
}

operatorStack.pop(); // remove '('
}

// Creates a BinaryOperationNode from the top two operands on operandStack
// These top two operands are removed (poped), and the new BinaryOperation
// takes their place on the top of the stack.
void BinaryExpressionBuilder::doBinary(char op)
{
ExpressionElementNode *right = operandStack.top();

operandStack.pop();

ExpressionElementNode *left = operandStack.top();

operandStack.pop();

BinaryOperationNode *p = new BinaryOperationNode(operatorStack.top(), left,
right);

operandStack.push(p);
}
int main(int argc, char** argv)
{

NumericElementNode num1(10);
NumericElementNode num2(20);
BinaryOperationNode n('+', &num1, &num2);

BinaryExpressionBuilder b;

cout << "Enter expression" << endl;

string expression;
getline(cin, expression);

BinaryOperationNode *root = b.parse(expression);

cout << " result = " << root->value();
return 0;
}


Output:

$ g++ ExpressionTreeInfix.cpp
$ a.out

Enter expression
2+3*5
result = 17
------------------
(program exited with code: 0)
Press return to continue