欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

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

程序员文章站 2022-03-09 22:36:51
...

2017年西北工业大学夏令营第四题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;
}