数据结构实验2---表达式求值（“栈”实现）

[c++]代码库

#include<iostream>  

#include<string>  

#include <sstream>  

#include<fstream>  

#define STACK_INIT_SIZE 100  

#define INCREAMENT 100  

#define ZUIDAWEISHU 10  

#define ERROR 0  

using namespace std;  

class YunSuanFu{//运算符类  

	char fuhao;  

	int pri;  

public :  

	char get_fuhao(){  

		return fuhao;  

	}  

	int get_pri(){  

		return pri;  

	}  

	void set_fuhao(char e){  

		fuhao = e;  

	}  

	void set_pri(int e){  

		pri = e;  

	}  

	YunSuanFu(char e){  

		fuhao = e;  

		if(e == '(' || e == ')' || e == '#')   

			pri = 0;  

		if(e == '+' || e == '-')  

			pri = 1;  

		if(e == '*' || e == '/')  

			pri = 2;  

	}  

	YunSuanFu(){//函数体为空  

	}  

};  

typedef struct{//SqStack1  

	int * bottom;  

	int * top;  

	int stacksize;  

}SqStack1;  

typedef struct{//SqStack2  

	YunSuanFu * bottom;  

	YunSuanFu * top;  

	int stacksize;  

}SqStack2;  

bool createStack1(SqStack1 &s){//创建栈  

	int a[STACK_INIT_SIZE];  

	s.bottom = a;  

	if(!s.bottom){  

		return false;  

	}  

	s.stacksize = STACK_INIT_SIZE;  

	s.top = s.bottom;  

	return true;  

}  



bool createStack2(SqStack2 &s){//创建栈  

	YunSuanFu a[STACK_INIT_SIZE];  

	s.bottom = a;  

	if(!s.bottom){  

		return false;  

	}  

	s.stacksize = STACK_INIT_SIZE;  

	s.top = s.bottom;  

	return true;  

}  

bool isEmpty1(SqStack1 &s){//判空  

	return s.bottom == s.top ? true : false;  

}  

bool isEmpty2(SqStack2 &s){  

	return s.bottom == s.top ? true : false;  

}  

bool get_top1(SqStack1 &s1, int &e){//得到栈顶元素  

	if(s1.top == s1.bottom)  

		return false;  

	e = *(s1.top - 1);  

	return true;  

}  

bool get_top2(SqStack2 &s2, YunSuanFu &e){  

	if(s2.top == s2.bottom)  

		return false;  

	e.set_fuhao((*(s2.top - 1)).get_fuhao());  

	e.set_pri((*(s2.top - 1)).get_pri());  

	return true;  

}  

bool push1(SqStack1 &s, int &e){//入栈  

	if((s.top - s.bottom ) >= s.stacksize){  

		int *newbase =(int*) realloc (s.bottom,(s.stacksize + INCREAMENT) * sizeof(int));  

		if(!newbase)   

			return false;  

		s.bottom = newbase;  

		s.top = s.bottom + s.stacksize;  

		s.stacksize += INCREAMENT;  

	}  

	*(s.top) = e;  

	cout<<*(s.top)<<endl;//ceshi  

	cout<<s.top<<endl;//ceshi  

	++(s.top);  

	return true;  

}  

bool push2(SqStack2 &s, YunSuanFu &e){  

	if(s.top - s.bottom >= s.stacksize){  

		YunSuanFu* newbase =(YunSuanFu*) realloc (s.bottom,(s.stacksize + INCREAMENT) * (sizeof(char)+sizeof(int)));  

		if(!newbase)  

			return false;  

		s.bottom = newbase;  

		s.top = s.bottom + s.stacksize;  

		s.stacksize += INCREAMENT;  

	}  

	(s.top)->set_fuhao(e.get_fuhao());//类不能直接赋值！！！  

	(s.top)->set_pri(e.get_pri());  

	s.top++;  

	return true;  

}  

bool pop1(SqStack1 &s, int &e){//出栈  

	if(s.top == s.bottom)  

		return false;  

	e = *(s.top - 1);//这里有错误  

	cout<< e<<endl;//ceshi  

	cout<<s.top-1<<endl;//ceshi  



	--s.top;  

	return true;  

}  

bool pop2(SqStack2 &s, YunSuanFu & e){  

	if(s.top == s.bottom)  

		return false;  

	e.set_fuhao((*(s.top - 1)).get_fuhao());  

	e.set_pri((*(s.top - 1)).get_pri());  

	s.top--;  

	return true;  

}  

void jisuan(SqStack1 &s1,SqStack2 & s2){//计算  

	int e1,e2;  

	YunSuanFu e3;  

	pop2(s2,e3);  

	if(e3.get_fuhao() == '+'){  

		pop1(s1,e1);  

		pop1(s1,e2);  

		int jieguo = e2 + e1;  

		push1(s1,jieguo);  

	}  

	if(e3.get_fuhao() == '-'){  

		int e1,e2;  

		pop1(s1,e1);  

		pop1(s1,e2);  

		int jieguo = e2 - e1;  

		push1(s1,jieguo);  

	}  

	if(e3.get_fuhao() == '*'){  

		int e1,e2;  

		pop1(s1,e1);  

		pop1(s1,e2);  

		int jieguo = e2 * e1;  

		push1(s1,jieguo);  

	}  

	if(e3.get_fuhao() == '/'){  

		int e1,e2;  

		pop1(s1,e1);  

		pop1(s1,e2);  

		int jieguo = e2 / e1;  

		push1(s1,jieguo);  

	}  

}  

//还要定义一个合法性检验函数  



void ceshi(){//测试函数  

	cout<<"进来了"<<endl;  

}//ceshi();//测试  



void biaodashiqiuzhi(string lujing){//表达式求值  

	string wenjianlujing = lujing;  

	SqStack1 s1;  

	SqStack2 s2;  

	createStack1(s1);   

	createStack2(s2);  

	ifstream in;  

	in.open(wenjianlujing,ios::out);  

	char t[ZUIDAWEISHU];  

	in>>t;  

	static string shuzhizichuan = "";//后面用  

	for(int i = 0,count1 = 0; t[i] != '\0'; i++){  

		if(t[i] == '+' || t[i] == '-' || t[i] == '*' || t[i] == '/' || t[i] == '('|| t[i] == ')' || t[i] == '#'){  

			if(t[i] == '#'){//测试ok  

				if(count1 == 0){  

					YunSuanFu yunsuanfu = YunSuanFu(t[i]);  

					push2(s2,yunsuanfu);  

					count1 = 1;  

				}else{  

					YunSuanFu yunsuanfu1;  

					do{  

						jisuan(s1,s2);  

						get_top2(s2,yunsuanfu1);  

					}while(yunsuanfu1.get_fuhao() != '#');  

					int e1;  

					pop1(s1,e1);  

					YunSuanFu e;  

					pop2(s2,e);  

					if(isEmpty2(s2) && isEmpty1(s1)){  

						cout<<"jieguoshi:"<<e1<<endl;  

					}else{  

						return ERROR;  

					}  

					count1 = 0;  

				}  

			}  

			if(t[i] == '('){  

				YunSuanFu yunsuanfu = YunSuanFu(t[i]);  

				push2(s2,yunsuanfu);  

			}  

			if(t[i] == ')'){  

				YunSuanFu yunsuanfu1;  

				do{  

					jisuan(s1,s2);  

					get_top2(s2,yunsuanfu1);  

				}while(yunsuanfu1.get_fuhao() != '(');  

				YunSuanFu e;  

				pop2(s2,e);  

			}  

			if(t[i] == '+' || t[i] == '-' || t[i] == '*' || t[i] == '/'){  

				YunSuanFu yunsuanfu = YunSuanFu(t[i]),yunsuanfu2;  

				get_top2(s2,yunsuanfu2);  

				if(yunsuanfu.get_pri() > yunsuanfu2.get_pri()){  

					push2(s2,yunsuanfu);  

				}else{  

					YunSuanFu yunsuanfu1;  

					do{  

						jisuan(s1,s2);  

						get_top2(s2,yunsuanfu1);  

					}while(yunsuanfu.get_pri() <= yunsuanfu1.get_pri());  

					push2(s2,yunsuanfu);  

				}  

			}  

		}else{  

			shuzhizichuan = shuzhizichuan + t[i];  

			if(!(t[i + 1] == '+' || t[i + 1] == '-' || t[i + 1] == '*' || t[i + 1] == '/' || t[i + 1] == '('|| t[i + 1] == ')' || t[i + 1] == '#')){  

				continue;  

			}else{  

				int shuzhi;  

				stringstream ss;  

				ss<<shuzhizichuan;  

				ss>>shuzhi;  

				push1(s1, shuzhi);  

				shuzhizichuan = "";  

			}  

		}  

	}  

	in.close();  

}  



int main(){//主函数  

	// SqStack1 s1;//测试用  

	//SqStack2 s2;  

	//createStack1(s1);  

	//createStack2(s2);  

	//int e1 = 3;  

	//bool t2 = push1(s1,e1);  

	//cout<<"s1.top: "<<*(s1.top - 1)<<endl;  

	//cout<<t2<<endl;  

	//bool t1 = isEmpty1(s1);   

	//cout<<t1<<endl;  

	//int e = 0;  

	//bool t3 = pop1(s1,e);  

	//bool t4 = isEmpty1(s1);  

	//cout<<t3<<endl<<e<<endl;  



	string lujing = "biaodashi.txt";  

	biaodashiqiuzhi(lujing);  

}