作者:无为2502863873 | 来源:互联网 | 2023-05-17 21:44
链接:
POJ_1100
Sample Input
18 = 7 (5 3) 2
30 = 3 3 5
18 = 3 3 5
5 = 3 3
0
Sample Output
Equation #1:
18=7+(5-3)*2
Equation #2:
30=3+3*5
Equation #3:
Impossible
Equation #4:
Impossible
对于这道题,我的基本思想是:整行读取,将等号左边的数用变量left保存下来,用于比较。右边采取栈的方式,申明两个栈,stack num 和stack bracket,num用于存储右边的数字(不在括号中的),bracket用于存储括号中的数字,将bracket中的数用递归的方法算出所有可能结果,保存在一个数组中,再将结果逐一推到栈num中,继续读取数字,遇到括号则先计算括号里的可能值。额,那个,貌似挺复杂的,然后我就卡那儿了~不知道各位大侠觉得这办法怎么样?我越来越觉得不太可行了~还请各位多多指教~下面是我未能完成的代码:
#include
#include
#include
#include
#include
using namespace std;
int num=0;//用于计算测试数据的组数
int calculate(vector v,int i,int j){//想计算栈中所有可能值,原打算用递归,但,没写出来
stack num;
stack bracket;
while(i!=j){//将数字和括号内的数字分别入栈num和bracket。
if(v[j]!=')'){
num.push(v[j]-'0');
j--;}
else if(v[j]==')'){
j--;
if(v[j]!=')'&&v[j]!='(')
{bracket.push(v[j]-'0');
j--;}
}
else if(v[j]=='('){
int answer;
int f=0;
while(bracket.empty()){//求一个栈的元素的所有可能结果,这儿卡住了,不知道怎么做了。
int m=bracket.top();
bracket.pop();
int n=bracket.top();
bracket.pop();
if(f=0){
bracket.push(m+n);
f=1;
}else if(f=1){
bracket.push(m*n);
f=2;
}else if(f=2){
bracket.push(m-n);
answer=bracket.top();
bracket.pop();
}
}
}
}
return 0;
}
void match(char data[]){
num++;
int left=0;
int i=0;
while(data[i]!=' '){//left
left+=data[i]-'0';
if(data[i+1]!=' ')
left*=10;
i++;
}
vector v;
while(data[i]){//将等号右边的括号和数据推入栈中
if(data[i]!=' '&&data[i]!='=')
v.push_back(data[i]);
i++;
}
/* vector::const_iterator j;
for(j=v.begin ();j!=v.end();j++)
cout<<*j;
*/
int n=v.end()-v.begin();
//cout<