BIT2010年上机第二题

题目要求：

     输入表达式，输出值。分两种情况：中缀表达式和后缀表达式。

解题思路

       1.中缀表达式，需要转换成后缀表达式

       2.后缀表达式直接计算

       设置一个符号栈，然后将输入的表达式按照字符进行读取，如果数值则放进后缀表达式的字符串汇中，如果是符号，则比对栈内的符号和当前指向的符号的优先级。

       很经典的一道题目，和括号匹配，进制转换，迷宫问题都是一样的，运用到了栈

      也是参考了一些网友的解题思路和代码

代码如下

#include<iostream>#include<stack>#include<string>#include<sstream>using namespace std;int isp(char ch){	switch(ch){		case'#':return 0;		case'(':return 1;		case'+':return 3;		case'-':return 3;		case'*':return 5;		case'/':return 5;		case')':return 6;		}}int icp(char ch){	switch(ch){		case'#':return 0;		case'(':return 6;		case'+':return 2;		case'-':return 2;		case'*':return 4;		case'/':return 4;		case')':return 1;	}}//获得后缀表达式string shorten(string s){	stack<char> b; //符号栈	b.push('#');	string str; //后缀表达式	for(int i =0;i<s.size();i++){		if(isdigit(s[i])||s[i]=='.'){			while(isdigit(s[i])||s[i]=='.') str +=s[i++];			i--;			str+='$';		}else{			if(isp(b.top())<icp(s[i])){				b.push(s[i]);				continue;			}else if(isp(b.top())>icp(s[i])){				while(1){					str +=b.top();					b.pop();					if(isp(b.top())==icp(s[i])){ //相等（）						b.pop();						break;					}					if(isp(b.top())<icp(s[i])){						b.push(s[i]);						break;					}				}			}		}	}	while(!b.empty()){		str +=b.top();		b.pop();	}	return str;}//计算后缀表达式int compute(string str){	stack<double> stack;	double a,b,c;	string s;	for(int i=0;i<str.size();i++){		if(str[i]!='$'){			if(isdigit(str[i])||str[i]=='.'){				while(isdigit(str[i])||str[i]=='.')  s+=str[i++];				i--;			}else{				if(str[i]=='*'){					a = stack.top();					stack.pop();					b = stack.top();					stack.pop();					c = a*b;					stack.push(c);				}				if(str[i]=='/'){					a = stack.top();					stack.pop();					b = stack.top();					stack.pop();					c = a/b;					stack.push(c);				}				if(str[i]=='+'){					a = stack.top();					stack.pop();					b = stack.top();					stack.pop();					c = a+b;					stack.push(c);				}				if(str[i]=='-'){					a = stack.top();					stack.pop();					b = stack.top();					stack.pop();					c = a-b;					stack.push(c);				}			}		}else{			istringstream iss(s);   //str2double			double x;			iss>>x;			stack.push(x);			s="";		}	}	return stack.top();}int main(){	string s; //表达式	char ch;	string sur;	cout<<"请进行选择操作 1.中缀表达式计算  2.后缀表达式计算  3.退出"<<endl;		while(cin>>ch){		if(ch=='1'){			cout<<"请输入表达式，以#结束："<<endl;			cin>>s;			sur = shorten(s);			cout<<"后缀表达式："<<sur<<endl;			cout<<"表达式的结果："<<compute(sur)<<endl;		}else if(ch=='2'){			cout<<"请输入表达式,数值用$间隔："<<endl;			cin>>s;			cout<<"表达式的结果："<<compute(s)<<endl;		}else if(ch=='3'){			break;		}else{			cout<<"输入非法，请重新输入"<<endl;		}		cout<<"请进行选择操作 1.中缀表达式计算  2.后缀表达式计算  3.退出"<<endl;	}		return 0;}