## 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

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

### 708 - Dreisam Equations

any superman can help me work out this problem ?

UFP2161
A great helper
Posts: 277
Joined: Mon Jul 21, 2003 7:49 pm
Contact:
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

thx for your help

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

### 708 ... again

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);
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("");
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;
}

{
//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
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
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

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

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
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:
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
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:
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

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!