C++ Program to Create Expression Tree from Infix Expression

This is a C++ Program to construct an Expression tree for an Infix Expression. A binary expression tree is a specific application of a binary tree to evaluate certain expressions. Two common types of expressions that a binary expression tree can represent are algebraic[1] and boolean. These trees can represent expressions that contain both unary and binary operators.In general, expression trees are a special kind of binary tree. A binary tree is a tree in which all nodes contain zero, one or two children. This restricted structure simplifies the programmatic processing of Expression trees

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<char> operatorStack;
```
```
 
```

        // operandStack is made up of BinaryOperationNodes and NumericElementNode

        std::stack<ExpressionElementNode *> 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<BinaryOperationNode *> (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

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Here’s the list of Best Books in C++ Programming, Data Structures and Algorithms.

« Prev - C++ Program to Create Expression Tree from Postfix Expression

» Next - C++ Program to Print the Nodes at Odd Levels of a Tree

Related Posts:

Check Computer Science Books
Apply for Computer Science Internship
Check Programming Books
Check Data Structure Books
Practice Design & Analysis of Algorithms MCQ

Recommended Articles: