這個是poj的1100 題 Dreisam Equations
提交的時候說是記憶體超限了， 不知道怎么修改。思路是遞回的DFS 然后判斷每個支路是否符合要求。請教下各位前輩應該怎么修改？我猜測是在遞回的程序中使用了過多的變數（每層遞回我用了3個堆疊，題目限制最多有12個數）
#include <stdio.h>
#include <iostream>
#include <String>
#include <stdlib.h>
#include <stack>
using namespace std;
enum flag {find,not_find};
flag outputflag=not_find;
int size=0,result;
int global_element=0;
char global_sign[50];
int count=0;
void initial_global()
{
size=0;
result=0;
global_element=0;
memset(global_sign,0,sizeof(char)*50);
outputflag=not_find;
}
void readin(int answer_i,int element[50],int &elem_num)
{
elem_num=0;
memset(element,0,sizeof(int)*50);
string str;//初始化
getline(cin,str);
if(str=="0")
exit(0);
int loca=str.find('=');
string answer=str.substr(0,loca-1);
answer_i=atoi(str.c_str());
result=answer_i;//use global for convenience
for(int i=loca;i<str.length();i++)
{
if(str[i]==' ')//start getting a num
{
int end=str.find_first_of(' ',i+1);
string temp=str.substr(i+1,end-i-1);
if(temp[0]=='(')
{
element[elem_num++]=-1;
element[elem_num]=atoi(temp.substr(1,1).c_str());
}
else if(end>0&&temp[end-i-2]==')')//there are end-i-1 digital so the location of last digit should -1
{
element[elem_num++]=atoi(temp.substr(0,1).c_str());
element[elem_num]=-2;
}
else
{
element[elem_num]=atoi(temp.c_str());
}
elem_num++;
size++;
}
}
global_element=elem_num;
return;
}
bool calculate(stack<char> sign,int element[50])
{
stack<char> reverse,copy;
stack<char> cal_stack;
stack<char> num_stack;
while(!sign.empty())
{
reverse.push(sign.top());
sign.pop();
}
copy=reverse;
memset(global_sign,0,sizeof(char)*50);
for(int i=0;!copy.empty();i++)
{
global_sign[i]=copy.top();
copy.pop();
}
for(int i=0;i<global_element;i++)
{
if(element[i]==-1)
num_stack.push(-1);
else if(element[i]==-2)
{
int temp=num_stack.top();
num_stack.pop();
num_stack.pop();
if(num_stack.empty()||num_stack.top()==-1)
num_stack.push(temp);//pop ( out and push the number back
else
{
int op1=num_stack.top();
num_stack.pop();
if(cal_stack.top()=='+')
num_stack.push(op1+temp);
else if(cal_stack.top()=='-')
num_stack.push(op1-temp);
else if(cal_stack.top()=='*')
num_stack.push(op1*temp);
cal_stack.pop();
}
cal_stack.push(reverse.top());
reverse.pop();
}
else //it is number
{
if(num_stack.empty()||num_stack.top()==-1)
{
num_stack.push(element[i]);
}
else
{
int op1=num_stack.top();
num_stack.pop();
if(cal_stack.top()=='+')
num_stack.push(op1+element[i]);
else if(cal_stack.top()=='-')
num_stack.push(op1-element[i]);
else if(cal_stack.top()=='*')
num_stack.push(op1*element[i]);
cal_stack.pop();
}
if(element[i+1]!=-2&&element[i+1]!=0)
{
cal_stack.push(reverse.top());
reverse.pop();
}
}
}
if(num_stack.top()==result)
return true;
else
return false;
}
void output(int element[50])
{
cout<<"Equation #"<<count<<":"<<endl;
cout<<result<<"=";
int n=0;
for(int i=0;i<global_element;i++)
{
if(element[i]==-1)
{
cout<<"(";
}
else if(element[i]==-2)
{
cout<<")"<<global_sign[n];
n++;
}
else
{
if(element[i+1]!=-2)
{
cout<<element[i]<<global_sign[n];
n++;
}
else
{
cout<<element[i];
}
}
}
cout<<endl;
return ;
}
void search(int element_num,stack<char> sign,int element[50])
{
//1 stands for '+' 2 stands for '-' 3 stands for '*'
if(element_num==1)// element should be 1 more than operator and the element num is 1 larger than actual element number
{
if(calculate(sign,element))
{
if(outputflag==not_find)
output(element);
outputflag=find;
}
return;
}
else
{
sign.push('+');
search(element_num-1,sign,element);
sign.pop();
sign.push('-');
search(element_num-1,sign,element);
sign.pop();
sign.push('*');
search(element_num-1,sign,element);
sign.pop();
if(element_num==size&&outputflag==not_find)
{
cout<<"Equation #"<<count<<":"<<endl;
cout<<"Impossible"<<endl;
}
}
}
int main()
{
while(1)
{
initial_global();
count++;
stack<char> sign;
int element_num=0,answer=0;
int element[50];
readin(answer,element,element_num);
search(size,sign,element);
}
return 0;
}
uj5u.com熱心網友回復：
給個原題的鏈接uj5u.com熱心網友回復：
題目連接 http://poj.org/problem?id=1100轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/117234.html
標籤：基礎類
上一篇：求匿名登陸服務器的埠號?