// ExpressionTranslation.cpp: 实现文件
//

#include <iostream>
#include "stdafx.h"
#include "ExpressionTranslation.h"

//去除所有空格
void RemoveSomeChar(string& text, char ascii)
{
	text.erase(std::remove(text.begin(), text.end(), ascii), text.end());
}
//截取非逻辑字符串
string GetKeyValueString(const string& str)
{
	int pos = 0;
	while (pos < str.size())
	{
		if ((str[pos] == ':') || (str[pos] >= '0' && str[pos] <= '9') || (str[pos] >= 'a' && str[pos] <= 'z') || (str[pos] >= 'A' && str[pos] <= 'Z'))
			pos++;
		else
			break;
	}
	return string(str.begin(), str.begin() + pos);
}
void SplitKeyValueOprString(const string& str, string& key, string& value, string& opr)
{
	key.clear();
	value.clear();
	opr.clear();
	int pos = 0;
	while (pos < str.size())
	{
		if (key.empty())
		{
			if ((str[pos] == ':') || (str[pos] >= '0' && str[pos] <= '9') || (str[pos] >= 'a' && str[pos] <= 'z') || (str[pos] >= 'A' && str[pos] <= 'Z'))
				pos++;
			else
				break;
		}
	}
	if (key.empty())
	{
		key = string(str.begin(), str.begin() + pos);
	}
	if (opr.empty())
	{
		if (str.compare(pos, 3, OperatorType_Relational_NotBetween) == 0)
		{
			opr = OperatorType_Relational_NotBetween;
		}
		else if (str.compare(pos, 2, OperatorType_Relational_Between) == 0)
		{
			opr = OperatorType_Relational_Between;
		}
		else if (str.compare(pos, 3, OperatorType_Relational_NotIN) == 0)
		{
			opr = OperatorType_Relational_NotIN;
		}
		else if (str.compare(pos, 2, OperatorType_Relational_IN) == 0)
		{
			opr = OperatorType_Relational_IN;
		}
		else if (str.compare(pos, 2, OperatorType_Relational_NotEqual) == 0)
		{
			opr = OperatorType_Relational_NotEqual;
		}
		else if (str.compare(pos, 1, OperatorType_Relational_Equal) == 0)
		{
			opr = OperatorType_Relational_Equal;
		}
		else if (str.compare(pos, 2, OperatorType_Relational_SmallAnd) == 0)
		{
			opr = OperatorType_Relational_SmallAnd;
		}
		else if (str.compare(pos, 1, OperatorType_Relational_Small) == 0)
		{
			opr = OperatorType_Relational_Small;
		}
		else if (str.compare(pos, 2, OperatorType_Relational_BigAnd) == 0)
		{
			opr = OperatorType_Relational_BigAnd;
		}
		else if (str.compare(pos, 1, OperatorType_Relational_Big) == 0)
		{
			opr = OperatorType_Relational_Big;
		}
	}
	if (value.empty())
	{
		if (pos + opr.size() < str.size())
			value = string(str.begin() + pos + opr.size(), str.end());
	}
}

//******************二叉树节点结构**************************
struct TreeNode
{
	TreeNode* m_pLeft{ nullptr };  //左节点
	TreeNode* m_pRight{ nullptr }; //右节点
	string    m_strData;           //[数据名][运算符][逻辑值]
	TreeNode(string val_) :m_strData(val_) {};
	int Show(vector<vector<string>>& strPrint, int dep)
	{
		string branch;//树枝
		int nodeLength = m_strData.size();//果长 
		//规整树枝
		for (int i = 0; i < nodeLength; ++i)
		{
			branch += "─";
		}
		//左遍历
		int leftSize{ 0 };
		if (nullptr != m_pLeft)
		{
			leftSize = m_pLeft->Show(strPrint, dep + 1);
		}
		else
		{
			strPrint.push_back(vector<string>{"", "null"});
			leftSize = strPrint.size() - 1;
		}
		//根节点
		strPrint.push_back(vector<string>{"", m_strData});
		int ret = strPrint.size() - 1;
		//右遍历
		int rightSize{ 0 };
		if (nullptr != m_pRight)
		{
			rightSize = m_pRight->Show(strPrint, dep + 1);
		}
		else
		{
			strPrint.push_back(vector<string>{"", "null"});
			rightSize = strPrint.size() - 1;
		}
		//组装二叉树打印
		int start = strPrint.size();
		for (int i = start; i <= leftSize - 1; ++i)
		{
			strPrint[i][0] = string(nodeLength + 1, ' ') + strPrint[i][0];
		}
		strPrint[leftSize][0] = "└" + branch + strPrint[leftSize][0];
		for (int i = leftSize + 1; i <= rightSize - 1; ++i)
		{
			strPrint[i][0] = "│" + string(nodeLength, ' ') + strPrint[i][0];
		}
		strPrint[ret][0] = "";
		strPrint[rightSize][0] = "┌" + branch + strPrint[rightSize][0];
		for (int i = rightSize + 1; i < strPrint.size(); ++i)
		{
			strPrint[i][0] = string(nodeLength + 1, ' ') + strPrint[i][0];
		}
		return ret;
	}
};

//******************表达式类**************************

CcosExpression::CcosExpression(EN_TreeType treeType)
{
	m_eTreeType = treeType;
	switch (treeType)
	{
		case TT_Number:
		{
			glo_PriorityMap[OperatorType_Logical_EndOfExpression] = 0;
			glo_PriorityMap[OperatorType_Logical_LeftBracket] = 1;
			glo_PriorityMap[OperatorType_Arithmetic_Add] = 2;
			glo_PriorityMap[OperatorType_Arithmetic_Subtract] = 2;
			glo_PriorityMap[OperatorType_Arithmetic_Multiply] = 3;
			glo_PriorityMap[OperatorType_Arithmetic_Divide] = 3;
			glo_PriorityMap[OperatorType_Logical_RightBracket] = 4;
		}break;
		case TT_bool:
		{
			glo_PriorityMap[OperatorType_Logical_EndOfExpression] = 0;
			glo_PriorityMap[OperatorType_Logical_LeftBracket] = 1;
			glo_PriorityMap[OperatorType_Logical_Or] = 2;
			glo_PriorityMap[OperatorType_Logical_And] = 3;
			glo_PriorityMap[OperatorType_Logical_RightBracket] = 4;
		}break;
		default:
		{
			throw std::invalid_argument("Type negative");
		}break;
	}
}
CcosExpression::~CcosExpression()
{
	if (m_pRoot)
	{
		DestroyTree(m_pRoot);
		m_pRoot = nullptr;
	}
}
//设置、获取优先级
int CcosExpression::CheckPriority(char operatorType)
{
	auto iter = glo_PriorityMap.find(operatorType);
	return iter == glo_PriorityMap.end() ? -1 : iter->second;
}
//判断当前栈中是否包含'('操作符
bool CcosExpression::IsLeftSymbol(stack<char> stacks)
{
	while (!stacks.empty())
	{
		if (stacks.top() == OperatorType_Logical_LeftBracket)
			return true;
		stacks.pop();
	}
	return false;
}
//设计一个单元的二叉树（一个父节点，两个子节点）
void CcosExpression::SetRootNode(stack<char>& operatorStacks, vector<string>& dataArray, TreeNode*& curNode)
{
	curNode = new TreeNode(string(1, operatorStacks.top()));
	operatorStacks.pop();
	curNode->m_pLeft = new TreeNode(dataArray[dataArray.size() - 1]);
	dataArray.pop_back();
	curNode->m_pRight = new TreeNode(dataArray[dataArray.size() - 1]);
	dataArray.pop_back();
}
void CcosExpression::SetSingleNode(vector<string>& dataArray, TreeNode*& curNode)
{
	curNode = new TreeNode(dataArray[dataArray.size() - 1]);
}
//在当前节点的右子树最下方重新构建一个单元的二叉树，
//比如:
//     +
//    / \
//   3   5
//如果c='*'，rightNum=8,则
//    +
//   / \
//  3   *
//    /  \
//   5    8
void CcosExpression::SetRightTree(TreeNode* curNode, char operatorType, string rightData)
{
	stack<TreeNode*> stacks;
	while (curNode->m_pRight != nullptr)
	{
		stacks.push(curNode);
		curNode = curNode->m_pRight;
	}
	TreeNode* node = new TreeNode(string(1, operatorType));
	node->m_pLeft = stacks.top()->m_pRight;
	node->m_pRight = new TreeNode(rightData);
	stacks.top()->m_pRight = node;
}
//在当前节点上方重新构建一个单元的二叉树，
//比如：
//    +
//   / \
//  5	6
//如果s = {#,-},dataArray = {6};则
//    -
//   / \
//  +   6
// / \
//5   6
void CcosExpression::SetTopTree(stack<char>& operatorStacks, vector<string>& dataArray, TreeNode*& curNode)
{
	if (!dataArray.empty())
	{
		TreeNode* node = new TreeNode(string(1, operatorStacks.top()));
		operatorStacks.pop();
		node->m_pLeft = curNode;
		node->m_pRight = new TreeNode(dataArray[dataArray.size() - 1]);
		dataArray.pop_back();
		curNode = node;
	}
}
//根据不同的情况（运算符的优先级）构建不同的二叉树单元
void CcosExpression::SetTree(stack<char>& operatorStacks, vector<string>& dataArray, TreeNode*& curNode, bool flag)
{
	if (curNode == nullptr)
	{
		SetRootNode(operatorStacks, dataArray, curNode);
	}
	else if (CheckPriority((curNode->m_strData[0])) < CheckPriority(operatorStacks.top()) && !flag)//如果当前父节点的优先级小于栈顶运算符的优先级
	{
		SetRightTree(curNode, operatorStacks.top(), dataArray[dataArray.size() - 1]);
		operatorStacks.pop();
		dataArray.pop_back();
	}
	else if (CheckPriority((curNode->m_strData[0])) >= CheckPriority(operatorStacks.top()) || flag)//如果当前父节点的优先级大于等于栈顶运算符的优先级
	{
		SetTopTree(operatorStacks, dataArray, curNode);
	}
}
//计算二叉树
double CcosExpression::GetNumberValue(TreeNode* node)
{
	if (glo_PriorityMap.find(node->m_strData[0]) != glo_PriorityMap.end())
	{
		if (node->m_strData[0] == OperatorType_Arithmetic_Add)
			return GetNumberValue(node->m_pLeft) + GetNumberValue(node->m_pRight);
		else if (node->m_strData[0] == OperatorType_Arithmetic_Subtract)
			return GetNumberValue(node->m_pLeft) - GetNumberValue(node->m_pRight);
		else if (node->m_strData[0] == OperatorType_Arithmetic_Multiply)
			return GetNumberValue(node->m_pLeft) * GetNumberValue(node->m_pRight);
		else if (node->m_strData[0] == OperatorType_Arithmetic_Divide)
			return GetNumberValue(node->m_pLeft) / GetNumberValue(node->m_pRight);
	}
	else
		return atof(node->m_strData.c_str());
}
bool CcosExpression::GetBoolValue(TreeNode* node)
{
	if (glo_PriorityMap.find(node->m_strData[0]) != glo_PriorityMap.end())
	{
		if (node->m_strData[0] == OperatorType_Logical_Or)
			return GetBoolValue(node->m_pLeft) || GetBoolValue(node->m_pRight);
		else if (node->m_strData[0] == OperatorType_Logical_And)
			return GetBoolValue(node->m_pLeft) && GetBoolValue(node->m_pRight);
	}
	else
	{
		bool ret{ false };
		if (m_funGetValue)
		{
			ret = m_funGetValue(node->m_strData);
		}
		else
		{
			ret = atoi(node->m_strData.c_str());
		}
		return ret;
	}
}

//=============对外提供接口=============
//设置、获取优先级
void CcosExpression::SetPriorityMap(map<char, int>& Map_type_level)
{
	if (!Map_type_level.empty())
		glo_PriorityMap = Map_type_level;
}
void CcosExpression::GetPriorityMap(map<char, int>& Map_type_level)
{
	Map_type_level = glo_PriorityMap;
}
//构建二叉树，用于计算中缀表达式
bool CcosExpression::CreateTree(string strText, list<string>& nodeValueList)
{
	if (m_pRoot)
	{
		DestroyTree(m_pRoot);
		m_pRoot = nullptr;
	}
	try
	{
		vector<string> dataArray;
		stack<char> operatorStacks;
		operatorStacks.push(OperatorType_Logical_EndOfExpression);
		bool flag = false;
		while (!strText.empty())
		{
			int keyValueLengh = JudgeKeyValue(strText);
			if (keyValueLengh > 0)
			{
				dataArray.push_back(string(strText.begin(), strText.begin() + keyValueLengh));
				nodeValueList.push_back(string(strText.begin(), strText.begin() + keyValueLengh));
				strText.erase(strText.begin(), strText.begin() + keyValueLengh);
			}
			else//此时为运算符（+，-，*，/）或者'('和')'
			{
				if (strText[0] == OperatorType_Logical_RightBracket)//如果为')'符号，则处理当前数据
				{
					strText.erase(strText.begin());//去除')'
					while (operatorStacks.top() != OperatorType_Logical_EndOfExpression)
					{
						if (operatorStacks.top() == OperatorType_Logical_LeftBracket)
						{
							operatorStacks.pop();
							flag = true;
							continue;
						}
						SetTree(operatorStacks, dataArray, m_pRoot, flag);//构建二叉树
					}
					if (CheckPriority(strText[0]) >= CheckPriority(m_pRoot->m_strData[0]))//这个是用于判断比如(3+5)*2和2*(3+5)，即如果括号在右侧，flag为true，此时不需要按照优先级判断。
						flag = true;
					else
						flag = false;
				}
				else if (strText[0] == OperatorType_Logical_LeftBracket)//此时无条件入栈
				{
					operatorStacks.push(strText[0]);
					strText.erase(strText.begin());
				}
				else if (IsLeftSymbol(operatorStacks))//如果栈中有'('符号，则运算符号直接入栈
				{
					operatorStacks.push(strText[0]);
					strText.erase(strText.begin());
				}
				else if (CheckPriority(strText[0]) >= CheckPriority(operatorStacks.top()))//如果当前表达式中的符号优先级大于等于栈顶符号优先级
				{
					//如果此时二叉树中已经有节点，则接着处理
					if (m_pRoot != nullptr && operatorStacks.top() != OperatorType_Logical_EndOfExpression)
						SetTopTree(operatorStacks, dataArray, m_pRoot);
					operatorStacks.push(strText[0]);
					strText.erase(strText.begin());
				}
				else if (CheckPriority(strText[0]) < CheckPriority(operatorStacks.top()))//如果当前表达式中的符号优先级小于栈顶符号优先级
				{
					SetTree(operatorStacks, dataArray, m_pRoot, flag);
					operatorStacks.push(strText[0]);
					strText.erase(strText.begin());
				}
			}
		}

		if (m_pRoot == nullptr)//如果m_pRoot未初始化，同时
		{
			if (operatorStacks.size() == 1)//当前不存在其它符号
			{
				if (dataArray.size() == 1)//dataArray中有一个数字
				{
					SetSingleNode(dataArray, m_pRoot);
				}
			}
			else
			{
				SetRootNode(operatorStacks, dataArray, m_pRoot);
			}
		}
		while (operatorStacks.size() > 1 && !dataArray.empty())//将最后剩余的元素进行处理
		{
			SetTree(operatorStacks, dataArray, m_pRoot, false);
		}
	}
	catch (...)
	{
		//mLog::FERROR("CreateTree[{$}] crash", strText.c_str());
		return false;
	}
	return true;
}
//销毁二叉树
void CcosExpression::DestroyTree(TreeNode* root)
{
	//后序遍历删除根为subTree的子树；
	try {
		if (root != nullptr)
		{
			DestroyTree(root->m_pLeft);    //删除左子树
			DestroyTree(root->m_pRight);   //删除右子树
			delete root; 			       //删除当前结点
			root = nullptr;
		}
	}
	catch (...)
	{
		//mLog::FERROR("DestroyTree crash");
	}
}
//打印二叉树
void CcosExpression::Show(vector<vector<string>>& strPrint)
{
	try {
		if (m_pRoot)
		{
			m_pRoot->Show(strPrint, 0);
		}
	}
	catch (...)
	{
		//mLog::FERROR("Show crash");
	}
}
//截取关键词
int CcosExpression::JudgeKeyValue(const string& data)
{
	int count = 0;
	while (count < data.size())
	{
		if (glo_PriorityMap.find(data[count]) != glo_PriorityMap.end())
			break;
		else
			count++;
	}
	return count;
}