expression.cpp

对输入的前缀

#include <windows.h>
#include <iostream.h>
#include <conio.h>
#include <math.h>
#define MAXSTR     50

typedef struct BiNode{                    //二叉树结点
	unsigned char data;
	int status;                           //1变量2常量3运算符
	struct BiNode *lchild,*rchild;
}BiNode, *BiTree;

void ClearBT(BiTree &T){
	delete (T);
}

//作为输入的数组str因为要常常跟随函数而改变值，且几乎每一个函数都
//与之有关所以做成全局变量比较方便。

//全局变量
unsigned char str[MAXSTR];
int result;                               //表达式结果
int overflow;                            //溢出判定 1溢出 0没有
unsigned char v[MAXSTR/2];               //需要赋值的变量

void  Interpret(){
	cout<<endl;
	cout<<"--------------------表达式类型的实现--------------------"<<endl;
	cout<<endl;
	cout<<"                                              2003 计算机4 "<<endl;
	cout<<"                                                李建龙  15 "<<endl;
	cout<<endl;
	cout<<"  说  明 :用二叉树作为表达式的存储结构。"<<endl;
	cout<<"          因为数据在不同类型下转化的缘故,输出的表达式的最"<<endl; 
	cout<<"          大值只能到464=512-48。"<<endl;
	cout<<endl;
	cout<<" 数据输入:用户需要输入的数据有2个:1.语法正确的前缀表示式"<<endl;
	cout<<"                                  2.变量值"<<endl;
	cout<<endl;
	cout<<"  提  示 :1.请注意输入的数据范围变量(a~z)，常量(0~9)，运"<<endl;
	cout<<"            算符'+,-,*,/,^'"<<endl;
	cout<<"          2.若要退出请在输入表达式菜单时按Q/q"<<endl;
	cout<<endl;
	cout<<"-----------------------------------------------------------"<<endl;
	cout<<endl;
	cout<<"                  欢迎使用!"<<endl;
    cout<<endl;
}

void CreateBT(BiTree &T,int& i){             //以先序方式读入表达式并用二叉树
	T=new(BiNode);                           //作为存储方式。
	if (str[i]=='\0') return;
	else if (str[i]>='0'&&str[i]<='9') {
		T->data=str[i];
		T->status=2;                        //标记为常量
		T->lchild=T->rchild=NULL;
		return;
		}//else if
		else if (str[i]=='+'||str[i]=='-'||str[i]=='*'||str[i]=='/'||str[i]=='^'){
			T->data=str[i];
			T->status=3;                          //标记为运算符
			i++;
			CreateBT(T->lchild,i);
			i++;
			CreateBT(T->rchild,i);
		}//else if
}

void trans(){                                    //为str里面的变量赋值
	unsigned char c;
	int k=0;
	for (int i=0;str[i]!='\0';i++)               //遍查str找变量
		if (str[i]>='a'&&str[i]<='z'){           //是变量
			k++;
			v[k]=str[i];                          
			for (int j=1;j<k;j++)                //与前面的变量比较	
				if (v[k]==v[j]) {
					v[k]='\0';					 //相同便删除
					k--;
				}//if
		}//if
	cout<<"     共有变量"<<k<<"个"<<endl;
	for (int n=1;n<=k;n++){
		cout<<"   第"<<n<<"个变量为"<<v[n]<<endl;
		cout<<"   赋值为:";
		cin>>c;
		cout<<endl;
		for (i=0;str[i]!='\0';i++)
			if (v[n]==str[i]) str[i]=c;
	}//for
}


char precedence(char oa,char ob){     //参照书P53页制作的优先权比较函数 多一个乘幂运算  
	switch(oa){                       //若oa<ob即oa的优先权低于ob
	     case'+':switch(ob){ 
		         case'+':return'>';
				 case'-':return'>';
				 case'*':return'<';
				 case'/':return'<';
				 case'^':return'<';
				 case'(':return'<';
				 case')':return'>';
				 case'#':return'>';
				 }
				 break;        
	     case'-':switch(ob){
			     case'+':return'>';
				 case'-':return'>';
				 case'*':return'<';
				 case'/':return'<';
				 case'^':return'<';
				 case'(':return'<';
				 case')':return'>';
				 case'#':return'>';
				 }
				 break;
	     case'*':switch(ob){
			     case'+':return'>';
				 case'-':return'>';
				 case'*':return'>';
				 case'/':return'>';
				 case'^':return'<';
				 case'(':return'<';
				 case')':return'>';
				 case'#':return'>';
				 }
				 break;
       	 case'/':switch(ob){
			     case'+':return'>';
				 case'-':return'>';
				 case'*':return'>';
				 case'/':return'>';
				 case'^':return'<';
				 case'(':return'<';
				 case')':return'>';
				 case'#':return'>';
				 }
				 break;
	     case'^':switch(ob){ 
		         case'+':return'>';
				 case'-':return'>';
				 case'*':return'>';
				 case'/':return'>';
				 case'^':return'>';
				 case'(':return'<';
				 case')':return'>';
				 case'#':return'>';
				 }
				 break;
	     case'(':switch(ob){
			     case'+':return'<';
				 case'-':return'<';
				 case'*':return'<';
				 case'/':return'<';
				 case'^':return'<';
				 case'(':return'<';
				 case')':return'=';
				 case'#':return' ';
				 }
				 break;
	     case')':switch(ob){
			     case'+':return'>';
				 case'-':return'>';
				 case'*':return'>';
				 case'/':return'>';
				 case'^':return'>';
				 case'(':return' ';
				 case')':return'>';
				 case'#':return'>';
				 }
				 break;
	     case'#':switch(ob){
			     case'+':return'<';
				 case'-':return'<';
				 case'*':return'<';
				 case'/':return'<';
				 case'^':return'<';
				 case'(':return'<';
				 case')':return' ';
				 case'#':return'=';
				 }		
	}//switch
}//precedence

void Out_Expression(BiTree T,int& len){               //以中序输出表达式并适当的加上括号
	if (str[0]&&str[1]=='\0') return; 
	char temp;
	if (!T) return;                                    //判空
	if(T->lchild){                                     //左子树
		if (T->lchild->status!=3) str[len++]=T->lchild->data;
		else {
			temp=precedence(T->lchild->data,T->data);
			switch(temp){
					case '<': 
							str[len++]='(';
							Out_Expression(T->lchild,len);
							str[len++]=')';
							break;
					case '=': 
					case '>':
							Out_Expression(T->lchild,len);
							break;
				 }//switch
			}//else
	}//if                                                
	str[len++]=T->data;                                 //自己
	if(T->rchild){                                      //右子树
		if (T->rchild->status!=3) str[len++]=T->rchild->data;
		else{
			temp=precedence(T->rchild->data,T->data);
			switch(temp){
					case '>':
							Out_Expression(T->rchild,len);
							break;
					case '=': 
					case '<':
							str[len++]='(';
							Out_Expression(T->rchild,len);
							str[len++]=')';
							break;
				}//switch
			}//else
   }//if                                               
}//Out_Expression


void Compute(BiTree &T){                        //计算表达式的值
	if (!T) return;
	int a,b,an;
	if (T->lchild&&T->lchild->status==3)         //向运算符孩子前进
		Compute(T->lchild);
	if (T->rchild&&T->rchild->status==3)
		Compute(T->rchild);
	if (T->lchild&&T->rchild&&T->lchild->status==2&&T->rchild->status==2){
		a=T->lchild->data-'0';
		b=T->rchild->data-'0';
//		cout<<a<<b;                              //测试用输出
		switch(T->data){
			case '+':	an=a+b;
						break;
			case '-':	an=a-b;
						break;	
			case '*':	an=a*b;
						break;
			case '/':	an=a/b;
						break;
			case '^':	an=(int)pow(a,b);
		}//switch
	T->data=an+'0';
	T->status=2;
//	cout<<an;                                    //测试用输出
	if (an+48>255) overflow=1;
//	cout<<T->data<<endl;                       //测试用输出
	}//if
}

void main(){
	BiTree T;
	Interpret();
	while (str[0]!='q'){
		cout<<"   请输入表达式:";
		cin>>str;
		cout<<endl;
		if (str[0]=='Q'||str[0]=='q')
			cout<<"           谢谢使用！"<<endl;
		else {
			int i=0,j=0;
			overflow=0;
			trans();
			CreateBT(T,i);
			Out_Expression(T,j);
			cout<<"   中序表达式为:";
			cout<<str;
			cout<<endl<<endl;
			Compute(T);
			result=T->data-'0';
//			cout<<result;                           //测试用输出
			if (overflow) result=256+result;
			cout<<"   表达式结果为:"<<result<<endl;
			cout<<"   -----------------------------------------------------------"<<endl<<endl;
			ClearBT(T);
		}//else
	}//while
}