test9.cpp

本人还是初学者

#define STACKINITSIZE 100//存储空间初始分量
#define STACKINCREMENT 10//存储空间分配增量
#include<stdio.h>
#include<stdlib.h>
#include<string.h>

char OP[]={'+','-','*','/','(',')','#'};

typedef struct BiTNode{
	//建立二叉树节点的存储结构
	char data;
	BiTNode *lchild,*rchild;//左右孩子指针
}* BiTree;

typedef struct {
	//建立存储字符的栈结构
	BiTree *base;	         
	BiTree *top;
	int stacksize;
}CharStack;

int InitCharStack(CharStack &S){
	//初始化CharStack
	S.base=(BiTree *)malloc(STACKINITSIZE*sizeof(BiTree));  //分配存储空间	
	if(!S.base)return 0;
	S.top=S.base;
	S.stacksize=STACKINITSIZE;
	return 1;
}

int CharStackEmpty(CharStack S){
	//判断栈是否为空
	if(S.top==S.base)return 1;
	return 0;
}

int Push(CharStack &S,BiTree e){
	//进栈
	if(S.top-S.base>=S.stacksize){
		S.base=(BiTree *)realloc(S.base,(STACKINITSIZE+STACKINCREMENT)*sizeof(BiTree));
		if(!S.base)return 0;
		S.top=S.base+S.stacksize;
		S.stacksize+=STACKINCREMENT;
	}
	*(S.top)=e;
	S.top++;
	return 1;
}

int Pop(CharStack &S,BiTree *e){
	//出栈
	if(S.top==S.base)return 0;	
	S.top--;
    *e=*S.top;
	return 1;
}

BiTree GetTop(CharStack s){
	//获得栈顶元素
	BiTree e;
	if(s.top==s.base)return 0;
	e=*(--s.top);	
	return e;
}

char Precede(char c1,char c2){
	//判断运算符的优先顺序
	switch(c1){
	case '+':
	case '-':
		switch(c2){
		case '+':
		case '-':
		case ')':
		case '#':
			return '>';
			break;
		case '*':
		case '/':
		case '(':
			return '<';
			break;
		default:return '0';
		}
	case '*':
	case '/':
		switch(c2){
		case '+':
		case '-':
		case '*':
		case '/':
		case ')':
		case '#':
			return '>';
			break;
		case '(':
			return '<';
			break;
		default:
			return '0';
			break;
		}
	case '(':
		switch(c2){
		case '+':
		case '-':
		case '*':
		case '/':
		case '(':
			return '<';
			break;
		case ')':
			return '=';
			break;
		default:
			return '0';
		}
	case ')':
		switch(c2){
		case '+':
		case '-':
		case '*':
		case '/':
		case ')':
		case '#':
			return '>';
			break;	;
		default:
			return '0';
		}
	case '#':
		switch(c2){
		case '+':
		case '-':
		case '*':
		case '/':
		case '(':
			return '<';
			break;
		case '#':
			return '=';
			break;
		default:
			return '0';
		}
	default:
			return '0';
	}
}

int In(char c,char p[]){
    //判断输入的是不是运算符
	for(unsigned i=0;i<(strlen(p));i++){
		if(c==p[i])return 1;
	}
	return 0;
}



int EvaluateExpression(BiTree *T){
	//算数表达式求值得算符优先算法。
	CharStack OPTR,OPND;
	InitCharStack(OPTR); 
	InitCharStack(OPND);
	BiTree node[STACKINITSIZE],p,theta,a,b;
	char c=' ';
	int n=0,i=0;	
	if(!(node[n]=(BiTree)malloc(sizeof(BiTree))))return 0;
	node[n]->data='#';
	node[n]->lchild=NULL;
	node[n]->rchild=NULL;//运算符栈底置#
	n++;
	do{// 将输入字符串转化成树节点结构
		c=getchar();
		if(!(node[n]=(BiTree)malloc(sizeof(BiTree))))return 0;
		node[n]->data=c;
		node[n]->lchild=NULL;
		node[n]->rchild=NULL;
		n++;
	}while(c!='#');	
	Push(OPTR,node[i]);
	i++;
	while(node[i]->data!='#'||GetTop(OPTR)->data!='#'){//while		
		if(!In(node[i]->data,OP)){			
			Push(OPND,node[i]);
			i++;
		}//if
		else{			
			switch(Precede(GetTop(OPTR)->data,node[i]->data)){
			case '<'://栈顶元素优先权低
				Push(OPTR,node[i]);//运算符进栈
				i++;
				break;
			case '='://脱括号并接受下一个字符
				Pop(OPTR,&p);
				i++;
				break;
			case '>'://退栈，并将运算结果入栈
				Pop(OPTR,&theta);//取出一个运算符
				Pop(OPND,&b);
				Pop(OPND,&a);//取出两个操作数
				theta->rchild=b;
				theta->lchild=a;
				Push(OPND,theta);//建立子树结构，并把子树根节点进操作数栈
				break;
			default:				
				return 0;
			}//switch
		}//else		
	}//while
	Pop(OPND,T);//取出根节点
	return 1;
}

void visit(BiTree T){
	//按先序序列访问二叉树，并打印出它的先序序列；
	if(T->lchild)visit(T->lchild);//如果左孩子存在，则访问左子树
	if(T)printf("%c",T->data);//输出节点信息
	if(T->rchild)visit(T->rchild);//如果右孩子存在，则访问右子树	
}

int main(){
	BiTree T;	
	printf("请输入原四则表达式,并以#结束:");
	EvaluateExpression(&T);	
	printf("表达式的前缀序列为：");
	visit(T);
	printf("\n");
	system("pause");
	return 0;
}