postfixtobtree.cpp

postfixComputer, Calculate the postfix expression, such as 45+,which means 4+5,and the result is 9.

//将一个后缀表达式转化成二叉树的表示形式
BTreeNode *PostfixToBTree(char a[])
{
	using std::stack;
	stack<BTreeNode *> aStack;
	int i=0;	//设置i来记录a串的当前值的下标
	BTreeNode *pointer;//记录新建立的二叉树当前结点的指针
	while (a[i]!='\0')
	{
		pointer = new BTreeNode(a[i]);//以a[i]为结点值构造二叉树结点
		if (pointer ==NULL)
		{//若指针为空说明没有申请到空间
			cout<<"There is not enough room to create the binary tree!";
			return NULL;
		}
		if(a[i]=='+'||a[i]=='-'||a[i]=='*'||a[i]=='/')
		{
			if(aStack.empty())
			{//若栈空则说明输入的后缀表达式不正确清栈退出
				cout<<"The postfixexpression you input is wrong!";
				return NULL;
			}
			else
			{//若非空则弹栈并设为结点的右孩子
				pointer->right=aStack.top();
				aStack.pop();
			}
			if(aStack.empty())
			{//若栈空则说明输入的后缀表达式不正确清栈退出
				cout<<"The postfixexpression you input is wrong!";
				return NULL;
			}
			else
			{//若非空则弹栈并设为结点的左孩子
				pointer->left=aStack.top();
				aStack.pop();
			}
			aStack.push(pointer);//当前结点压栈
			i++;//指向下一元素
		}
		else
		{
			aStack.push(pointer);//输入为操作数时直接压栈
			i++;//指向下一元素
		}
	}
	reurn pointer;//最后一个结点即为根结点
}