数据结构-“表达式求值”

#define MAXLEN 100 #include "operate.h" #include <string> #include <windows.h> #include <iostream> using namespace std; void Calc::gotoxy(int x,int y)//光标定位函数，将光标定位到坐标(x,y) { COORD c; c.X = x - 1; c.Y = y - 1; SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),c); } void Calc::Start(){ system("color 1E");//设置背景颜色为蓝色，前景颜色为黄色 cout<<"┏━━━━━━━━━━━━━━━━━━━━━┓"<<endl <<"┃ ◇表达式求值◇ ┃"<<endl <<"┣━━━━━━━━━━━━━━━━━━━━━┫"<<endl <<"┃ ┃"<<endl <<"┃ 姓名：郑李新 ┃"<<endl <<"┃ 学号：20072110010112 ┃"<<endl <<"┃ 班级：07软件工程（1）班 ┃"<<endl <<"┃ ┃"<<endl <<"┃ 按回车键开始... ┃"<<endl <<"┣━━━━━━━━━━━━━━━━━━━━━┫"<<endl <<"┃ 2008年12月25日 ┃"<<endl <<"┗━━━━━━━━━━━━━━━━━━━━━┛"<<endl; getchar(); system("cls");//清屏 cout<<"┏━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┓"<<endl <<"┃ ◇表达式求值◇ ┃"<<endl <<"┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫"<<endl <<"┃ ┃"<<endl <<"┃ 请输入表达式，并以'#'结尾(数值小于10)： ┃"<<endl <<"┃ ┃"<<endl <<"┃ ┃"<<endl <<"┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛"<<endl; gotoxy(5,6); char input[MAXLEN]; cin>>input;//输入表达式 cout<<"┣━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┫"<<endl <<"┃ ◇结 果◇ ┃"<<endl <<"┣━━┳━━━━━━━┳━━━━━━━┳━━━━━━━━━━━━━━┫"<<endl <<"┃步骤┃ OPTR栈 ┃ OPND栈 ┃ 主要操作 ┃"<<endl <<"┣━━╋━━━━━━━╋━━━━━━━╋━━━━━━━━━━━━━━┫"<<endl; for(int i=1;i<=strlen(input)+8;i++){ cout<<"┃ ┃ ┃ ┃ ┃"<<endl; } cout<<"┣━━┻━━━━━━━┻━━━━━━━┻━━━━━━━━━━━━━━┫"<<endl <<"┃ 2008年12月25日 ┃"<<endl <<"┗━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━┛"<<endl; int count = 1; for(int i=0;i<strlen(input);){//循环读取输入的表达式 if(input[i] >= '0' && input[i] <= '9'){//如果表达式中的字符是数字 Opnd.push(input[i]-48);//将数字压入数字栈 gotoxy(42,11+count); if(strlen(input)>1) cout<<"PUSH(OPND,'"<<input[i]<<"')";//如果表达式的长度大于1，输出操作信息 i++; } else{//如果表达式中的字符是操作符 switch(Precede(Optr.top(),input[i])){//判断当前操作符和字符栈栈顶元素的优先级 case '<'://如果当前操作符比字符栈栈顶元素优先级低 gotoxy(42,11+count); Optr.push(input[i]);//将字符压入字符栈 cout<<"PUSH(OPTR,'"<<input[i]<<"')";//输出操作信息 i++; break; case '='://如果当前操作符和栈顶元素优先级相同 if(input[i]!='#'){//如果当前操作符不是'#' gotoxy(42,11+count); Optr.pop();//将堆栈栈顶元素弹出 cout<<"POP(OPTR)";//输出操作信息 } i++; break; case '>'://如果当前操作符优先级低于堆栈栈顶元素 int a,b; char d; d=Optr.top();Optr.pop();//取出字符栈的栈顶运算符 a=Opnd.top();Opnd.pop();//取出数字栈的操作数 b=Opnd.top();Opnd.pop();//取出数字栈的操作数 Operate(b,d,a);//进行运算 gotoxy(42,11+count); cout<<"Operate('"<<b<<"','"<<d<<"','"<<a<<"')";//输出操作信息 break; /*当前操作符优先级 高于栈顶 则从符号栈取一元素，从数字栈取两个元素进行运算*/ } } gotoxy(4,11+count); cout<<count;//输出序号 gotoxy(9,11+count); PrintStack(Optr);//输出当前字符栈的内容 gotoxy(25,11+count); PrintStack(Opnd);//输出当前数字栈的内容 count++; } gotoxy(42,10+count); cout<<"RESULT:"<<Opnd.top();//输出最后结果 } template<class T> void Calc::PrintStack(stack<T> _stack){//输出堆栈内容的模板函数 if(!_stack.empty()){//如果堆栈不空 stack<T> temp;//定义一个临时栈 while(!_stack.empty()){//循环输出堆栈内容 temp.push(_stack.top());//并且把堆栈内容压入临时栈，目的是倒置堆栈内所有元素 _stack.pop(); } while(!temp.empty()){//循环输出倒置后的堆栈元素 cout<<temp.top()<<' '; temp.pop(); } } } char Calc::Precede(char c1,char c2){ //判断c1,c2运算符优先级函数，优先级高返回'>',低返回'<',相同返回'=' int i=0,j=0; static char array[49]={ '>', '>', '<', '<', '<', '>', '>', '>', '>', '<', '<', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>', '>', '>', '>', '>', '<', '>', '>', '<', '<', '<', '<', '<', '=', '!', '>', '>', '>', '>', '!', '>', '>', '<', '<', '<', '<', '<', '!', '=' }; switch(c1){/* i为下面array的横标 */ case '+' : i=0;break; case '-' : i=1;break; case '*' : i=2;break; case '/' : i=3;break; case '(' : i=4;break; case ')' : i=5;break; case '#' : i=6;break; } switch(c2){/* j为下面array的纵标 */ case '+' : j=0;break; case '-' : j=1;break; case '*' : j=2;break; case '/' : j=3;break; case '(' : j=4;break; case ')' : j=5;break; case '#' : j=6;break; } return (array[7*i+j]); /* 返回运算符 */ } void Calc::Operate(double x,char g,double y){//运算函数,x,y为数字，g为运算符 switch(g) { case '+': Opnd.push(x+y);break; /*操作结果运算后进入数字栈*/ case '-': Opnd.push(x-y);break; /*操作结果运算后进入数字栈*/ case '*': Opnd.push(x*y);break; /*操作结果运算后进入数字栈*/ case '/': Opnd.push(x/y);break; /*操作结果运算后进入数字栈*/ } }