#include <iostream>
#include <string>
#include <utility>
#include "BinTree.h"
using namespace std;
//Problem 1:
//Create a custom build linked list class to implement a stack and create
//a push, pop, and peek function for the class.
//The Node class for the linked list should have a string variable and a next pointer.
/*
template<typename T>
struct Node {
    T data;
    Node* next = nullptr;
};

template<typename T>
class LinkedList {
private:
    Node<T>* head;
public:
    LinkedList() {
        head = nullptr;
    }



    void pushFIFO(string& data) {
        Node<T>* n = new Node<T>;
        n->data = data;

        if (head == nullptr) {
            head = n;
            return;
        }
        Node<T>* cur = head;
        while (cur->next != nullptr) {
            cur = cur->next;
        }
        cur->next = n;
    }

    void pushLIFO(T data) {
        Node<T>* n = new Node<T>;
        n->data = std::move(data);
        n->next = head;
        head = n;
    }

    T pop() {
        Node<T>* oldHead = head;
        T result = oldHead->data;

        head = oldHead->next;
        delete oldHead;
        return result;
    }

    T peek() {
        if (head == nullptr) {
            T e;
            return e;
        }
        return head->data;
    }
};

//Write a function outside of the linked list and node classes to convert
//postfix expressions into prefix expressions using a stack.
string convert(string expression) {
    LinkedList<string> stack;
    for (char c : expression) {
        if (c >= '0' && c <= '9') {
            string s;
            s += c;
            stack.pushLIFO(s);
        } else {
            string s;
            s.insert(0, stack.pop());
            s.insert(0, stack.pop());
            string a;
            a += c;
            s.insert(0, a);
            stack.pushLIFO(s);
        }
    }
    return stack.pop();
}

double evaluatePrefix(string expression) {
    LinkedList<double> numStack;
    LinkedList<char> opStack;
    for (char c : expression) {
        if (c >= '0' && c <= '9') {
            double num = 1.0 * ((int) c - (int) '0');
            if (numStack.peek()) {
                //operating
                double num0 = numStack.pop();
                char op = opStack.pop();
                double result;
                switch (op) {
                    case '+':
                        result = num0 + num;
                        break;
                    case '-':
                        result = num0 - num;
                        break;
                    case '/':
                        result = num0 / num;
                        break;
                    case '*':
                        result = num0 * num;
                        break;
                    default:
                        cout << "error";
                        break;
                }
                numStack.pushLIFO(result);
            }
        } else {
            opStack.pushLIFO(c);
        }
    }
    return numStack.pop();
}

int main() {
    string prefix = "42$3*3-84/11+/+";
    cout << convert(prefix);
    string exp = "*+-4236";
    cout << endl << evaluatePrefix(exp);


    return 0;
}*/

int main() {

}