#include <stdio.h>
#include <malloc.h>
#include <string.h>
#define minQueueSize 5
struct Queue{
    int front;
    int rear;
    int size;
    int capacity;
    int *Array;
};
struct nodeD{
    int data;
    struct nodeD* Next;
    struct nodeD* Prev;
};

struct node{
    int data;
    char c;
    struct node* Next;
};
//Function For Queues:
struct Queue* createQueue(int maxElements);
void makeQueueEmpty(struct Queue* Q);
int isEmptyQueue(struct Queue* Q);
int isFull(struct Queue* Q );
void DisposeQueue( struct Queue* Q );
int Succ(int value,struct Queue* Q);
void Enqueue(int X,struct Queue* Q);
void Dequeue(struct Queue* Q);
int Front(struct Queue* Q);
int frontAndDequeue(struct Queue* Q);
void mergeQueues(struct Queue* Q1,struct Queue* Q2); //merge q2 into q1 if it possible
int contains(int X,struct Queue* Q);
int getQueueSize(struct Queue* Q);
void printQueue(struct Queue* Q); // print queue without cross the condition( pointer at the first and at the end only)
struct Queue* attendQueue(struct Queue* Q1,struct Queue* Q2); // return a new queue(Q1+Q2) with delete q1,q2

// Function For Stacks :
int isEmpty(struct node* S);
struct node* createStack( );
void Pop(struct node* S);
void makeStackEmpty( struct node* S );
struct node* Top(struct node* S);
void Push(int X,struct node* S);
void PushChar(char c,struct node* S);
void DisposeStack( struct node* S );
int size(struct node* S);
struct node* reverseStack(struct node* S) ;
void printStack(struct node* S);
void copyStack(struct node* originalStack, struct node* newStack);
int isRight();
int postfixEvaluation();


// Function For Double Linked List :
void insertDouble(int X,struct nodeD* L,struct nodeD* p);
void deleteDouble(int X,struct nodeD* L);

// Function For Single Linked List :

struct node* makeEmpty(struct node* L);
void insert(int X,struct node* L,struct node* P);
void insertFirst(int X,struct node* L);
void insertLast(int X,struct node* L);
struct node* find(int X,struct node* L);
struct node* findPrevious(int X,struct node* L);
int isLast(struct node* P,struct node* L);
void delete(int X,struct node* L);
void deleteFirst(struct node* L);
void deleteLast(struct node* L);
void printList(struct node* L);
int isEmpty(struct node* L);
void deleteList(struct node* L);
int size(struct node* L);
struct node* copyList(struct node* L);
struct node* getNth(int N, struct node* L); // to return The Nth Node ( return a pointer at it)
struct node* getLast(struct node* L); // return the last node
void concatList(struct node * firstList, struct node * secondList);
struct node* findMiddle(struct node* L);
void linkedListToArray(struct node* L,int arr[]);
void arrayToLinkedList(int arr[],struct node* L);
void merge(int arr[], int left, int mid, int right);
void mergeSort(int arr[], int left, int right);
void reverseList(struct node* L);
int main() {
    FILE file;
    printf("%d", postfixEvaluation(&file));


    /*

struct Queue* queue2= createQueue(25);
Enqueue(70,queue2);
Enqueue(80,queue2);
Enqueue(90,queue2);
printQueue(queue2);
struct Queue* q=attendQueue(queue,queue2);
printQueue(q);

/*
printQueue(Q);
Dequeue(Q);
printQueue(Q);
Dequeue(Q);
printQueue(Q);
struct Queue* Q2= createQueue(7);
for(int i=0;i<Q2->capacity;i++){
    Enqueue(i,Q2);
}
printf(" attend\n ");
printQueue(attendQueue(Q,Q2));

// إضافة عناصر إلى القائمة
insert(10, L, L);
insertFirst(222,L);
insert(20, L, L);
insertLast(333,L);
insertLast(143,L);
int arr[size(L)];

linkedListToArray(L,arr);
for(int i=0;i< size(L);i++)
    printf("%d ",arr[i]);
mergeSort(arr,0, size(L)-1);
printf("\n\n\n");
for(int i=0;i< size(L);i++)
    printf("%d ",arr[i]);
printf("\n\n\n");

arrayToLinkedList(arr,L);
printList(L);
// طباعة القائمة 1
printf("List after insertion: ");
printList(L);
printf("\n");
DeleteLast(L);
printf(" list after delete last ");
PrintList(L);
printf("Middle date:%d",FindMiddle(L)->data);
struct node* List2= CopyList(L);
// طباعة القائمة 2

printf("The copied List :");
PrintList(List2);

// العثور على عنصر
struct node* foundNode = Find(13, L);
if (foundNode != NULL) {
    printf("\nNode with data 20 found: %d\n", foundNode->data);
}

// حذف عنصر
Delete(10, L);
printf("\nList after deletion of 33: ");
PrintList(L);
DeleteLast(L);
printf(" list after delete last ");
PrintList(L);
printf("\nMiddle date:%d",FindMiddle(L)->data);

printf("\n");
PrintList(List2);

// حجم القائمة
int size = Size(L);
printf("\nSize of the list: %d\n", size);

// حذف كل العناصر
int size2=Size(List2);
printf("\nSize of the list2: %d\n", size2);

//DeleteList(L);
printf("List after deleting all elements: ");
PrintList(L);
printf("\n");
PrintList(List2);
printf("%d",Size(L));
printf("%d",Size(List2));
printf("\n\n");
ConcatList(L,List2);
PrintList(L   );
*/
    return 0;
}


struct node* makeEmpty(struct node* L){
    if(L!=NULL){
        deleteList(L);
    }
    L=(struct node*)malloc(sizeof (struct node));
    if(L==NULL){
        printf("out of memory");
        return NULL;
    }

    L->Next = NULL;
    return L;
}



int isLast(struct node* P,struct node* L){
    return (P!=NULL && P->Next==NULL);
}


int isEmpty(struct node* L){
    return (L!=NULL && L->Next==NULL);
}


void insert(int X,struct node* L,struct node* P){
    struct node* temp=(struct node*)malloc(sizeof(struct node));
    temp->data=X;
    temp->Next=P->Next;
    P->Next=temp;
}

void insertFirst(int X,struct node* L){

    insert(X,L,L);
}

void insertLast(int X,struct node* L){

    struct node* temp=(struct node*) malloc(sizeof(struct node));

    if(temp==NULL){
        printf("out of memory, InsertLast Function");
        return;
    }

    temp->data=X;
    temp->Next=NULL;

    if(L->Next==NULL) // if the list is empty
        L->Next=temp;

    else{
        struct node* P=L->Next;
        while(P->Next != NULL)
            P=P->Next;
        P->Next=temp;
    }

}


struct node* find(int X,struct node* L){
    struct node* P;
    P=L->Next;
    if(P==NULL){
        printf("Error, P == NULL at Find Function");
        return NULL;
    }
    while(P!=NULL && P->data!=X)
        P= P->Next;
    return P;
}


struct node* findPrevious(int X,struct node* L){
    struct node* P=L;
    if(P==NULL){
        printf("Error, P == NULL at Find Previous Function, the return of the function is : NULL");
        return NULL;
    }
    while(P->Next!=NULL && P->Next->data != X)
        P=P->Next;
    return P;
}


void delete(int X,struct node* L){
    struct node* P= findPrevious(X,L);
    struct node* tempForNodeWant2Free;
    if(!isLast(P,L)){
        tempForNodeWant2Free=P->Next;
        P->Next=P->Next->Next;
        free(tempForNodeWant2Free);
    }
}

void deleteFirst(struct node* L){
    if(L!=NULL && L->Next!=NULL){
        struct node* wantToDelete=L->Next;
        L->Next=wantToDelete->Next;
        free(wantToDelete);
    }
    else
        printf("Empty List , Delete First Function  ");
}
void deleteLast(struct node* L){
    struct node* p=L;
    while(L!=NULL &&p->Next->Next!=NULL){
        p=p->Next;
    }
    struct node* temp=p->Next;
    p->Next=NULL;
    free(temp);
}
void deleteList(struct node* L){
    struct node* temp;
    struct node* P=L->Next;
    L->Next= NULL;

    while(P!=NULL){
        temp=P->Next;
        free(P);
        P=temp;
    }

}


void printList(struct node* L){
    struct node* P=L->Next;
    if(P==NULL){
        printf("Empty List");
    }
    else
        printf("L -> Head-> ");
    while(P!=NULL){
        printf(" [ %d | -]-->",P->data);
        P=P->Next;
    }
    printf(" NULL");
}


int size(struct node* L){
    struct node* P=L->Next;
    int sizeCounter=0;
    while(P!=NULL){
        sizeCounter++;
        P=P->Next;
    }
    return sizeCounter;
}



struct node* copyList(struct node* L) {
    if (L == NULL) {
        return NULL;
    }

    struct node* copyList =NULL;
    copyList= makeEmpty(copyList);;

    struct node* currentOriginal = L->Next;
    struct node* currentCopy = copyList;

    while (currentOriginal != NULL) {
        struct node* newNode = (struct node*)malloc(sizeof(struct node));
        newNode->data = currentOriginal->data;
        newNode->Next = NULL;

        currentCopy->Next = newNode;
        currentCopy = newNode;

        currentOriginal = currentOriginal->Next;
    }

    return copyList;
}
struct node* getNth(int N, struct node* L) {
    struct node* current = L->Next;
    int count = 0;

    while (current != NULL) {
        if (count == N) {
            return current;
        }
        count++;
        current = current->Next;
    }

    return NULL;
}

struct node* getLast(struct node* L) {
    struct node* current = L->Next;

    while (current != NULL && current->Next != NULL) {
        current = current->Next;
    }

    return current;
}

void  concatList(struct node * firstList, struct node * secondList){
    struct node *p = firstList;
    while (p->Next != NULL){
        p = p->Next;            // to arrive to the last node
    }
    p->Next = secondList->Next;

    // second = NULL; if i want to disable the second list after i concated it with first list
}
struct node* findMiddle(struct node* L) {

    int middleIndex=size(L)/2;
    int counter=0;
    struct node* p=L->Next;
    while(p!=NULL){
        if(counter==middleIndex)
            return p;
        p=p->Next;
        counter++;
    }
    return NULL; // if everything work good, we are not arrive to this case.
}
void linkedListToArray(struct node* L,int arr[]){
    int i=0;
    struct node* p=L->Next;
    while(p!=NULL){
        arr[i]=p->data;
        p=p->Next;
        i++;
    }
}
void arrayToLinkedList(int arr[],struct node* L){
    struct node* p=L->Next;
    int i=0;
    while(p!=NULL){
        p->data=arr[i];
        i++;
        p=p->Next;
    }
}
void merge(int arr[], int left, int mid, int right) {
    int i, j, k;
    int n1 = mid - left + 1;
    int n2 = right - mid;

    int leftArr[n1], rightArr[n2];

    for (i = 0; i < n1; i++)
        leftArr[i] = arr[left + i];
    for (j = 0; j < n2; j++)
        rightArr[j] = arr[mid + 1 + j];

    i = 0;
    j = 0;
    k = left;
    while (i < n1 && j < n2) {
        if (leftArr[i] <= rightArr[j]) {
            arr[k] = leftArr[i];
            i++;
        }
        else {
            arr[k] = rightArr[j];
            j++;
        }
        k++;
    }

    while (i < n1) {
        arr[k] = leftArr[i];
        i++;
        k++;
    }

    while (j < n2) {
        arr[k] = rightArr[j];
        j++;
        k++;
    }
}
void mergeSort(int arr[], int left, int right) {
    if (left < right) {
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

void reverseList(struct node* L) {
    struct node* current = L->Next;
    struct node* next = NULL;
    struct node* temp = NULL;

    while (current != NULL) {
        next = current->Next;
        current->Next = temp;
        temp = current;
        current = next;
    }

    L->Next = temp;  // to let the head pointer at the last node which it convert to the first one
}
void insertDouble(int X,struct nodeD* L,struct nodeD* p){
    struct nodeD* temp=(struct nodeD*) malloc(sizeof(struct nodeD));
    temp->data=X;
    temp->Next=p->Next;
    temp->Prev=p;
    p->Next=temp;
    p->Next->Prev=temp;
}
void deleteDouble(int X,struct nodeD* L){
    struct nodeD* temp=L->Next;
    while(temp!=NULL&&temp->data!=X){
        temp=temp->Next;
    }
    temp->Next->Prev=temp->Prev;
    temp->Prev->Next=temp->Next;
    free(temp);
}

///// Stacks Functions :

struct node* createStack( ){
    struct node* S;
    S = (struct node*)malloc( sizeof( struct node ) );
    if( S == NULL )
        printf( "Out of space!" );
    S->Next = NULL;
    makeStackEmpty( S );
    return S;
}

void Pop(struct node* S){
    if(isEmpty(S))
        printf("Empty Stack");
    else{
        struct node* temp=S->Next;
        S->Next=temp->Next;
        free(temp);
    }
}
void makeStackEmpty( struct node* S ){
    if( S == NULL )
        printf( "Out of space!" );
    else
        while( !isEmpty( S ))
            Pop( S );
}

struct node* Top(struct node* S){
    if(!isEmpty(S))
        return S->Next;
    printf("Empty Stack");
    return 0;
}

void Push(int X,struct node* S){
    struct node* temp=(struct node*) malloc(sizeof(struct node));
    if(temp==NULL)
        printf("out of size");
    else{
        temp->data=X;
        temp->Next=S->Next;
        S->Next=temp;
    }
}

void DisposeStack( struct node* S ){
    makeStackEmpty( S );
    free( S );
}


void printStack(struct node* S){
    struct node* temp=createStack();
    while(Top(S)!=NULL){
        printf("%d",Top(S)->data);
        Push(Top(S)->data,temp);
        Pop(S);
    }
    while(Top(temp)!=NULL){
        Push(Top(temp)->data,S);
        Pop(temp);
    }
}
void copyStack(struct node* originalStack, struct node* newStack) {
    struct node* temp = createStack();  // ستاك مؤقت لتخزين العناصر مؤقتًا

    // نخرج العناصر من الستاك الأصلي إلى الستاك المؤقت
    while (Top(originalStack) != NULL) {
        Push(Top(originalStack)->data, temp);  // إضافة العنصر إلى الستاك المؤقت
        Pop(originalStack);  // إزالة العنصر من الستاك الأصلي
    }

    // نعيد العناصر إلى الستاك الأصلي بنفس الترتيب
    while (Top(temp) != NULL) {
        Push(Top(temp)->data, newStack);  // إضافة العنصر إلى الستاك الجديد
        Pop(temp);  // إزالة العنصر من الستاك المؤقت
    }
}

struct node* reverseStack(struct node* S) {
    struct node* temp = createStack();  // إنشاء ستاك مؤقت لتخزين العناصر

    // استخدم دالة مساعدة لإزالة العنصر من الستاك وإضافته إلى الستاك المؤقت
    while (Top(S) != NULL) {
        Push(Top(S)->data, temp);  // إضافة العنصر إلى الستاك المؤقت
        Pop(S);  // إزالة العنصر من الستاك الأصلي
    }
    return temp;
}

int isRight(){
    char line[40]="{test} i donmt know if its work().{";

    FILE* file;
    file =fopen("C:\\\\Users\\\\HP\\\\Desktop\\\\untitled3\\\\tasks.txt","r");
    //fgets(line,sizeof(line),file);

    printf("%s",line);
    struct node* Stack=createStack();
    makeStackEmpty(Stack);
    for(int i=0;i<strlen(line);i++){
        if(line[i]=='(' ||line[i]=='[' ||line[i]=='<'||line[i]=='{' ){
            PushChar(line[i],Stack);
        }
        else if(line[i]==')' ||line[i]==']' ||line[i]=='>'||line[i]=='}'){
            if((isEmpty(Stack))){
                printf("\nError Cause Stack Is Empty at first condition");
                return 0;
            }
            else{
                if( (Top(Stack)->c == '(' && line[i] == ')') ||
                    (Top(Stack)->c =='[' &&   line[i] == ']') ||
                    (Top(Stack)->c == '<' &&  line[i] =='>')  ||
                    (Top(Stack)->c == '{' &&  line[i] =='}') ){
                    Pop(Stack);
                }
                else{
                    printf("Error\n");
                    return -1;
                }
            }
        }
    }
    if(!isEmpty(Stack)){
        return -2;
    }
    return 1;
}

void PushChar(char c,struct node* S){
    struct node* temp=(struct node*) malloc(sizeof(struct node));
    if(temp==NULL)
        printf("out of size");
    else{
        temp->c=c;
        temp->Next=S->Next;
        S->Next=temp;
    }

}
int postfixEvaluation(){
    FILE* file= fopen("C:\\\\Users\\\\HP\\\\Desktop\\\\untitled4\\\\task.txt","r");
    if(file==NULL){
        printf("Error File");
        return 0;
    }
    char postfix[30];
    fgets(postfix,30,file);
    struct node* stack=createStack();
    char* tok= strtok(postfix," ");
    while(tok!=NULL){

        if(tok[0]-'0'>=0 && tok[0]-'0'<=9){ //asci for 0 is 42 , for 1 43 , so if do ( 43-42) i get the value of the number
            Push(atoi(tok),stack);
        }
        else {
            int x2= Top(stack)->data;
            Pop(stack);
            int x1= Top(stack)->data;
            Pop(stack);
            int result;
            if(tok[0]=='/')
                result=x1/x2;
            else if (tok[0]=='-')
                result=x1-x2;
            else if(tok[0]=='*')
                result=x1*x2;
            else
                result=x1+x2;
            Push(result,stack);
        }
        tok= strtok(NULL," ");
    }
    return Top(stack)->data;
}





int isEmptyQueue(struct Queue* Q){
    return Q->size==0;
}

int isFull( struct Queue* Q ){
    return Q->size==Q->capacity;
}

void makeQueueEmpty(struct Queue* Q){
    Q->front=1;
    Q->rear=0;
    Q->size=0;
}

struct Queue* createQueue(int maxElements){
    if(maxElements<minQueueSize){
        printf("Queue Is Too Small . .");
        return NULL;
    }
    struct Queue* Q=(struct Queue*) malloc(sizeof(struct Queue));
    if(Q==NULL){
        printf("Out Of Memory . .");
        return NULL;
    }
    Q->Array=(int *) malloc(sizeof(int)*maxElements );
    if(Q->Array==NULL){
        printf("Out Of Memory . .");
        return NULL;
    }
    Q->capacity=maxElements;
    makeQueueEmpty(Q);
    return Q;
}

void DisposeQueue( struct Queue* Q ){
    if( Q != NULL ){
        free( Q->Array );
        free( Q );
    }
}

int Succ(int value,struct Queue* Q){

    if(++value == Q->capacity)
        value=0;

    return value;
}

void Enqueue(int X,struct Queue* Q){
    if(isFull(Q)){
        printf("Full Queue");
    }
    else{
        (Q->size)++;
        Q->rear=Succ(Q->rear,Q);
        Q->Array[Q->rear]=X;
    }
}
/*
void Succ(struct Queue* Q) {
    if (++(Q->rear) == Q->capacity)
        Q->rear = 0;
}*/

void Dequeue(struct Queue* Q){
    if(isEmptyQueue(Q))
        printf("Empty Queue");
    else{
        Q->size--;
        Q->front= Succ(Q->front,Q);
    }
}
int Front(struct Queue* Q){
    if(!isEmptyQueue(Q))
        return Q->Array[Q->front];
    printf("Empty Queue");
    return -1;
}
int frontAndDequeue(struct Queue* Q){
    int X=0;
    if(isEmptyQueue(Q)){
        printf("Empty Queue");
        return -1;
    }
    else{
        Q->size--;
        X=Q->Array[Q->front];
        Q->front= Succ(Q->front,Q);
    }
    return X;
}

void mergeQueues(struct Queue* Q1,struct Queue* Q2){
    int emptyCells=Q1->capacity - Q1->size;
    if(emptyCells<Q2->size) {
        printf("There is No Enough Empty Cells At First Queue To Merge Process ");
    }
    else{
        while(!isEmptyQueue(Q2)){
            Enqueue(frontAndDequeue(Q2),Q1);
        }
    }
}
int contains(int X,struct Queue* Q){
    int isFound=0;
    struct Queue* temp= createQueue(Q->capacity);
    while(!isEmptyQueue(Q)){
        if(Front(Q)==X)
            isFound=1;
        Enqueue(frontAndDequeue(Q),temp);
    }
    while(!isEmptyQueue(temp))
        Enqueue(frontAndDequeue(temp),Q);
    DisposeQueue(temp);
    return isFound;
}


int getQueueSize(struct Queue* Q){
    return Q->size;
}

void printQueue(struct Queue* Q){
    struct Queue* tempQueue= createQueue(Q->capacity);

    while(!isEmptyQueue(Q)){
        printf("%d ", Front(Q));
        Enqueue(frontAndDequeue(Q),tempQueue);
    }
    printf("\n");
    while (!isEmptyQueue(tempQueue)){
        Enqueue(frontAndDequeue(tempQueue),Q);
    }
    DisposeQueue(tempQueue);
}

struct Queue* attendQueue(struct Queue* Q1,struct Queue* Q2){
    struct Queue* attendQueue= createQueue(Q1->capacity+Q2->capacity);
    if(attendQueue==NULL){
        printf("out of memory");
        return NULL;
    }
    while(!isEmptyQueue(Q1)){
        Enqueue(frontAndDequeue(Q1),attendQueue);
    }
    DisposeQueue(Q1);
    while(!isEmptyQueue(Q2)){
        Enqueue(frontAndDequeue(Q2),attendQueue);
    }
    DisposeQueue(Q2);
    return attendQueue;
}

int infixToPostfix(char infix[]){
    int i=0,j=0;
    char postfix[30];
    struct node* stack=createStack();
    while (infix[i]!='\0'){
        char chr=infix[i];
        switch (chr) {
            case '(':
                PushChar(('('),stack);
                break;
            case ')':
                while(Top(stack)->c!='('){
                    postfix[j++]=Top(stack)->c;
                    Pop(stack);
                }
                break;
            default:
                postfix[j++]=chr;
        }

    }
}