## 12088 - Expression

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

Moderator: Board moderators

3tito
New poster
Posts: 2
Joined: Fri Aug 31, 2012 1:05 pm

### 12088 - Expression

i can't figure out why my solution getting WA.

am using greedy approach and it passed many cases.

there's any cases fail my code ?

Code: Select all

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <string.h>
using namespace std;
void Simplify(string &Exp)
{
bool neg[100000];
memset(neg, false, sizeof(neg));
long long Depth = 0;

for (int i = 0; i < Exp.size(); ++i)
{
if (i < Exp.size() - 1)

if (Exp[i] == '-' && Exp[i + 1] == '(')
{
if (Exp[i] == '-')
if (neg[Depth])
Exp[i] = '+';
Depth++;
neg[Depth] = neg[Depth-1] == true ? false : true;
i++;
}
else if (Exp[i] == '(')
{
Depth++;
neg[Depth] = neg[Depth - 1];
}
else if (Exp[i] == ')')
Depth--;

if (Exp[i] == '+' || Exp[i] == '(')
{
if (neg[Depth])
Exp[i] = '-';
else Exp[i] = '+';
}
else if (Exp[i] == '-')
if (neg[Depth])
Exp[i] = '+';
}
}
void Solve(string &Exp, string nums)
{
int limdown = 0, limup = nums.size() - 1;
bool positive = true;
vector<vector <pair<int , bool> > > digit;
digit.resize(10);
int count = 0;
for (int i = 0; i < Exp.size(); ++i)
{
if (Exp[i] == '+')
positive = true;
else if (Exp[i] == '-')
positive = false;
if (Exp[i] == '#')
{
count++;
digit[count].push_back(make_pair(i,positive));
}
else
count = 0;
}
for (int i = 0 ; i < digit.size() ; ++i)
for (int j = digit[i].size() - 1; j >= 0 ; --j)
{
if (digit[i][j].second == true)
Exp[digit[i][j].first] = nums[limup--];
}

for (int i = 0; i < digit.size(); ++i)
for (int j = 0; j < digit[i].size(); ++j)
{
if (digit[i][j].second == false)
Exp[digit[i][j].first] = nums[limdown++];

}

digit.clear();
}
vector <int>  selectedNums;
int calculate(string Exp)
{
long long count = 0;
bool positive = true;
int digits = 1;
long long num = 0;

for (int i = Exp.size()-1; i >=0 ; --i)
{
if (Exp[i] >= '0' && Exp[i] <= '9')
{
num += (Exp[i] - '0')*digits;
digits *= 10;
}
else
{
if (digits!=1)
selectedNums.push_back(num);
digits = 1;
num = 0;
}
}
if (digits != 1)
selectedNums.push_back(num);

int j = selectedNums.size() - 1;
bool bnum = true;
for (int i = 0; i < Exp.size(); ++i)
{
if (Exp[i] == '+')
positive = true;
else if (Exp[i] == '-')
positive = false;
else if (Exp[i] >= '0' && Exp[i] <= '9' && bnum)
{
if (positive)
count += selectedNums[j];
else
count -= selectedNums[j];
j--;
bnum = false;
}
if (!(Exp[i] >= '0' && Exp[i] <= '9'))
bnum = true;
}

return count;
}
void printFormula(string form)
{
int j = selectedNums.size() - 1;
bool num = true;
for (int i = 0; i < form.size(); ++i)
{
if (form[i] == '#'&&num)
{
cout << selectedNums[j--];
num = false;
}
else if (form[i] != '#')
{
cout << form[i];
num = true;
}
}
selectedNums.clear();

}
int main()
{
int cases;
cin >> cases;
cin.ignore();
for (int c = 0; c < cases; c++)
{
string exp, nums , cpy;

getline(cin, exp);
cpy = exp;
getline(cin, nums);
sort(nums.begin(), nums.end());
Simplify(exp);
//cout << exp << endl;
Solve(exp , nums);
//cout << exp << endl;
int out = calculate(exp);

cout << "Case " << c+1 << ":" << endl;
printFormula(cpy);
cout << endl;
cout << out << endl;

}
return 0;
}

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

### Re: 12088 - Expression

Input:

Code: Select all

1
#-##
012
AC output:

Code: Select all

Case 1:
2-01
1
Check input and AC output for thousands of problems on uDebug!