#include<iostream>
#include<string>
using namespace std;
typedef string ItemType;
struct NodeType;
class StackType
{
public:
	StackType();
	~StackType();
	void push(ItemType newItem);
	void pop();
	ItemType Top();
	bool IsFull() const;
	bool IsEmpty() const;

private:
	NodeType* topPtr;
};
struct NodeType{
	ItemType info;
	NodeType* next;
};
StackType::StackType()
{
	topPtr = NULL;
}
StackType::~StackType()
{
	NodeType* tempPtr;
	while (topPtr != NULL)
	{
		tempPtr = topPtr;
		topPtr = topPtr->next;
		delete tempPtr;
	}
}
void StackType::push(ItemType newItem)
{
	if (IsFull())
		cout << "Error : the Stack is Full" << endl;
	else
	{
		NodeType*  location;
		location = new  NodeType;
		location->info = newItem;
		location->next = topPtr;
		topPtr = location;
	
	}
}
void StackType::pop()
{
	if (IsEmpty())
	{
		cout << "Error : The Stack Is Empty" << endl;
	}
	else
	{
		NodeType* tempPtr;
		tempPtr = topPtr;
		topPtr = topPtr->next;
		delete tempPtr;
	}
}
ItemType StackType::Top()
{
	if (IsEmpty())
		cout << "Error : The Stack Is Empty 표시할 것 이없습니다." << endl;
	else
		return topPtr->info;
}
bool StackType::IsEmpty() const{
	if (topPtr == NULL)
		return true;
	else
		return false;
}
bool StackType::IsFull() const
{
	NodeType* location;
	try
	{
		location = new NodeType;
		delete location;
		return false;
	}
	catch (std::bad_alloc exception)
	{
		return true;
	}
}
int main()
{
	StackType Postfix;
	ItemType input;
	cout << "Input Postfix 수식: ";
 	getline(cin, input);
	int i;
	int c = 0;
	int input_digit=0;// 숫자가 몇번 들어왔는지 알려주는 정수<전부쪼갬>
	int result_num = 0; // 스택에 쪼개져서 들어간 수를 다시 정수형으로 맞추기 위한 수
	int result = 0; // 연산을 위한 result
	
	for (i = 0; i != input.length(); i++)
	{
		if (input[i] == ' ') // 공백을 느낌!<저장 X>
		{
			
				ItemType Top = Postfix.Top(); // 전에 저장한 수를 꺼내옴
				if (isdigit(Top[0]) || Top[0] == '_') //전의 저장한 수가 숫자이거나, 단항연산자 이면
				{
					if (Top[0] == '_')  //단항연산자일경우
					{
					}
					else{
						ItemType nexttop;
						do{
							;//승수를 위한 정수
							result_num = result_num + ((atoi(Top.substr(0, Top.length()).c_str()) - 48)* pow(10, c));
							c++;
							Postfix.pop();
							if (Postfix.IsEmpty())
							{
								break;
							}
							nexttop = Postfix.Top();
						} while (!Postfix.IsEmpty() && isdigit(nexttop[0]) && result_num<10); // 입력받은수에대해 10이상의 수 계산
						Postfix.push(to_string(result_num));//최종결과 스택에 push
						c = 0; // 재 초기화
						result_num = 0; // 다시 0으로 만들어줌
					}
				}
		}
		else if (isdigit(input[i]))
		{
			Postfix.push(to_string(input[i]));
			input_digit++;
		}
		else if (input[i] == '*')
		{
			if (Postfix.Top() == "0")
			{
				Postfix.pop();
			}
			ItemType opr1 = Postfix.Top();
			Postfix.pop();
			ItemType opr2 = Postfix.Top();
			Postfix.pop();
			int opr1_ = atoi(opr1.substr(0, opr1.length()).c_str());
			int opr2_ = atoi(opr2.substr(0, opr2.length()).c_str());
			result = opr1_ * opr2_;
			Postfix.push(to_string(result));
			Postfix.push(" ");// 다음 공백을 입력받을때 만약 스택에 숫자가 존재하면 그 다다음수도
			// 연속된 수를 묶어주려는  경향이 있기때문에 그것을 방지
		}
		else if (input[i] == '+')
		{
			if (Postfix.Top() == "0")
			{
				Postfix.pop();
			}
			ItemType opr1 = Postfix.Top();
			Postfix.pop();
			ItemType opr2 = Postfix.Top();
			Postfix.pop();
			int opr1_ = atoi(opr1.substr(0, opr1.length()).c_str());
			int opr2_ = atoi(opr2.substr(0, opr2.length()).c_str());
			result = opr1_ + opr2_;
			Postfix.push(to_string(result));
			Postfix.push(" ");

		}
		else if (input[i] == '-')
		{
			if (Postfix.Top() == "0")
			{
				Postfix.pop();
			}
			ItemType opr1 = Postfix.Top();
			Postfix.pop();
			ItemType opr2 = Postfix.Top();
			Postfix.pop();
			int opr1_ = atoi(opr1.substr(0, opr1.length()).c_str());
			int opr2_ = atoi(opr2.substr(0, opr2.length()).c_str());
			result = opr1_ - opr2_;
			Postfix.push(to_string(result));
			Postfix.push(" ");
		}
		else if (input[i] == '/')
		{
			if (Postfix.Top() == "0")
			{
				Postfix.pop();
			}
			ItemType opr1 = Postfix.Top();
			Postfix.pop();
			ItemType opr2 = Postfix.Top();
			Postfix.pop();
			int opr1_ = atoi(opr1.substr(0, opr1.length()).c_str());
			int opr2_ = atoi(opr2.substr(0, opr2.length()).c_str());
			result = opr1_ / opr2_;
			Postfix.push(to_string(result));
			Postfix.push(" ");
		}
		else if (input[i] == '%')
		{
			if (Postfix.Top() == "0")
			{
				Postfix.pop();
			}
			ItemType opr1 = Postfix.Top();
			Postfix.pop();
			ItemType opr2 = Postfix.Top();
			Postfix.pop();
			int opr1_ = atoi(opr1.substr(0, opr1.length()).c_str());
			int opr2_ = atoi(opr2.substr(0, opr2.length()).c_str());
			result = opr1_ * opr2_;
			Postfix.push(to_string(result));
			Postfix.push(" ");
		}
		else if (input[i] == '_')
		{
			ItemType pre_num = Postfix.Top();
			Postfix.pop();
			int opr1_ = atoi(pre_num.substr(0, pre_num.length()).c_str());
			result = opr1_ * -1;
			Postfix.push(to_string(result));

		}
	}
	if (Postfix.Top() == " ")
	{
		Postfix.pop();
	}
	cout << Postfix.Top() << endl;
	Postfix.~StackType();
	
return 0;
}