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;
}