算术表达式求值wancheng.cpp

这是我的数据结构课程设计

//算术表达式求值

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<conio.h>
#include<iostream.h>
#include<fstream.h>

#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10
#define MAXSIZE     100
typedef struct{
	float *base;
	float *top;
	float *move;
	int stacksize;
}sqstack1;
typedef struct{
	char *base;
	char *top;
	char *move;
	int stacksize;
}sqstack2;
sqstack1  OPND;//运算数栈
sqstack2   OPTR;//运算符栈；
char str[255];

/*-----------------本程序的主要函数--------------//

void  menu();
int initstack1(sqstack1 &sq);
int initstack2(sqstack2 &sq);
float gettop1(sqstack1 sq);
char  gettop2(sqstack2 sq);
int push1(sqstack1 &sq);
int push2(sqstack2 &sq);
float pop1(sqstack1&sq);
char  pop2(sqstack2&sq);
void showmove(sqstack1 sq1,sqstack sq2,int count);
void destroysqstack(sqstack1&sq1,sqstack2&sq2);
void instring(char*prompt,char*s,int count);
int in(char c);
float operate(float a,char b,float c);
char precede(char a,char b);
float checknum(char *s1,int *s2);
evaluateexpression();*/

int initstack1(sqstack1 &s){
	s.base=(float*)malloc(STACK_INIT_SIZE*sizeof(float));
	if(!s.base ) exit(0);
	s.top =s.base ;
	s.move =s.base ;
	s.stacksize =STACK_INIT_SIZE;
	return 1;
}
int initstack2(sqstack2 &s){
	s.base =(char*)malloc(STACK_INIT_SIZE*sizeof(char));
	if(!s.base ) exit(0);
	s.top =s.base ;
	s.move =s.base ;
	s.stacksize =STACK_INIT_SIZE;
	return 1;
}
float gettop1(sqstack1 s){
	float e;
	if(s.top ==s.base )  return 0;
	e=*(s.top -1);
	return e;
}
char gettop2(sqstack2 s){
	char e;
	if(s.top ==s.base )  return 0;
	e=*(s.top -1);
	return e;
}

int  push1(sqstack1 &s,float e){
	if(s.top -s.base >=s.stacksize ){
		s.base =(float*)realloc(s.base ,
			(s.stacksize +STACKINCREMENT)*sizeof(float));
		if(!s.base ) exit(0);
	      s.top =s.base +s.stacksize ;
		  s.stacksize +=STACKINCREMENT;
		  }
	*s.top ++=e;
	return 1;

}
int  push2(sqstack2 &s,char e){
	if(s.top -s.base >=s.stacksize ){
		s.base =(char*)realloc(s.base ,
			(s.stacksize +STACKINCREMENT)*sizeof(char));
		if(!s.base ) exit(0);
	      s.top =s.base +s.stacksize ;
		  s.stacksize +=STACKINCREMENT;
		  }
	*s.top ++=e;
	return 1;

}

int  pop1(sqstack1&s,float&e){
	if(s.top ==s.base )  return 0;
	e=*--s.top ;
	return 1;
}
int  pop2(sqstack2&s,char&e){
	if(s.top ==s.base )  return 0;
	e=*--s.top ;
	return 1;
}


int in(char c){
	if(c=='+'||c=='-'||c=='*'||c=='/'||c=='('||c==')'||c=='#'||c=='.') return 1;
     else return 0;
}
float operate(float a,char b,float c){
	float  d=a;
	switch(b){
	case'+':  
		d=a+c;
		break;
	case'-':
		d=a-c;
		break;
	case'*':
		d=a*c;
		break;
	case'/':
		d=a/c;
		break;
	}
	return d;
}
char precede(char a,char b){
	int i,j;
	char com[8][8]={
' ','+','-','*','/','(',')','#',
'+','>','>','<','<','<','>','>',
'-','>','>','<','<','<','>','>',
'*','>','>','>','>','<','>','>',
'/','>','>','>','>','<','>','>',
'(','<','<','<','<','<','=',' ',
')','>','>','>','>',' ','>','>',
'#','<','<','<','<','<',' ','=',
	};
	for(i=0;i<8;i++)
		if(com[i][0]==a)break;
	for(j=0;j<8;j++)
		if(com[0][j]==b) break;
		return com[i][j];
}

float checknum(char *s,int &j){//j开始时引用i 的位置和后面纪录改变后i的位置
	int i=j;
	float num=0.0;
	float occur=0.1;
	for(;!in(s[i]);i++){
		num=10*num+s[i]-'0';
	    if(s[i]=='.') break;
	}
	if(s[i]=='.'){
		i++;
		for(;!in(s[i]);i++){
			if(s[i]=='.'){
				cout<<"\n此数中有两个小数点。输入错误！";
					exit(0);
			}
			num=num+(s[i]-'0')*occur;
		    occur=occur*0.1;
		}//for
	}//if
 j=i;
 return num;
}
void show(sqstack1 s1,sqstack2 s2,int count,int i){
	
	printf("\n %d     ",count);
	while(s1.move !=s1.top ){
		printf("  %g  ",*(s1.move ));
		s1.move ++;
	}
	printf("                  ");
	while(s2.move !=s2.top ){
		printf("%c",*(s2.move ));
		s2.move ++;
	}
	s1.move =s1.base ;
	s2.move =s2.base ;
	printf("                           ");
	if(count<strlen(str))//当字符串读取完时，不需要再继续输出
	for(;str[i]!='#';i++)
		printf("%c",str[i]);
}
void destroystack(sqstack1 &s1,sqstack2 &s2){
	if(s1.base!=NULL){
	    for(s1.move =s1.base+1;s1.move !=s1.top ;s1.move++){
		free(s1.base );
		s1.base =s1.move ;
		}
	}
	if(s2.base !=NULL){
	for(s2.move =s2.base ;s2.move !=s2.top ;s2.move ++){
		free(s2.base );
		s2.base =s2.move ;
	}
	}
}
     
	
int  checkstring(char *s){
	int i=0;
	int k=0;
	char* p;
	p=s;
	char c=*s;
	if(c=='+'||c=='-'||c=='*'||c=='/'||c=='.'||c==')') {
		cout<<"字符串的第一个数输入为"<<c<<"语法错误！\n";
	    
		return 0;
	}//第一个字符的判断
	
	while((*p)!='\0'){
		if((*p)=='#') break;
		else p++;
	}
	if((*p)=='\0'){
		cout<<"此输入中无结束符'#',程序会有错误\n";
		
		return 0;
	}//结束符的判断
	p=s;
	while((*s)!='#'){
		if( ((*p)=='+'||(*p)=='-'||(*p)=='*'||(*p)=='/'||(*p)=='('||(*p)=='.')  &&
			((*s)=='+'||(*s)=='-'||(*s)=='*'||(*s)=='/'||(*s)==')'||(*s)=='.')  &&( ((*p)!='(') &&((*s)!=')') ))
		{
			cout<<"\n此字符串中"<<*p<<"和"<<*s<<"同在一起，语法错误！";
			
			return 0;
		}//相邻字符的判！
		if(k>=0){
			if((*s)=='(') k++;
			else if((*s)==')') k--;
		}//字符串中的'(' ')'的计数
		if(k<0){
			cout<<"\n符号')'前没有正确匹配的'('.";
			return 0;
		}//判断是否有')'比'('多
		p=s;
		s++;
	}//while
	if(k!=0){
		cout<<"\n符号'('后没有正确匹配的')'.";
		return 0;
	}//判断括号是否匹配
	if(strlen(str)>MAXSIZE){
		cout<<"\n此字符串太长！ ";
		return 0;
				}//判断字符的长
	for(i=0;s[i]!='#';i++){
		if(!(in(s[i])||(s[i]>47&&s[i]<58)))
			
			cout<<"\n输入有非法字符"<<s[i]<<endl;
			return 0;
		}//判断是否有非法字符的出现
	
	return 1;
}

void evaluateexpression(){
	
	
	char s[6];
	strcpy(s,"quit");
	cout<<"\n请输入一个表达式：(以#为结束)";
	cin>>str;
	
	
	while(!(checkstring(str))){
         cout<<"请重新输入：(输quit退出)";
		 cin>>str;
		 if(strcmp(str,s)==0)  exit(0);
	}
	cout<<"\n算术表达式为：";
	cout<<str<<endl;
	int i=0,j=i,count=0;
	float num,result;
	float a,b;
	char x,theta;
	initstack1(OPND);
	initstack2(OPTR);
	push2(OPTR,'#');
	
	
	i=0;
	printf("\n步骤--------OPND栈----------------------- OPTR栈----------------------------字符串读取");
	while((str[i]!='#'&&str[i]!='\0')||gettop2(OPTR)!='#'){
		if(!in(str[i])){
			j=i;
			num=checknum(str,j);
			push1(OPND,num);
			i=j;
		
		}
		else
			switch(precede(gettop2(OPTR),str[i])){
			case'<':
				push2(OPTR,str[i]);
				i++;
				break;
			case'=':
				pop2(OPTR,x);
				i++;
				break;
			case'>':
				pop2(OPTR,theta);
				pop1(OPND,b);
				pop1(OPND,a);
				push1(OPND,operate(a,theta,b));
				if(theta=='/'&&b==0){
					printf("\n除数不能为0");
					exit(0);
				}
				break;

		}

		count++;
		
		show(OPND,OPTR,count,i);
	}

	pop1(OPND,result);
	printf("\n表达式结果为：%s=%5.2f\n",str,result);
}



     
	
  int  menu(){
	char yourchoice;
	cout<<"-------------------------------算术表达式求值------------------------------------------\n"<<endl;
	cout<<"                                                         此程序尚有多处不足，请谅解\n";
	cout<<"                                                        姓名:张莉 学号:040640203\n"<<endl;
	cout<<"\n                  工作菜单选择                              "<<endl;
	cout<<"a.表达式求值；                                                "<<endl;
	cout<<"b.退出"<<endl;
	cout<<"----------------------------------------------------------------------------------------"<<endl;
	while(1){

	cout<<"请输入你的选择：";
	cin>>yourchoice;
	switch(yourchoice){
	case'a':
		system("cls");
		evaluateexpression();
		break;
	case'b':
		destroystack(OPND,OPTR);
		cout<<"谢谢使用！";
		exit(0);
	}//switch
     cout<<"-----------------------------算术表达式求值-----------------------------------------\n"<<endl;
	 cout<<"                                                      此程序尚有多处不足，请谅解\n";
	cout<<"                                                       姓名:张莉 学号:040640203\n"<<endl;
	cout<<"\n                   工作菜单选择                           "<<endl;
	cout<<"a.表达式求值；                 "<<endl;
	cout<<"b.退出"<<endl;
	cout<<"------------------------------------------------------------------------------------\n"<<endl;
	}
	return 1;

}
  void main(){
	  system("color 1f"); //屏幕颜色设定
      system("mode con: cols=140 lines=130");
        menu();
		}