tree_exp.cpp

数据结构课程中利用树进行表达式求值方法

#include<stdio.h>
#include<stdlib.h>
#include<process.h>   
#include<conio.h>

#define STACK_INIT_SIZE 100   //存储空间初始分配量
#define	STACKINCREMENT 10   //存储空间分配增量

typedef int ElemType;

typedef struct BiTNode
{
	ElemType data;
	struct BiTNode *lchild,*rchild;
	struct BiTNode *next;
}BiTNode,*BiTree;

typedef struct 
{
	BiTree base;
	BiTree top;
	int stacksize;
}LinkStack;

LinkStack S;
LinkStack PTRS;
char OP[7]={'+','-','*','/','(',')','#'};
char op[4]={'+','-','*','/'};

void wait()    
{
	printf("\n\n按任意键继续\n");
	getch();
}

int StackEmpty(LinkStack &S)
{//判断栈是否为空
	if(S.base == S.top)
		return 1;
	else
		return 0;
}

int InitStack(LinkStack &S)
{//构造一个空栈，初始化
	S.base = S.top = (BiTree)malloc(sizeof(BiTNode));  
	if(!S.base)
		return 0;  //存储分配失败
	S.top->next = NULL;
	return 1;
}

char Push(LinkStack &S, char e)
{//数据压栈
	BiTNode *p;
	p = (BiTNode *)malloc(sizeof(BiTNode));
	p->data = e;  //将传入的数据压栈
	p->next = S.top;
	S.top = p;
	return e;
}

char Pop(LinkStack &S, char &e)
{
	BiTNode *p;
	if(StackEmpty(S))
	{
		return '0';//空栈
	}
	else
	{//当栈非空，
		p = S.top;
		S.top = p->next;
	}
	e = p->data;
	return e;
}

char GetTop(LinkStack &S,char &e)
{
	if(StackEmpty(S))
	{
		return '0';
	}
	else
	{
		e = (S.top)->data;
	}
	return e;
}

BiTNode *Pop(LinkStack &S,BiTNode *p)
{
	if(StackEmpty(S))
	{
		printf("空栈");
		return NULL;
	}
	else
	{//当栈非空
		p = S.top;
		S.top = p->next;
		return p;
	}
}

BiTNode *Push(LinkStack &S, BiTNode *p)
{//数据压栈
	p->next = S.top;
	S.top = p;
	return p;
}

void DestroyStack(LinkStack &S)
{
	BiTNode *p;
	while(!StackEmpty(S))
	{
		p = S.top;
		S.top = p->next;
		free(p);
	}
}

int IN(char c,char *op)//比较字符是否为运算符，是则返回1，否则0
{
        int i=0;
        while(i < 7)
        	if(c == op[i++])
				return 1;
        return 0;
}

int precede[7][7]={//检查运算符排序方法
    1,1,3,3,3,1,1,
    1,1,3,3,3,1,1,
    1,1,1,1,3,1,1,
    1,1,1,1,3,1,1,
    3,3,3,3,3,2,0,
    1,1,1,1,0,1,1,
    3,3,3,3,3,0,2,
};

int Precede(char op,char c)//比较运算符的优先级
{
        int pos_op;
        int pos_c;
        int i;
        for(i=0;i<7;i++)
        {
                if(op==OP[i]) pos_op=i;
                if(c==OP[i]) pos_c=i;
        }
        switch(precede[pos_op][pos_c])
        {
                case 1:return 1;//优先级高
				case 2:return 0;//优先级低
                case 3:return 0;
				default:return 0;
        }
}

//建叶子结点的算法为：
void CrtNode(BiTree T,int ch)
{
	if (!(T = new BiTNode))
		exit(0);//OVERFLOW
	T->data = ch;
	T->lchild = T->rchild = NULL;
	T =	Push(PTRS,T);
}

//建子树的算法为：
void CrtSubtree(BiTree T,char c)
{
	BiTNode *rc,*lc;
	rc = new BiTNode;
	lc = new BiTNode;
	if (!(T= new BiTNode))
		exit(0);//OVERFLOW
	T->data = c;
	rc = Pop(PTRS,rc);
	T->rchild = rc;
	lc = Pop(PTRS,lc);
	T->lchild = lc;
	T = Push(PTRS,T);
}

BiTree CrtExptree(char* exp)
{// 建立由合法的表达式字符串 exp 确定的只含二元运算符的 
 // 非空表达式树，返回其存储结构二叉链表的根结点指针
 	BiTree t;
	t = new BiTNode;
	char *p,ch,c;
	char pc;  //当前字符的后一个字符
	int st = 0;  //暂存要进行转换的数值
 	InitStack(S);
	Push(S,'#'); // S为暂存运算符的栈
	InitStack(PTRS);	// PTRS为暂存子树根指针的栈
	p=exp;  //表达式字符串 
	ch=*p;  //取一个字符 
	if(!(IN(ch,OP)))
	{
		pc = *(p+1);  //当第一个字符非运算符，让pc指向它的下一个字符
	}
	while(!(GetTop(S,c)=='#'&& ch=='#')) //取字符还未结束 
	{
		if(!IN(ch,OP))  //判断取入的是否是运算符 
		{
			if(st == 0)
				st = ch-48; //ASCII->int
			if(!IN(pc,OP))
			{
				st = st*10+(pc-48); //多位数字进行转化
			}
			if(IN(pc,OP))
			{
				CrtNode(t,st);
				st = 0;  //st已建立叶子节点，内容清空
			}
		}
		else
		{//是运算符 
			switch(ch) 
			{
				case'(': ch = Push(S, ch); break; //是左括号，则压入栈 
				case')':
				{
					c = Pop(S,c);  //碰到右括号，将栈内数据弹出 
					while (c!='(')
					{
						CrtSubtree(t,c);
						c = Pop(S,c);
					} // 建子树直至运算符的栈顶为'('
						break;
				}
				default:
				{//非左右括号，取得运算符栈栈顶元素，与取得的字符的优先级进行比较
					while (GetTop(S,c) && (Precede(c,ch))) 
					{
						CrtSubtree(t,c);
						c = Pop(S,c);
						if(GetTop(S,c)=='#'&& ch=='#')
							break;
					}// 建子树直至运算符栈顶运算符的优先数低
					if(ch != '#')//还未到表达式末尾则继续取一个字符压栈 
						ch = Push(S,ch);
					break;
				}// default
			} // switch
		} // else
		if(ch != '#')
		{
			p++;
			ch = *p;
			pc = *(p+1);
		}
	} // while 循环结束，所有字符处理完毕。
	c = Pop(S,c);//运算符栈 
	t = Pop(PTRS,t);//子树根节点栈 
	DestroyStack(S);//销毁栈 
	DestroyStack(PTRS);
	return t;
} // CrtExptree 

void preorder(BiTree &T)
{//先序遍历二叉树的递归算法
	if(T)
	{
		if(T->lchild!=NULL&&T->rchild!=NULL)
			printf("%c",T->data);
		else
			printf("%d",T->data);
		preorder(T->lchild);  //访问左孩子节点
		preorder(T->rchild);  //访问右孩子节点
	}
}

void midorder(BiTree &T)
{//中序遍历二叉树的递归算法
	if(T)
	{
		midorder(T->lchild);  //访问左孩子节点
		if(T->lchild!=NULL&&T->rchild!=NULL)
			printf("%c",T->data);
		else
			printf("%d",T->data);
		midorder(T->rchild);  //访问右孩子节点
	}
}

void postorder(BiTree &T)
{//后序遍历二叉树的递归算法
	if(T)
	{
		postorder(T->lchild);  //访问左孩子节点
		postorder(T->rchild);  //访问右孩子节点
		if(T->lchild!=NULL&&T->rchild!=NULL)
			printf("%c",T->data);
		else
			printf("%d",T->data);
	}
}

int Operate(int a,char P,int b)
{//运算函数，返回运算结果
	switch(P)
	{
		case '+':return a+b;
		case '-':return a-b;
		case '*':return a*b;
		case '/':
		{
			if(b==0)
			{
				printf("\n错误，除数不能为0！\n");
				wait();
				exit(0);
			}
			else
				return a/b;
		}
		default:return 0;
	}
}

int Value(BiTree &t,char tl,char tr)
{//对表达式树进行运算，返回结果
	char P;
	int A,B,V;
	A=tl;
	B=tr;
	P=t->data;
	if(!IN(P,OP))
		return ((int)P);
	if (IN(tl,OP))
		A=Value(t->lchild,t->lchild->lchild->data,t->lchild->rchild->data);
	if (IN(tr,OP))
		B=Value(t->rchild,t->rchild->lchild->data,t->rchild->rchild->data);
	V=Operate(A,P,B);//调用运算函数
	return V;
}

int main()
{
	char exp[100];
	BiTree t;
	int f=0,j,b = 0,i;
	printf("-----------------第三章 利用树进行表达式求值------------------\n");
	printf("\n欢迎使用本软件！\n");
	printf("说明：请先输入一个算数表达式，以'#'为结束符。程序将输出最后计算结果。\n");
	printf("\n请输入一个表达式：");
	scanf("%s",exp);
	if(exp[0] == '#')
		printf("\n表达式为空！\n");
	else
	{	
		for(i = 0;exp[i]!='\0';i++)
		{
			if(exp[i]=='(')
				b++;
			if(exp[i]==')')
				b--;
		}
		for(i = 0;exp[i]!='\0';i++)
		{
			if(exp[i]=='#')
			{
				f = 1;
				j = i;
				break;
			}
		}
		if(f==1)
		{
			if(IN(exp[j-1],op))
				f=0;
		}
		for(i = 0;exp[i]!='\0';i++)
		{
			if(IN(exp[0],op)||(IN(exp[i],op)&&IN(exp[i+1],op)))
			{
				f = 0;
				break;
			}
		}
	
		if(f == 0||b != 0)
			printf("\n表达式输入错误！\n");
		else
		{
			t = CrtExptree(exp);
			printf("\n前缀表达式：");
			preorder(t); 
			printf("\n\n中缀表达式：");
			midorder(t); 
			printf("\n\n后缀表达式：");
			postorder(t);
			printf("\n");
			if(t->lchild!=NULL&&t->rchild!=NULL)
			{
				printf("\n表达式的值为：%d\n",Value(t,t->lchild->data,t->rchild->data));
			}
			else
				printf("\n表达式的值为：%d\n",t->data);
		}
	}
	wait();
	return 0;
}