# Expression Evaluation

<figure><img src="/files/KKNAp8Pe4IePG1O4WBIy" alt=""><figcaption></figcaption></figure>

## [Repository Link](https://github.com/NafeesMadni/Calculator) <a href="#https-github.com-nafeesmadni-calculator" id="https-github.com-nafeesmadni-calculator"></a>

## <mark style="color:blue;">`File:`</mark>   *<mark style="color:red;">Doubly LL.h</mark>*

{% code overflow="wrap" lineNumbers="true" %}

```cpp
#include <iostream>
#pragma once
using namespace std;

template<typename T>class Node{
public:
    T data;
    Node<T>* next = nullptr;
    Node<T>* prev = nullptr;
    explicit Node(T val): data(val) {};
};

template<typename T>class DoublyLL{
    Node<T> *head = nullptr;
    Node<T> *tail = nullptr;
    int elements = 0;
public:
    
    DoublyLL() {};
    
    DoublyLL(const DoublyLL<T>& list);

    DoublyLL& operator= (const DoublyLL<T>& list);

    void insert(const T val);

    void insertAtHead(const T val);

    bool search(const T val) const;

    bool remove(const T val);

    bool removeHead(T& headData);

    bool isEmpty() { return elements == 0; }
    
    void Swap(DoublyLL& list2);

    template<typename out> friend ostream& operator<< (ostream& cout, const DoublyLL<out>& list);

    ~DoublyLL();
};

template<typename out> ostream& operator<< (ostream& cout, const DoublyLL<out>& list) {
    Node<out>* temp = list.head;
    while (temp != nullptr) {
        cout << temp -> data << " ";
        temp = temp -> next;
    } cout << endl;

    cout << "Head: " << list.head -> data << endl;
    cout << "Tail: " << list.tail -> data << endl;
    cout << "Elemments: " << list.elements << endl;

    return cout;
}

template<typename T> DoublyLL<T> :: DoublyLL(const DoublyLL<T>& list) {  
    elements = list.elements;  

    Node<T>* tempHead = list.head;  
    Node<T>* cur = new Node<T>(tempHead -> data);  
    tempHead = tempHead -> next;  

    head = tail = cur;  
        
    while (tempHead != nullptr) {  
        Node<T>* newNode = new Node<T>(tempHead -> data); 
        tail -> next = newNode;  
        newNode -> prev = tail;  
        tail = newNode;  

        tempHead = tempHead -> next;  
    }
} 

template<typename T> DoublyLL<T>& DoublyLL<T> :: operator= (const DoublyLL<T>& rhs) {  

    if(this == &rhs) return *this; 

    elements = rhs.elements; 
    
    while (head != nullptr) { 
        Node<T>* temp = head; 
        head = head -> next;  
        delete temp; 
    }  
    tail = nullptr;  

    Node<T>* tempHead = rhs.head; 
    Node<T>* cur = new Node<T>(tempHead -> data); 
    tempHead = tempHead -> next;  

    head = tail = cur;  
        
    while (tempHead != nullptr) {  
        Node<T>* newNode = new Node<T>(tempHead -> data);  
        tail -> next = newNode;
        newNode -> prev = tail;
        tail = newNode;

        tempHead = tempHead -> next;
    }
    return *this;
}

template<typename T> void DoublyLL<T> :: insert(const T val){

    if (!elements) insertAtHead(val);
    else{
        Node<T>* newNode = new Node<T>(val);
        tail -> next = newNode;
        newNode -> prev = tail;
        tail = newNode;
        elements++;
    }
}

template<typename T> void DoublyLL<T> :: insertAtHead(const T val){
    Node<T>* newNode = new Node<T>(val);
    if(!elements) head = tail = newNode;
    else{
        newNode -> next = head;
        head -> prev = newNode;
        head = newNode;
    }
    elements++;
}

template<typename T> bool DoublyLL<T> :: search(const T val) const {
    Node<T>* temp = head;

    while (temp != nullptr) {
        if(temp -> data == val) return true;
        temp = temp -> next;
    }
    return false;
}

template<typename T> bool DoublyLL<T> :: remove(const T val) {
    if(elements == 0) return false;

    if(head -> data == val && elements == 1) {
        delete head;
        head = tail = nullptr;
        elements--;
        return true;
    }
    
    if(tail -> data == val) {
        Node<T>* temp = tail;
        tail = tail -> prev;
        tail -> next = nullptr;
        delete temp;
        elements--;
        return true;
    }

    Node<T>* cur = head;
    Node<T>* pre = nullptr;

    while (cur -> next != nullptr) {
        if(cur -> data == val) {
            pre -> next = cur -> next;
            cur -> next -> prev = pre;
            elements--;
            return true;
        }
        pre = cur;
        cur = cur -> next;
    }
    
    return false;
}

template<typename T> bool DoublyLL<T> :: removeHead(T& headData) {
    if(elements == 0) return false;

    headData = head ->data;
    if(elements == 1) {
        delete head;
        head = tail = nullptr;
        elements--;
        return true;
    }
    Node<T>* temp = head;

    head = head -> next;
    head -> prev = nullptr;
    delete temp;
    elements--;
    return true;
}
template<typename T> DoublyLL<T> :: ~DoublyLL() {

    while (head != nullptr) {
        Node<T>* temp = head;
        head = head -> next;
        delete temp;
    }
    tail = nullptr;
}
```

{% endcode %}

## <mark style="color:blue;">`File:`</mark>  *<mark style="color:red;">stack.h</mark>*

{% code lineNumbers="true" %}

```cpp
#include "Doubly LL.h"

template<typename T> class stack {
    DoublyLL<T> list;
public:
    stack(){};
    
    stack(const stack<T>& s2);
    
    stack& operator= (const stack<T>& s2);

    bool isEmpty() { 
        return list.isEmpty();
    }
    void push(const T val);
    bool pop(T& val);
    T top();
    ~stack() {};
};

template<typename T> stack<T> :: stack(const stack<T>& rhs) {
    this -> list = rhs.list;
}

template<typename T> stack<T>& stack<T> :: operator=(const stack<T>& rhs) {
    if(&rhs == this) return *this;
    this -> list = rhs.list;
}

template<typename T> T stack<T> :: top() {
    T temp;
    if(isEmpty()) return temp;
    pop(temp);
    push(temp);
    return temp;
}

template<typename T> void stack<T> :: push(const T val) {
    list.insertAtHead(val);
}

template<typename T> bool stack<T> :: pop(T& val) {
    if(list.isEmpty()) return false;
    
    T temp;
    list.removeHead(temp);
    val = temp;
    return true;
}
```

{% endcode %}

## <mark style="color:blue;">`File:`</mark>   *<mark style="color:red;">main.cpp</mark>*

{% code lineNumbers="true" %}

```cpp
#include "stack.h"

int prec(char c) {
    if(c == '-' || c == '+') return 1;
    if(c == '*' || c == '/') return 2;
    return 0;
}

bool isUnary(int i, string str) {
    return ( i == 0 || i > 0 && !isalnum(str[i-1]) && isalnum(str[i+1]) && str[i-1] != ')');
}

float Evaluation(string str) {
    
    stack<float> s;
    for (int i = 0; i < str.size(); i++) {
        
        if(isalnum(str[i]) || str[i] == '.') {
            string output = "";
            while (isalnum(str[i]) || str[i] == '.') {
                output += str[i++];
            }
            s.push(stof(output));
        }

        else {
            float op1, op2;
            s.pop(op2);
            if(s.isEmpty() || str[i] == '&') {
                s.push(-op2);
                continue;
            }
            s.pop(op1);

            switch (str[i]) {
                case '+': s.push(op1+op2);
                    break; 
                case '-': s.push(op1-op2);
                    break; 
                case '*': s.push(op1*op2);
                    break; 
                case '/':  s.push(op1/op2);
                    break;
            }
        }
    }
    return s.top();
}

string infixToPostfix(string str) {

    string output = "";
    stack<char> s;
    char c;

    for (int i = 0; i < str.length(); i++) {
        if(str[i] == ' ' || str[i] == '+' && str[i+1] != '(' && isalnum(str[i+1]) && !isalnum(str[i-1]) && str[i] != '.') continue;
        output += str[i]; 
    }
    str = output;

    output.clear();

    for (int i = 0; i < str.size(); i++) {
        if(isalnum(str[i])  || str[i] == '.') {
            output += str[i];
            while (isalnum(str[i+1]) && i < str.size()-1  || str[i+1] == '.') {
                output += str[++i];
            } output += '#';
        }
        
        else if(str[i] == '(') s.push(str[i]);   

        else if(str[i] == ')') {
            char temp;
            while(!s.isEmpty() && s.top() != '(') {
                s.pop(temp);
                output += temp;
            } s.pop(temp);
        }

        else if(str[i] == '-' && isUnary(i, str)) {
            while (isalnum(str[i+1]) || str[i+1] == '.') {
                output += str[++i]; 
            }
            output += '#';
            output += '&';
        }       
        else {
            while (!s.isEmpty() && prec(str[i]) <= prec(s.top())) {
                s.pop(c);   
                output += c;
            }
            s.push(str[i]);
        }
    }

    while (!s.isEmpty()) {
        s.pop(c);
        output += c;
    }
    return output;
}

int main() {
    // string s = "((9876 +  5432) * (8765 - 4321) + 25000 / 5000) * (987 - 123) + 15000 / 3 - 8000 * (6000 / 2000)"; // 5.87768e+010 = 58776827048
    string s = "-5.31 + (-2.4) - (+743.13) + (-0.3) + 10.49 - (-401.3) + 643.331";  // 3D


    string temp = infixToPostfix(s);
    cout << temp << endl;
    cout << s << " = " << Evaluation(temp);
}
```

{% endcode %}


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://dsa-cpp.gitbook.io/nafees/project/expression-evaluation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.