The following code evaluates mathematical expressions and determines whether or not they are balanced.

If balanced, write software to evaluate the balanced expression above assuming x = -2.

In other words, for example, {2x + 5} (6x+4) is a balanced expression.

Therefore,

x= -2

{2(-2) + 5} (6(-2)+4) = -8

For the expression: {2x + 5} (6x+4) Answer: -8

#include

using namespace std;

// ===================================

// Node (class)

// ===================================

template

class Node

{

private:

T data;

Node *next;

public:

// ********************

// Constructor

// ********************

Node()

{

data = new T();

next = nullptr;

}

// *********************

// Loaded Constructor

// *********************

Node(T data)

{

this->data = data;

this->next = nullptr;

}

// *********************

// setData

// *********************

void setData(T data)

{

this->data = data;

}

// *********************

// setNext

// *********************

void setNext(Node *n)

{

next = n;

}

// *********************

// getData

// *********************

T getData()

{

return data;

}

// *********************

// getNext

// *********************

Node *getNext()

{

return next;

}

};

template

class LinkedList

{

private:

Node *head;

public:

// ********************

// Constructor

// ********************

LinkedList()

{

head = nullptr;

}

// ********************

// insertLast

// ********************

void insertLast(T data)

{

Node *node = new Node(data);

if (head == nullptr)

{

head = node;

}

else

{

Node *temp = head;

while (temp->getNext() != nullptr)

{

temp = temp->getNext();

}

temp->setNext(node);

}

}

// ********************

// insertFirst

// ********************

void insertFirst(T data)

{

Node *node = new Node(data);

node->setNext(head);

head = node;

}

// ********************

// popFirst

// ********************

T popFirst()

{

T data = head->getData();

head = head->getNext();

return data;

}

// ********************

// popLast

// ********************

T popLast()

{

Node *temp = head;

if (temp->getNext() == nullptr)

{

T data = head->getData();

head = nullptr;

return data;

}

else

{

while (temp->getNext()->getNext() != nullptr)

{

temp = temp->getNext();

}

T data = temp->getNext()->getData();

temp->setNext(nullptr);

return data;

}

}

// ********************

// getHead

// ********************

Node *getHead()

{

return head;

}

// ********************

// isEmpty

// ********************

bool isEmpty()

{

return head == nullptr;

}

};

template

class Stack

{

private:

LinkedList *last;

public:

// ********************

// Constructor

// ********************

Stack()

{

last = new LinkedList();

}

// ********************

// push

// ********************

void push(T data)

{

last->insertFirst(data);

}

// ********************

// pop

// ********************

T pop()

{

return last->popFirst();

}

// ********************

// top

// ********************

T top()

{

last->getHead();

}

// ********************

// isEmpty

// ********************

bool isEmpty()

{

return last->isEmpty();

}

// ********************

// isEmpty

// ********************

void print()

{

Node *temp = last->getHead();

while (temp != nullptr)

{

cout << temp->getData() << endl;

temp = temp->getNext();

}

}

};

bool parenthesesAlgm(const char array[], int size)

{

// Variable Declaration

char sym;

// Generates a stack

Stack stack;

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

{

if(array[i] == '{' || array[i] == '[' || array[i] == '(')

{

// Pushes item on the stack

stack.push(array[i]);

}

else if(array[i] == '}' || array[i] == ']' || array[i] == ')')

{

if(stack.isEmpty())

{

// Returns false if empty

return false;

}

// Loads the symbol

sym = stack.pop();

if(((array[i] == '}' && sym != '{') ||

(array[i] == ']' && sym != '[') ||

(array[i] == ')' && sym != '(')))

{

return false;

}

}

}

return stack.isEmpty();

}

int main(){

Stackexp;

exp.push("[(5x - 5) - 4x[6x + 2]]"); // Balanced

exp.push("{2x + 5} (6x+4)"); // Balanced

exp.push("(((4x+8)-x[4x+3])))"); // Unbalanced

exp.push("{{8x+5) - 5x[9x+3]})"); // Unbalanced

exp.push("((12x + 6) {2x - 4})"); // Balanaced

exp.push("(2x + 7} (12x + 6)"); // unbalanced

int index = 0;

int size = 6;

string str;

while(index < size)

{

// Loads String

str = exp.pop();

// Tests Balance

if(parenthesesAlgm(str.c_str(), str.size()))

{

cout << str << " is Balanced" << endl;

}

else

{

cout << str << " is not Balanced" << endl;

}

index++;

}

return 0;

}