708 - Dreisam Equations

[dennis]

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

[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]

thx for your help

[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]

[Dmytro Chernysh]

I can give you input/output. Mail me.

By the way, you speak Russian Than mail in Russian

[Experimenter]

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

[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.

[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)?

[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]

[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.

[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!