#pragma once
#define _CRT_SECURE_NO_WARNINGS  

using namespace std;

typedef int TElemType; // 树结点数据域类型为整型
typedef double OElemType; // 操作数类型为浮点型

typedef struct BiTNode { // 二叉树的类型定义
	TElemType data;
	struct BiTNode* lchild, * rchild;
} BiTNode, * BiTree;

typedef union {
	char OPTR; // SElemType 可以字符也可以是 二叉树的结点
	BiTree BiT;
} SElemType;

#include"Stack.h"

void ERRORMESSAGE(char* s)//出错信息处理
{
	cout << "---------------------------------------------------" << endl;
	cout << s << endl << endl;

	cout << "PLEASE RESTART THIS PROGRAME IF YOU WANT TO USE THE" << endl << " CALULATOR!" << endl;
	cout << "PROGRAME CLOSING..." << endl;
	cout << "---------------------------------------------------" << endl;
	system("pause");
	exit(1);
}//ERRORMESSAGE

void GetExp(char* Exp)//得到一个表达式,并对其进行单目运算的模式匹配
{
	char ch;
	int n = FALSE, i = 0;
	do
	{
		cin >> ch;
		if (ch == ' ')continue;
		if (i == 0 && (ch == '+' || ch == '-'))Exp[i++] = '0';
		if (n == TRUE && (ch == '-' || ch == '+')) Exp[i++] = '0';
		else n = FALSE;
		Exp[i++] = ch;
		if (ch == '(') n = TRUE;
	} while (ch != '#');
	Exp[i] = '\0';
}//GetExp


Status IN(char ch, char* OP)//判断字符ch 是否属于运算符集
{
	char* p = OP;
	while (*p && ch != *p) ++p;
	if (!*p) return ERROR;
	return OK;
}//IN


void ChangeOPND(char* p, int pos, int& n, OElemType operand[][2])
{
	//把相应的字符串转成对应的运算数,并存入operand数组中,pos是operand中的位序
	//使用 atof 系统函数进行转换.
	char data_real[MAX_OPERAND], data_image[MAX_OPERAND];
	char* q_real = data_real, * q_image = data_image;
	n = 0;
	int m = 0;
	while ((*p <= '9' && *p >= '0') || (*p == '.'))//实部处理
	{
		*q_real++ = *p++;
		n++;
	}
	*q_real = '\0';
	if (strcmp(data_real, "\0") == 0)strcpy(data_real, "0");
	operand[pos][0] = (float)atof(data_real);
	if (*p == '+' || *p == '-')//虚部处理
	{
		m++;
		char ch = *p++;
		while ((*p <= '9' && *p >= '0') || (*p == '.'))
		{
			*q_image++ = *p++;
			m++;
		}
		*q_image = '\0';
		if (*p == 'i')
		{
			if (strcmp(data_image, "\0") == 0)strcpy(data_image, "1");
			operand[pos][1] = (float)atof(data_image);
			m++;
			n += m;
			if (ch == '-')operand[pos][1] = -operand[pos][1];
		}
		else operand[pos][1] = 0;
	}
	else operand[pos][1] = 0;
}//ChangeOPND

void CrtNode(BiTree& T, int position, Stack& PTR)
{
	// 建叶子结点^T, 结点中的数据项为操作数所在的operand数组中的位置
	// 建立完成后把结点装入PTR栈
	SElemType e;
	T = new BiTNode;
	T->data = position;
	T->lchild = T->rchild = NULL;
	e.BiT = T;
	Push(PTR, e);
}//CrtNode

int ChangeOPTR(char ch)
{
	// 把相应的操作符转成宏定义值
	int n = 0;
	if (ch == '+') n = PLUS;
	else if (ch == '-') n = MINUS;
	else if (ch == '*') n = ASTERISK;
	else if (ch == '/') n = SLANT;
	return n;
}//ChangeOPTR

void CrtSubtree(BiTree& T, char ch, Stack& PTR)
{
	// 建子树^T, 其中根结点的数据项为操作符
	SElemType e;
	T = new BiTNode;
	T->data = ChangeOPTR(ch);
	if (Pop(PTR, e)) T->rchild = e.BiT;
	else T->rchild = NULL;
	if (Pop(PTR, e)) T->lchild = e.BiT;
	else T->lchild = NULL;
	e.BiT = T;
	Push(PTR, e);
}//CrtSubtree

Status precede(char c, char ch)
{
	//算符间的优先关系表,此表表示两操作符之间的大于小于关系
	switch (c)
	{
	case '#':
	case '(': return ERROR;
	case '*':
	case '/':
	case '+':
	case '-': if (!(ch != '*' && ch != '/')) return ERROR;
		return OK;
	default: return OK;
	}
}//precede

void CrtExptree(BiTree& t, char* exp, OElemType operand[][2], char* operate)
{
	// 建立由合法的表达式字符串确定的只含二元操作符的
	// 非空表达式树，其存储结构为二叉链表

	SElemType e, c;
	char* p, ch;
	int pos = 0, n;

	Stack S_OPTR, S_BiT; // 栈S_OPTR内放表达式的操作符,栈S_BiT放生成的结点
	InitStack(S_OPTR);
	e.OPTR = '#';
	Push(S_OPTR, e); // 把字符#进栈
	InitStack(S_BiT);

	p = exp; ch = *p; // 指针p指向表达式
	GetTop(S_OPTR, e);
while (!(e.OPTR == '#' && ch == '#')) // 当从栈S_OPTR退出的操作符为#,且ch=='#'时循环结束
	{
		if (!IN(ch, operate)) // 判断ch 是否属于操作符集合operate,
		{
			ChangeOPND(p, pos, n, operand); // 如果不属于操作符,把其转成操作数
			p += (n - 1); // 移动字符串指针
			CrtNode(t, pos++, S_BiT); // 建叶子结点

		}
		else
		{
			switch (ch) // 如果属于操作符
			{
			case '(': e.OPTR = ch;
				Push(S_OPTR, e); // 左括号先进栈
				break;
			case ')': { // 脱括号创建子树
				Pop(S_OPTR, c);
				while (c.OPTR != '(')
				{
					CrtSubtree(t, c.OPTR, S_BiT);
					Pop(S_OPTR, c);
				}
				break;
			}
			default: {
				while (GetTop(S_OPTR, c) && (precede(c.OPTR, ch))) // 栈顶元素优先权高
				{
					CrtSubtree(t, c.OPTR, S_BiT); // 建子树.
					Pop(S_OPTR, c);
				}
				if (ch != '#')
				{
					e.OPTR = ch;
					Push(S_OPTR, e); // 如果ch不为#,让ch进栈
				}
				break;
			} // default
			} // switch
		} // else
		if (ch != '#') { p++; ch = *p; } // 如果ch不为#,p指针后移
		GetTop(S_OPTR, e);
	} // while
	e.BiT = t;
	Pop(S_BiT, e);
} // CrtExptree

OElemType* Value(BiTree T, OElemType operand[][2])
{
	// 递归求值,使用后序遍历,operand数组存放叶子结点的数值
	OElemType lv[2], rv[2], v[2];
	if (!T) return 0;
	if (!T->lchild && !T->rchild) return operand[T->data];
	lv[0] = Value(T->lchild, operand)[0]; lv[1] = Value(T->lchild, operand)[1];
	rv[0] = Value(T->rchild, operand)[0]; rv[1] = Value(T->rchild, operand)[1];
	switch (T->data)
	{
	case PLUS: 
	{
		v[0] = lv[0] + rv[0];
		v[1] = lv[1] + rv[1];
		break;
	}
	case MINUS: 
	{
		v[0] = lv[0] - rv[0];
		v[1] = lv[1] - rv[1];
		break;
	}
	case ASTERISK:
	{	
		v[0] = lv[0] * rv[0] - lv[1] * rv[1];
		v[1] = lv[0] * rv[1] + rv[0] * lv[1];
		break;
	}
	case SLANT: if (rv[0] == 0 && rv[1] == 0)
	{
		char word[] = "ERROR: DIVISOR SHOULD NOT BE ZERO!"; 
		ERRORMESSAGE(word);
	} // 除法运算分母不能为零
			  v[0] = (lv[0] * rv[0] + lv[1] * rv[1]) / (rv[0] * rv[0] + rv[1] * rv[1]);
			  v[1] = (lv[1] * rv[0] - lv[0] * rv[1])/ (rv[0] * rv[0] + rv[1] * rv[1]);
		break;
	}
	return v;
}//Value