Expression Evaluation

You can make possible changing

Repository Link

File: Doubly LL.h

#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;
}

File: stack.h

#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;
}

File: main.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);
}