#pragma once
#include <iostream>

template <typename T>
struct Node {
	T data;
	Node<T>* next;
};

template <typename T>
class Stack {
private:
	Node<T>* topNode;
	void copy(Node<T>* toCopy);
	void eraseStack();
	void copyStack(Stack const& s);

public:
	Stack();
	Stack(Stack const& s);
	Stack& operator=(Stack const& s);
	~Stack();

	bool empty();
	void push(T const& x);
	T pop();
	T top() const;
};
template <typename T>
inline void Stack<T>::copy(Node<T>* toCopy)
{
	if (toCopy == NULL) return;
	copy(toCopy->next);
	push(toCopy->data);
}

template <typename T>
inline void Stack<T>::eraseStack()
{
	while (!empty()) {
		pop();
	}
}

template <typename T>
inline void Stack<T>::copyStack(Stack const & s)
{
	topNode = NULL;
	copy(s.topNode);
}

template <typename T>
inline Stack<T>::Stack() : topNode(NULL)
{}

template <typename T>
inline Stack<T>::Stack(Stack const & s)
{
	copyStack(s);
}

template <typename T>
inline Stack<T> & Stack<T>::operator=(Stack const & s)
{
	if (this != &s) {
		eraseStack();
		copyStack(s);
	}
	return *this;
}

template <typename T>
inline Stack<T>::~Stack()
{
	eraseStack();
}

template <typename T>
inline bool Stack<T>::empty()
{
	return topNode==NULL;
}

template <typename T>
inline void Stack<T>::push(T const & x)
{
	Node<T>* p = new Node<T>;
	p->data = x;
	p->next = topNode;
	topNode = p;
}

template <typename T>
inline T Stack<T>::pop()
{
	if (empty()) {
		std::cout << "Empty Stack!\n";
		return 0;
	}
	Node<T>* p = topNode;
	topNode = topNode->next;
	T x = p->data;
	delete p;
	return x;
}

template <typename T>
	inline T Stack<T>::top() const
	{
		if (empty()) {
			std::cout << "Empty Stack!\n";
			return 0;
		}
		return topNode->data;
	}


bool isNumber(char a)
{
	return a >= '0' && a <= '9';
}

int parseToInt(char a) {
	return a - '0';
}

int calculate(char* arr) {
	Stack<int> st;
	int num = 0;
	for (int i = 0; arr[i] != '\0'; i++) {
		while(isNumber(arr[i])){
            num*=10;
            num+=parseToInt(arr[i]);
            i++;
		}
		if(arr[i] == ' '){
            st.push(num);
            num = 0;
        }
		if (arr[i] == '+') {
				int x = st.pop();
				int y = st.pop();
				st.push(x + y);
				if(arr[i+1]==' ') i++;
			}
        if (arr[i] == '-') {
            int x = st.pop();
            int y = st.pop();
            st.push(y - x);
            if(arr[i+1]==' ') i++;
        }
        if (arr[i] == '*') {
            int x = st.pop();
            int y = st.pop();
            st.push(x * y);
            if(arr[i+1]==' ') i++;
        }
        if (arr[i] == '/') {
            int x = st.pop();
            int y = st.pop();
            if(arr[i+1]==' ') i++;
            if (x != 0) {
                st.push(y / x);
            }
            else {
                st.push(0);
            }
	}
	return st.pop();
    }
}