operation.cpp

来自「表达式求值 数据结构栈的应用 自己写的课程设计代码」· C++ 代码 · 共 230 行

#include <iostream>
#include <assert.h>
#define msize 100
#define asize 10
using namespace std;
char oper[]={'+' , '-' , 
'*' , '/' , '(' , ')' , '#'};
char relationship[7][7]={
	{'>' , '>' , '<' , '<' , '<' , '>' , '>'},
	{'>' , '>' , '<' , '<' , '<' , '>' , '>'},
	{'>' , '>' , '>' , '>' , '<' , '>' , '>'},
	{'>' , '>' , '>' , '>' , '<' , '>' , '>'},
	{'<' , '<' , '<' , '<' , '<' , '=' , '0'},
	{'>' , '>' , '>' , '>' , '0' , '>' , '>'},
	{'<' , '<' , '<' , '<' , '<' , '0' , '0'}
};

typedef struct {
	char * base;
	char * top;
	int optrsize;
}opstack,*op;
typedef struct {
	int *base;
	int *top;
	int maxsize;
}opernum,*num;

void initstack1(opstack & s){
	s.base=(char*)malloc(msize*sizeof(char));
	s.top=s.base;
	s.optrsize=msize;
}
void initstack2(opernum & s){
	s.base=(int*)malloc(msize*sizeof(int));
	s.top=s.base;
	s.maxsize=msize;
}
void push1(opstack &s,char e){
	if (s.top-s.base>=s.optrsize){
		s.base=(char *)realloc(s.base,(s.optrsize+asize ) *sizeof(char));
		s.top=s.base+s.optrsize;
		s.optrsize+=asize;
	}
	*s.top++=e;
}
void push2(opernum &s,int e){
	if (s.top-s.base>=s.maxsize){
		s.base=(int *)realloc(s.base,(s.maxsize+asize ) *sizeof(int));
		s.top=s.base+s.maxsize;
		s.maxsize+=asize;
	}
	*s.top++=e;
}
char gettop(opstack &s){
	assert(s.top>s.base);
	return *(s.top-1);
}
int gettop1(opernum &s){
	assert(s.top>s.base);
	return *(s.top-1);
}
char pop1(opstack &s){
	assert(s.top>s.base);
	return *--s.top;
}
int pop2(opernum &s){
	assert(s.top>=s.base);
	return *--s.top;
}
void print1 (opstack & s){
	char *p=s.top;
	while (p!=s.base){
		cout<<*(p-1)<<' ';
		p--;
	}
}	
void print2 (opernum & s){
	int *p=s.top;
	if (p!=s.base){
		while (p!=s.base){
			cout<<*(p-1)<<' ';
			p--;
		}
	}
	else
		cout<<"It is empty.";
}
char precede(char s,char t){//s->1,t->2
	int i;
	int x=-1,y=-1;
	for (i=0;i<7;i++){
		if (oper[i]==s)
			x=i;
		if (oper[i]==t)
			y=i;
		if (x!=-1 && y!=-1)
			break;
	}
	return relationship[x][y];
}
int operate (int a,char theta,int b){
	if (theta=='+')
		return a+b;
	if (theta=='-')
		return a-b;
	if (theta=='*')
		return a*b;
	if (theta=='/'){
		if (b==0)
			return INT_MAX;
		return a/b;
	}
}
bool isnumber(char c){
	if (c>='0' && c<='9')
		return true;
	return false;
}
int main(){
	cout<<"Please input.The input is terminated when input '#':"<<endl; 
	opstack oper;
	opernum nd;
	initstack1(oper);
	initstack2(nd);
	//push2(nd,INT_MAX);
	push1(oper,'#');
	char c,temp;
	int n=0,a,b;
	/*while (isnumber(c=getchar())){
		int cc=c-48;
		n=n*10+cc;
	}
	push2(nd,n);
	n=0;*/
	int num=1;
	while ((c=getchar())!= '\n'){
		cout<<"step:"<<num<<endl;
		num++;
		cout<<"opstack:";
		print1(oper);
		cout<<endl;
		cout<<"opernum:";
		print2(nd);
		cout<<endl;
		cout<<"The input char:"<<c<<endl;;
		cout<<"The main operations:"<<endl;
		if (isnumber(c)){
			int cc=c-48;
			n=n*10+cc;
			cout<<"Waiting for next number."<<endl;
			cout<<endl;
			//cout<<cc<<' '<<n<<endl;
			continue;
		}
		
		if (n){
			push2(nd,n);
			cout<<"push2(nd,"<<n<<')'<<endl;
			n=0;
		}
		
			
		//cout<<pop2(nd)<<endl;
		//cout<<n<<endl;
		switch(precede(gettop(oper),c)){
			case '<':
				push1(oper,c);
				cout<<"push1(oper,"<<c<<')'<<endl;
				break;
			case '=':
				pop1(oper);
				cout<<"pop1(oper)"<<endl;
				break;
			case '>':
				temp=pop1(oper);
				if (c=='+' || c=='-' || c=='*' || c=='/'){
					push1(oper,c);
					cout<<"push1(oper,"<<c<<')'<<endl;
				}
				b=pop2(nd);
				a=pop2(nd);
				push2(nd,operate(a,temp,b));
				cout<<"temp=pop1(oper) "<<endl;
				cout<<b<<"=pop2(nd) "<<endl;
				cout<<a<<"=pop2(nd) "<<endl;
				cout<<"push2(nd,operate("<<a<<","<<temp<<","<<b<<"))"<<endl;
				//cout<<"push2(nd,operate("<<a<<",temp,"<<b<<"))"<<endl;
				break;
		}
		if (c==')'){
			while ((gettop(oper))!='('){
				temp=pop1(oper);
				b=pop2(nd);
				a=pop2(nd);
				push2(nd,operate(a,temp,b));
				cout<<"temp=pop1(oper) "<<endl;
				cout<<b<<"=pop2(nd) "<<endl;
				cout<<a<<"=pop2(nd) "<<endl;
				
				cout<<"push2(nd,operate("<<a<<","<<temp<<","<<b<<"))"<<endl;
			}
			pop1(oper);
		}
		if (c=='#'){
			while ((gettop(oper))!='#'){//(*(nd.top-2)!=INT_MAX){
				temp=pop1(oper);
				b=pop2(nd);
				a=pop2(nd);
				push2(nd,operate(a,temp,b));
				cout<<"temp=pop1(oper) "<<endl;
				cout<<b<<"=pop2(nd) "<<endl;
				cout<<a<<"=pop2(nd) "<<endl;
				cout<<"push2(nd,operate("<<a<<","<<temp<<","<<b<<"))"<<endl;
			}
			cout<<endl;
			cout<<"The result is:"<<gettop1(nd)<<endl;
			break;
		}
		cout<<endl;
	}
	/*push2(nd,n);
	temp=pop1(oper);
	b=pop2(nd);				
	a=pop2(nd);
	push2(nd,operate(a,temp,b));*/
	//cout<<pop2(nd)<<endl;
	//cout<<gettop1(nd)<<' '<<*(nd.top-2)<<endl;
	return 0;
}