// tinhtoan.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include<string>
#include<vector>
#include<stack>
#include<string.h>
#include <netinet/in.h>
#include<arpa/inet.h>


using namespace std;


bool isNum(string op) {
	if (isdigit(op[0]))
		return 1;
	else if (op[0] == '-' and isdigit(op[1]))
		return 1;
	return 0;
}

float calc(float a, float b, string op) {

	if (op == "*")
		return a * b;
	else if (op == "/")
		return a / b;
	else if (op == "+")
		return a + b;
	else
		return a - b;

}

string calcExpression(vector<string> rev) {
	// Calculate the expression
	stack<float> res;
	for (int i = 0; i < rev.size(); i++) {
		if (isNum(rev[i]))
			res.push(stof(rev[i]));
		else {
			float b = res.top();
			res.pop();
			float a = res.top();
			res.pop();
			float ans = calc(a, b, rev[i]);
			res.push(ans);
		}
	}

	// Convert result to string
	string src = to_string(res.top());

	size_t findPos;
	findPos = src.find(".");

	if ((int)res.top() - res.top() == 0)
		return src.substr(0, findPos);

	return src.substr(0, findPos + 3);
}

int howLarge(string op) {
	//Format size of operators
	if (op == "^")
		return 3;
	if (op == "*" || op == "/")
		return 2;
	if (op == "+" || op == "-")
		return 1;
	return -1;

}

bool isMorePrioty(string ch1, string ch2) {
	if (howLarge(ch1) > howLarge(ch2))
		return 1;
	return 0;
}

vector<string> toRevPolNotation(vector<string> s) {
	// s: Vector contain the Operator and Number

	stack<string> tmp;
	vector<string> rev;

	//Convert infix to posfix
	for (int i = 0; i < s.size(); i++) {
		if (isNum(s[i]))
			rev.push_back(s[i]);
		else {
			if (s[i] == "(")
				tmp.push(s[i]);
			else if (s[i] == ")") {
				while (tmp.top() != "(") {
					rev.push_back(tmp.top());
					tmp.pop();
				}
				tmp.pop();
			}
			else {
				if (tmp.empty() || !isMorePrioty(tmp.top(), s[i]) || tmp.top() == "(") {
					tmp.push(s[i]);
				}
				else {
					rev.push_back(tmp.top());
					tmp.pop();
					if (tmp.empty())
						tmp.push(s[i]);
					else {
						while (isMorePrioty(tmp.top(), s[i]) && tmp.top() != "(") {
							rev.push_back(tmp.top());
							tmp.pop();
							if (tmp.empty())
								break;
						}
						tmp.push(s[i]);
					}
				}
			}
		}
	}

	//Write out all operators that are left from STACK
	while (!tmp.empty()) {
		rev.push_back(tmp.top());
		tmp.pop();
	}

	return rev;

}
void changeBracket(char& x) {
	//Change { [ to (
	if (x == 91 || x == 123) {
		x = 40;
	}
	//Change ] } to )
	if (x == 93 || x == 125) {
		x = 41;
	}
}

void change(string& temp) {
	for (int i = 0;i < temp.length();i++) {
		changeBracket(temp[i]);
	}
}

bool isOperator(string op) {
	if (op == "^" || op == "*" || op == "+" || op == "-" || op == "/")
		return true;
	return false;
}

bool isError(vector<string> op) {
	for (int i = 0; i < op.size() - 1; i++)
	{
		if (op[i].size() == 0)
			return true;
		if (isNum(op[i]) && isNum(op[i + 1]))
			return true;
		if (isOperator(op[i]) && isOperator(op[i + 1]))
			return true;
		if (!isNum(op[i]) && !isOperator(op[i]) && op[i] != "(" && op[i] != ")")
			return true;
	}
	//Check if have a space at the last index of expression
	if (op[op.size() - 1].size() == 0)
		return true;
	return false;
}

vector<string> split(string haystack, string needle) {
	vector<string> result;
	string sub = "";
	size_t startPos = 0;
	size_t findPos;

	//Change every bracket to ( and )
	change(haystack);
	//Split string and push back operands and operators
	while (true) {
		findPos = haystack.find(needle, startPos);
		if (findPos != string::npos) {
			sub = haystack.substr(startPos, findPos - startPos);
			//Handle bracket (
			while (sub[0] == '(') {
				result.push_back("(");
				sub = sub.substr(1);
			}

			//Handle bracket )
			if (sub[sub.length() - 1] == ')') {

				int idx = 1;
				while (sub[sub.length() - idx] == ')') {
					idx++;
				}

				result.push_back(sub.substr(0, sub.length() - idx + 1));

				for (int i = 1; i < idx; i++) {
					result.push_back(")");
				}

				startPos = needle.length() + findPos;
				continue;
			}
			//Add operators and operands
			result.push_back(sub);
			startPos = needle.length() + findPos;
		}
		else {
			//Handle with chain remaining
			sub = haystack.substr(startPos, haystack.length() - startPos);
			if (sub[sub.length() - 1] == ')') {

				int idx = 1;
				while (sub[sub.length() - idx] == ')') {
					idx++;
				}

				result.push_back(sub.substr(0, sub.length() - idx + 1));

				for (int i = 1; i < idx; i++) {
					result.push_back(")");
				}

				break;
			}
			result.push_back(sub);
			break;
		}
	}

	return result;

}

int main()
{
    string inputT;
	char client_mes[256];
	cout << "Nhap bieu thuc tinh: ";
	cin.get( client_mes,256);
	cout <<"t1: " << client_mes << endl;
	inputT += client_mes;
	cout << inputT;
    //getline(cin, inputT, '\n');

	vector<string> temp = split(inputT, " ");

	vector<string> revPolNotation = toRevPolNotation(temp);

	cout << calcExpression(revPolNotation) << endl;

}