#include <iostream>
#include <cstring>

template <class T>
class StackElem {
	T data;
	StackElem* next;

public:
	StackElem(T data) : StackElem(data, nullptr) {}
	StackElem(T data, StackElem* se) : data(data), next(se) {}
	~StackElem() = default;
	StackElem(StackElem& other) = delete;
	StackElem& operator=(StackElem& other) = delete;

	const T& get_data() { return this->data; }
	StackElem* get_next() { return this->next; }
	void set_next(StackElem* next) { this->next = next; }
};

template <class T>
class Stack {
	StackElem<T>* topPtr;
	StackElem<T>* startPtr;

public:
	Stack() : topPtr(), startPtr() {}
	Stack(Stack& other) = delete;
	~Stack() {
		StackElem<T>* temp;
		while (startPtr != nullptr) {
			temp = startPtr->get_next();
			delete startPtr;
			startPtr = temp;
		}
	}
	Stack& operator=(Stack& other) = delete;

	void push(T value) {
		if (topPtr == nullptr)
			startPtr = topPtr = new StackElem<T>(value);
		else {
			topPtr->set_next(new StackElem<T>(value));
			topPtr = topPtr->get_next();
		}
	}

	T pop() {
		if (topPtr == nullptr) return T();

		T temp = topPtr->get_data();
		if (startPtr == topPtr) {
			delete topPtr;
			startPtr = topPtr = nullptr;
			return temp;
		}

		StackElem<T>* prevDel = startPtr;
		while (prevDel->get_next() != topPtr)
			prevDel = prevDel->get_next();

		delete topPtr;
		topPtr = prevDel;
		prevDel->set_next(nullptr);
		return temp;
	}

	T top() {
		if (topPtr == nullptr) return T();

		return topPtr->get_data();
	}
};

// Exercise 1

void ex1() {
	const char* str = "thi*s i*s exampl*e";
	unsigned strLen = strlen(str);

	Stack<char> parsedStr;
	for (unsigned i = 0; i < strLen; i++) {
		if (str[i] == '*') parsedStr.pop();
		else parsedStr.push(str[i]);
	}

	while (parsedStr.top() != char())
		std::cout << parsedStr.pop();
	std::cout << std::endl;
}

// Exercise 2

void ex2() {
	const char* str = "()()(())";
	unsigned strLen = strlen(str);

	Stack<char> brackets;
	for (unsigned i = 0; i < strLen; i++) {
		if (str[i] == '(') brackets.push('(');
		else if (str[i] == ')') brackets.pop();
	}

	if (brackets.top() != '(')
		std::cout << "Balanced" << std::endl;
	else
		std::cout << "Unbalanced" << std::endl;
}

// Exercise 3

void ex3() {
	const char* str = "1 2 - 3 + 10 *";

	Stack<int> calc;
	while (*str != '\0') {
		if (*str >= '0' && *str <= '9') {
			calc.push(atoi(str));
			while (*str >= '0' && *str <= '9')
				str++;
		}
		else if (*str == '+')
			calc.push(calc.pop() + calc.pop());
		else if (*str == '-')
			calc.push(calc.pop() - calc.pop());
		else if (*str == '*')
			calc.push(calc.pop() * calc.pop());
		else if (*str == '/')
			calc.push(calc.pop() / calc.pop());
		else if (*str == '%')
			calc.push(calc.pop() % calc.pop());

		str++;
	}

	std::cout << calc.top() << std::endl;
}

int main() {
	ex3();
}