2017年西北工业大学夏令营第四题

题目只是提示四则运算，是否存在负数，是否存在括号等情况并没详细说明，因此为保证程序的健壮性，编写代码时将这两种情况考虑进去，具体的详细注释在代码中体现。

补充测试样例：

13
(-1)*(-1)-1
(-1)*(-1)-(1)*(-1)
(-1*-3*(1*4))*1
(((1+9)))
-1+((-2*-3)*-1)
1+1
2.2/3
1+2*3
1+2*-300
-1+2+0
(-1*(-3+-4-(-1*-2)))
(-2)
2*(-300)/(-2)*2
 

#include<iostream>
#include<stack>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
int a[300][300]={0};//用来判断该当前字符串是进行入栈操作，还是先出栈再入栈 
int book[300]={0};//用来判断'-'是减号还是负号 
void init(){
	//当前符号是左括号直接入栈 
	a['(']['('] = 1;
	a['+']['('] = 1;
	a['-']['('] = 1;
	a['*']['('] = 1;
	a['/']['('] = 1;
	//栈内没有操作符则将该操作符入栈 
	a['#']['('] = 1;
	a['#']['+'] = 1;
	a['#']['-'] = 1;
	a['#']['*'] = 1;
	a['#']['/'] = 1;
	//栈顶为左括号，四则运算符号入栈 
	a['(']['+'] = 1;
	a['(']['-'] = 1;
	a['(']['*'] = 1;
	a['(']['/'] = 1;
	//栈顶为加号，乘除入栈 
	a['+']['*'] = 1;
	a['+']['/'] = 1;
	//栈顶为减号，乘除入栈 
	a['-']['*'] = 1;
	a['-']['/'] = 1;
	//以下三种符号后面紧跟着的'-'为负号 
	book['('] = 1;
	book['+'] = 1;
	book['-'] = 1;
	book['*'] = 1;
	book['/'] = 1;
}
//运算操作 
double acc(double a,double b,char c){
	if(c == '+'){
		return a + b;
	}
	if(c == '-'){
		return a - b;
	}
	if(c == '*'){
		return a * b;
	}
	if(c == '/'){
		return a / b;
	}
}
int main(){
	
	init();
	int n;
	cin>>n;
	
	for(int k = 0;k < n;k++){
		string s;
		cin>>s;
		cout<<s<<endl;
		stack<double>s1;//操作数栈 
		stack<char>s2;//操作符栈 
		s2.push('#');//放入一个非操作符 
		int cnt = 0;//用来统计当前操作数的长度 
		bool flag = true;//第一个字符就是'-'则该符号肯定为负号 
		
		for(int i = 0;i < s.length();i++){
			//以下三种情况表示该字符属于操作数的一部分
			//1、阿拉伯数字 
			//2、小数点
			//3、负号 
			if( (s[i] >= '0'&&s[i] <= '9') || (s[i] == '.') || (flag&&s[i] == '-')){
				cnt ++;//操作数长度加一 
				flag = false;//跟在操作数后面的'-'为减号 
				//字符串末尾是操作数时需要进行额外判断 
				if(i == s.length()-1&&cnt > 0){
					s1.push( atof( s.substr(i-cnt+1,cnt).c_str() ) );
				//	cout<<s1.top()<<endl;
				}
				
				
			}else{
				//该字符前面出现了操作数，将字符串转化成浮点数入栈 
				if(flag==false&&cnt > 0){
					s1.push( atof( s.substr(i-cnt,cnt).c_str() ) );
				//	cout<<s1.top()<<endl;
					cnt = 0;//操作数长度清零 
				}
				if(book[s[i]] == 1){//该字符后面紧跟着的'-'是负号 
					flag = true;
				}
				//cout<<"操作符"<<s[i]<<endl;
				
				if(s[i] == ')'){
					//两个括号之间只有一个操作数，没有操作符，将左括号出栈 
					if(s2.top()=='('){
						s2.pop();
					}else{
						//两个括号中间有操作符和两个操作数，应该先把这两个数进行四则运算，再将左括号出栈 
						
						//进行四则运算最少需要两个数，并且需要一个操作符，左括号已经排除了 
						if(s1.size() > 1&&book[s2.top()]){
							//先出栈的在操作符后面，后出栈的在操作符前面
							//栈的原则，先进后出 
							double c = s1.top();
							s1.pop();
							double b = s1.top();
							s1.pop();
							char top = s2.top();
							s2.pop();
							s2.pop();
							s1.push(acc(b,c,top));
						//	cout<<b<<"  "<<c<<"  "<<top<<"         "<<s[i]<<endl;
						}
						
					}
					
				}else{
					
					if(a[s2.top()][s[i]] == 1){
						s2.push(s[i]);//当前操作符的优先级比栈顶操作符优先级高 
					}else{
						//进行四则运算最少需要两个数，并且需要一个操作符，如果左括号不会进入该步 
						if(s1.size() > 1&&book[s2.top()]){
							double c = s1.top();
							s1.pop();
							double b = s1.top();
							s1.pop();
							char top = s2.top();
							s2.pop();
							s1.push(acc(b,c,top));
						//	cout<<b<<"  "<<c<<"  "<<top<<"         "<<s[i]<<endl;
						}
						s2.push(s[i]);//将当前操作符入栈 
					}
					
				} 
				
			}
		
		}
		//完场剩余的四则运算 
		while(s1.size() > 1&&book[s2.top()]){
			double c = s1.top();
			s1.pop();
			double b = s1.top();
			s1.pop();
			char top = s2.top();
			s2.pop();
			s1.push(acc(b,c,top));
		//	cout<<b<<"  "<<c<<"  "<<top<<endl;
		}
		printf("%.1f\n",s1.top());
	}
	return 0;
}