708 - Dreisam Equations

All about problems in Volume 7. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
dennis
New poster
Posts: 5
Joined: Fri Aug 01, 2003 4:41 am
Contact:

708 - Dreisam Equations

Post by dennis »

any superman can help me work out this problem ?
thx in advance

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:

Post by UFP2161 »

I think the concept is fairly simple. Convert infix notation to postfix notation. Then using the postfix notation, parse it and anytime there's supposed to be an operator, recusively plug in either +, - and *.

However, the string manipulation and parsing to get AC is quite tedious. At least it was for me.

dennis
New poster
Posts: 5
Joined: Fri Aug 01, 2003 4:41 am
Contact:

708

Post by dennis »

thx for your help :D

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

708 ... again

Post by Experimenter »

hi, everybody. it seems the code below gets correct answers when I am testing but the judge says "Runtime error". I am just looking for tests which will lead to this situation.
I would really appreciate any help offered.
ps
please don't say that the code is rubbish - I know that. I was just writing in a hush with an intention to make it least work somehow.
[cpp]#include <stdio.h>
#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
#include <stack>
#include <sstream>

using namespace std;

const int iBufSize = 0xff;
bool Pred(char a,char b);
void Format_String(string &s);
void Read_String(string &s);
long Extract_Number(string &s);
string Extract_String_To_Compute(string &s);
bool FindEquation(string::iterator iBegin,string &s,long lNum);
long ComputeEquation(const string &s);
string PolRecord(string sIn);
bool IsOperation(char c);
int GetPriority(char c);
long EvaluateString(string s);
string MyLongInt2String(long lNum);
long MyString2LongInt(string &s);
bool Pred2(char a,char b);

int main();
char chOperations[] = "+-*";

int main()
{
int i__ = 1;
while(true)
{
long lNum;
string s(""),sComp("");
Read_String(s);
if(s.length() == 1 && s[0] == '0')
break;
Format_String(s);
lNum = Extract_Number(s);
sComp+= Extract_String_To_Compute(s);
bool bFound = FindEquation(sComp.begin(),sComp,lNum);
cout<<"Equation #"<<i__++<<":"<<endl;
if(bFound)
{
cout<<lNum<<'=';
cout<<sComp<<endl;
}
else
cout<<"Impossible."<<endl;

}

return (0);
}

long MyString2LongInt(string &s)
{
string::reverse_iterator iRev;
long lRes =0, lExp = 1;

for (iRev = s.rbegin(); iRev != s.rend(); iRev++)
{
if('-' == *iRev)
{
lRes = -lRes;
break;
}
lRes += (*iRev - 0x30)*lExp;
lExp *= 10;
}

return lRes;
}
string MyLongInt2String(long lNum)
{
string s("");
bool fl = lNum < 0;
lNum = fl ? -lNum : lNum;
char c;

if(!lNum) return string("0");

while(lNum)
{
c = (lNum % 10) + 0x30;
lNum /= 10;
s.insert(s.begin(),c);
}

if(fl)
s.insert(s.begin(),'-');

return s;
}
long EvaluateString(string s)
{
long lA,lB,lRes;

char cOp;
string::iterator i = s.begin(),j;
while(i != s.end() )
{
if( !IsOperation(*i))
{
i++;
continue;
}
cOp = *i;
j = i - 2;
lA = 0;

long lExp = 1;

while(j != s.begin() && ' ' != *j && '-' != *j)
{
lA += ((*j) - 0x30)*lExp;
lExp *= 10;
j--;
}
if('-' == *j)
{
lA = -lA;
if(j != s.begin()) --j;
}


lB = 0;
j--;
lExp = 1;
bool fl = true;
while((' ' != *j && '-' != *j) && fl)
{
if(j == s.begin())
fl = false;
lB += ((*j) - 0x30)*lExp;
lExp *= 10;
if(fl) j--;
}

if('-' == *j)
{
lB = -lB;
if(j != s.begin()) --j;
}


switch(cOp)
{
case '+':
lRes = lA + lB;
break;
case '-':
lRes = lB - lA;
break;
case '*':
lRes = lA * lB;
break;
}

string sTemp = MyLongInt2String(lRes);
int iOffset = ((s.begin() == j) ? j : j + 1) - s.begin();
s.replace( j == s.begin() ? j : j + 1,i + 1,sTemp);
i = s.begin() + iOffset + sTemp.length();
if(*i == '-' && i != s.end()) i++;
}

return lRes = MyString2LongInt(s);
}
int GetPriority(char c)
{
if('(' == c) return 0;
if(')' == c) return 1;
if(IsOperation(c)) return 2;
}
bool IsOperation(char c)
{
bool fl = false;
int i;
for(i=0; i < 3 && !fl; i++)
fl = (c == chOperations);
return fl;
}

string PolRecord(string sIn)
{
string sOut("");
stack <char> st;
string::iterator i;

i = sIn.begin();

while(i != sIn.end())
{
if( *i >= '0' && *i <= '9')
{
for(; *i >= '0' && *i <= '9'; i++)
{
sOut += *i;
}
sOut+= " ";
continue;
}

if(IsOperation(*i))
{
if(st.empty())
{
st.push(*i);
}
else
{
if(GetPriority(st.top()) < GetPriority(*i))
{
st.push(*i);
}
else
{
while(!st.empty() && (GetPriority(st.top()) >= GetPriority(*i)))
{
string sTemp;
sTemp += (st.top());
sTemp += " ";
sOut += sTemp;
st.pop();
}
st.push(*i);
}
}
goto next_iter;
}

if('(' == *i)
{
st.push('(');
goto next_iter;
}

if(')' == *i)
{
while(!st.empty() && st.top() != '(')
{
sOut += st.top() + string(" ");
st.pop();
}
st.pop();
}

next_iter:
i++;

}
while(!st.empty())
{
sOut += st.top() + string(" ");
st.pop();
}

while( (sOut.begin() != (sOut.end() - 1)) && *(sOut.end() - 1) == ' ')
{
sOut.erase(sOut.end() - 1);
}

return sOut;
}

long ComputeEquation(const string &s)
{
string sPol = PolRecord(s);
return EvaluateString(sPol);
}
bool FindEquation(string::iterator iBegin,string &s,long lNum)
{
string::iterator iEnd = s.end();
iBegin = find(iBegin,iEnd,' ');

if(iBegin == iEnd)
{
long lRet = ComputeEquation(s);
return lNum == lRet;
}
int i;

for(i = 0; i < 3; i++)
{
*iBegin = chOperations;
if(FindEquation(iBegin + 1,s,lNum))
{
return true;
}
}
*iBegin = ' ';
return false;
}

string Extract_String_To_Compute(string &s)
{
string::iterator iT = find(s.begin(),s.end(),'=');
iT++;
while(*iT == ' ') iT++;

string sRes = "";
for(;iT != s.end(); iT++)
sRes += *iT;

return sRes;
}

long Extract_Number(string &s)
{
string::iterator iT = find(s.begin(),s.end(),'=');
long lRes = 0, lExp = 1;
iT--;
while(*iT == ' ') iT--;
while(iT != s.begin())
{
lRes += ((*iT) - 0x30)*lExp;
lExp *= 10;
--iT;
}
lRes += ((*iT) - 0x30)*lExp;

return lRes;
}

void Read_String(string &s)
{
//s = "18 = 32 23 (2 3) 2 ";
char chStr[iBufSize] = {0};
cin.getline(chStr,iBufSize);
s = chStr;//*/
string::iterator i = s.end() - 1;
while(*i == ' ') s.erase(i--);
return;
}

void Format_String(string &s)
{
string::iterator iEnd = unique(s.begin(),s.end(),Pred);
s.erase(iEnd,s.end());

string::iterator i = s.begin();
while(i != s.end())
{
if(*i == ' ' && *(i+1) == ')')
i = s.erase(i);
else
i++;
}
return;
}

bool Pred(char a,char b)
{
bool fl;
fl = (b == a ) && (a == ' ');
fl |= (a == '(') && (b == ' ');

return fl;
}

bool Pred2(char a,char b)
{
return (b == a ) && (a == ' ');
}[/cpp]
it would be great if you replied this post. really.

Dmytro Chernysh
Experienced poster
Posts: 146
Joined: Sat Apr 26, 2003 2:51 am

Post by Dmytro Chernysh »

I can give you input/output. Mail me.

By the way, you speak Russian :-) Than mail in Russian

Experimenter
Learning poster
Posts: 76
Joined: Thu Mar 13, 2003 5:12 am
Location: Russia

Post by Experimenter »

Dmytro_Chernysh wrote:I can give you input/output. Mail me.

By the way, you speak Russian :-) Than mail in Russian
no sweat. thanks, I've emailed you already
it would be great if you replied this post. really.

guayoyo
New poster
Posts: 11
Joined: Wed Aug 17, 2005 5:59 pm
Location: Caracas, Venezuela

Test Cases

Post by guayoyo »

Hi everybody. Can any of you give me test cases for this problem, I have a RE and I don't know where.

Thank you for your consideration.
10024 - Guayoyo has Curled Up the Cube!

20717TZ
New poster
Posts: 33
Joined: Tue Apr 27, 2004 7:41 pm
Location: Santa Clara / Mountain View, CA, USA
Contact:

708 - Dreisam Equations - SampleOut is incorrect for SampleI

Post by 20717TZ »

708 - Dreisam Equations - SampleOutput is EVEN incorrect for SampleInput
There will always be at least one space or parenthesis between two numbers, otherwise the occurrence of white space is unrestricted.
This statement makes so many pitfalls, even the sample output is not correct for the sample input

Code: Select all

For Input:
18 = 7 (5 3) 2
The Output should be:
18=+7+(5-3)*2
Instead of:
18=7+(5-3)*2
And,

Code: Select all

For this input:
18 = ( ( ( 18 ) ) )
what's the output?
18=(((18)))
or
18=(+(+(+18)))
?
And,

Code: Select all

For this input:
3 = 3 6
Output should be:
3=-3+6
or
no solution?
And, if there are different solutions for each line, which one should be output?

'White space' can be '\t' ?

At last, does that mean, if there is/are continues space(s) after '=', we should always replace the space(s) with an operator (+-*) or we can just omit thi(se)s space(s)?
I Believe I Can - leestime.com

20717TZ
New poster
Posts: 33
Joined: Tue Apr 27, 2004 7:41 pm
Location: Santa Clara / Mountain View, CA, USA
Contact:

Post by 20717TZ »

I think the concept is fairly simple. Convert infix notation to postfix notation. Then using the postfix notation, parse it and anytime there's supposed to be an operator, recusively plug in either +, - and *.
I think the concept is not so clear!

708 - Dreisam Equations - SampleOutput is EVEN incorrect for SampleInput
There will always be at least one space or parenthesis between two numbers, otherwise the occurrence of white space is unrestricted.
This statement makes so many pitfalls, even the sample output is not correct for the sample input

Code: Select all

For Input:
18 = 7 (5 3) 2
The Output should be:
18=+7+(5-3)*2
Instead of:
18=7+(5-3)*2
And,

Code: Select all

For this input:
18 = ( ( ( 18 ) ) )
what's the output?
18=(((18)))
or
18=(+(+(+18)))
?
And,

Code: Select all

For this input:
3 = 3 6
Output should be:
3=-3+6
or
no solution?
And, if there are different solutions for each line, which one should be output?

'White space' can be '\t' ?

At last, does that mean, if there is/are continues space(s) after '=', we should always replace the space(s) with an operator (+-*) or we can just omit thi(se)s space(s)?[/quote]
I Believe I Can - leestime.com

20717TZ
New poster
Posts: 33
Joined: Tue Apr 27, 2004 7:41 pm
Location: Santa Clara / Mountain View, CA, USA
Contact:

Post by 20717TZ »

And should I also take the inbalance parenthesis into account, if it's required, this problem would be so complicated.

thanks everyone, can someone reply?

I spent a lot of time in this problem, and my code can get this input lines worked:
(There are '\t' or spaces in or in the end of the input lines

Code: Select all

45 =((1)) 2( (   3 4)( 5 6) 7    )8	 9		  
200 = 20 10

However, i got Runtime Error. So I'm guessing that this problem, the input has some very unusual lines. Pls, help.
I Believe I Can - leestime.com

ngchumin
New poster
Posts: 8
Joined: Sun Jun 16, 2002 11:18 am

P708

Post by ngchumin »

Hi,

can anyone help with advice on the input? it's seem like it is very very tricky. So far my program has been able to handle the below input,

Input
8 = (2 0 10 0)
12 = (10 0 2 0)
10 = 10 20
10 = (5 0 0 5)
9 = ( ( ( 18) ) ) ( ( ( 9 ) ) )((1))
0 = 0
100 = 10 10
45 =((1)) 2( ( 3 4)( 5 6) 7 )8 9
9 = ( ( ( 18) ) )( ( ( 9 ) ) )
45 =((1)) 2 ( ( 3 4) ( 5 6) 7 ) 8 9
200 = 20 10
18 = (7 5) 3 2
18 =
9 = ( ( ( 18) ) ) ( ( ( 9 ) ) )
42 = 7 ( ( (5) (2 4 ) ) 3) 2
18 = 7 (5 3) 2
30 = 3 3 5
18 = 3 3 5
5 = 3 3
0

Output
Equation #1:
12=(10+0+2+0)

Equation #2:
10=-10+20

Equation #3:
10=(5+0+0+5)

Equation #4:
9=(((18)))-(((9)))*((1))

Equation #5:
0=0

Equation #6:
100=10*10

Equation #7:
45=((1))+2+((3+4)+(5+6)+7)+8+9

Equation #8:
9=(((18)))-(((9)))

Equation #9:
45=((1))+2+((3+4)+(5+6)+7)+8+9

Equation #10:
200=20*10

Equation #11:
18=(7+5)-3*2

Equation #12:
Impossible.

Equation #13:
9=(((18)))-(((9)))

Equation #14:
42=7+(((5)+(2+4))+3)*2

Equation #15:
18=7+(5-3)*2

Equation #16:
30=3+3*5

Equation #17:
Impossible.

Equation #18:
Impossible.

Any help will be greatly appreciated!

Post Reply

Return to “Volume 7 (700-799)”