## 12803 - Arithmetic Expressions

Moderator: Board moderators

Alim14
New poster
Posts: 8
Joined: Sun Jan 05, 2014 3:40 pm

### Re: 12803 - Arithmetic Expressions

WA again and again.Please help me to find my error or give me some test cases in which my code fails.

Code: Select all

``````/*
Problem: 12803 - Arithmetic Expressions
Algorithm: Stack
*/

#include<bits/stdc++.h>
using namespace std;
#define LL long long

int main()
{
int i,j,k,n,m,d,test;
scanf("%d",&test);
getchar();
while(test--)
{
string s,p;
getline(cin,s);
stringstream ss;
ss<<s;
stack<string>st;
while(ss>>p)
{
if(p==")")
{
string tmp1=st.top();
st.pop();
stringstream sss;
sss<<tmp1;
double num1;
sss>>num1;
string br=st.top();
st.pop();
string tmp2=st.top();
st.pop();
sss.clear();
sss<<tmp2;
double num2;
sss>>num2;
st.pop();

double val;
if(br=="+") val=num2+num1;
else if(br=="-") val=num2-num1;
else if(br=="*") val=num2*num1;
else val=num2/num1;
// nearest is the two decimal places of val. if val=3.77777, then nearest=3.78
double nearest = roundf(val * 100.0) / 100.0;

string ins;
sss.clear();
sss<<nearest;
sss>>ins;
st.push(ins);
}
else st.push(p);
}
string gg=st.top();
ss.clear();
double ans;
ss<<gg;
ss>>ans;
printf("%.2lf\n",ans);
}
return 0;
}``````
When I believe it is possible, I always find a way

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

### Re: 12803 - Arithmetic Expressions

Don't round until you print the final result.
Input:

Code: Select all

``````1
( ( 0.01 / 100.00 ) * 100.0 )
``````
AC output: 0.01
Check input and AC output for thousands of problems on uDebug!

Alim14
New poster
Posts: 8
Joined: Sun Jan 05, 2014 3:40 pm

### Re: 12803 - Arithmetic Expressions

brianfry713 wrote:Don't round until you print the final result.
Input:

Code: Select all

``````1
( ( 0.01 / 100.00 ) * 100.0 )
``````
AC output: 0.01
Fixed this issue, but again WA

Code: Select all

``````/*
Problem: 12803 - Arithmetic Expressions
Algorithm: Stack
*/

#include<bits/stdc++.h>
using namespace std;
#define LL long long

int main()
{
int i,j,k,n,m,d,test;
scanf("%d",&test);
getchar();
while(test--)
{
string s,p;
getline(cin,s);
stringstream ss;
ss<<s;
stack<string>st;
while(ss>>p)
{
if(p==")")
{
string tmp1=st.top();
st.pop();
stringstream sss;
sss<<tmp1;
double num1;
sss>>num1;
string br=st.top();
st.pop();
string tmp2=st.top();
st.pop();
sss.clear();
sss<<tmp2;
double num2;
sss>>num2;
st.pop();

double val;
if(br=="+") val=num2+num1;
else if(br=="-") val=num2-num1;
else if(br=="*") val=num2*num1;
else val=num2/num1;
string ins;
sss.clear();
sss<<val;
sss>>ins;
st.push(ins);
}
else st.push(p);
}
string gg=st.top();
ss.clear();
double ans;
ss<<gg;
ss>>ans;
printf("%.2lf\n",ans);
}
return 0;
}
``````
When I believe it is possible, I always find a way

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

### Re: 12803 - Arithmetic Expressions

You are losing precision converting a double to and from a string.
Try input:

Code: Select all

``````1
( ( 1000000.01 / 1000000.00 ) * 1000000.0 )
``````
AC output:

Code: Select all

``1000000.01``
I solved it using a recursive descent parser where all intermediate values are kept as a double.
Check input and AC output for thousands of problems on uDebug!

Alim14
New poster
Posts: 8
Joined: Sun Jan 05, 2014 3:40 pm

### Re: 12803 - Arithmetic Expressions

brianfry713 wrote:You are losing precision converting a double to and from a string.
Try input:

Code: Select all

``````1
( ( 1000000.01 / 1000000.00 ) * 1000000.0 )
``````
AC output:

Code: Select all

``1000000.01``
I solved it using a recursive descent parser where all intermediate values are kept as a double.
Thanks Brianfry, Got AC, Learned something new !!
When I believe it is possible, I always find a way

alexhighviz
New poster
Posts: 3
Joined: Fri Nov 21, 2014 4:00 am

### Re: 12803 - Arithmetic Expressions

It seems to me that I solved this problem but the judge does not agree (WA).

I see that my solution is different from uDebug, but I cannot see why uDebug would be right.

My input is:

Code: Select all

``````1
( 0.41 / 2.00 )``````
For which my answer is 0.21 and uDebug says 0.20. The PDF brief says that 0.005 must be rounded to 0.01.

Does anybody have an idea?

My solution is below, it uses either doubles or numerator/denominator pairs to represent the rational numbers, but either setting leads to Wrong Answer:

Code: Select all

``````#include <cmath>
#include <iomanip>
#include <iostream>
#include <sstream>
#include <string>
#include <type_traits>
#include <utility>

// Requires C++11

typedef long long int_type;

int_type gcd(int_type a, int_type b) // Greatest Common Denominator
{
if (a < b) std::swap(a,b);
if (a == 0) return 1;
if (b == 0) return a;
while (a = a % b) std::swap(a, b);
return b;
}

struct number
{
number() : div(1), d(1), n(0){}
number(int_type num, int_type den) : div(gcd(abs(num), abs(den))), n(num / div), d(den / div) {}
number(double real) : div(1), n(static_cast<int_type>(round(100 * real))), d(100){}

number operator+(const number& b) const { return number(n * b.d + b.n * d, b.d * d); }
number operator-(const number& b) const { return number(n * b.d - b.n * d, b.d * d); }
number operator*(const number& b) const { return number(n * b.n          , b.d * d); }
number operator/(const number& b) const { return number(n * b.d          , b.n * d); }

const int_type div; // common divider
const int_type n;   // numerator
const int_type d;   // denominator
};

double round2(double v)
{
const int p = 100;
return round(v * p) / p;
}

double round2(const number& v)
{
const int p = 100;
const double out = (((abs(v.n) * 2 * p) / abs(v.d) + 1) / 2) / static_cast<double>(p);
return (v.n * v.d < 0 ? -out : out);
}

template<typename T> // T is either number or double
T parse(std::istream& is)
{
std::string str;
is >> str;
if (str[0] == '(') { // read the expression
const T lhs = parse<T>(is); // parse lhs expression
is >> str;
char operation = str[0];
const T rhs = parse<T>(is); // parse rhs expression
is >> str; // skip closing bracket

switch (operation) { // perform the operation
case '+': return lhs + rhs;
case '-': return lhs - rhs;
case '*': return lhs * rhs;
case '/': return lhs / rhs;
default:  return T(); // default surpresses a warning in VS
}
}
else { // parse the value
return T(std::stod(str));
}
}

int main()
{
static const bool use_floating_point = false;
typedef std::conditional<use_floating_point, double, number>::type number_type;
std::string line;
std::getline(std::cin, line);
std::stringstream ss(line);
int n;
ss >> n;
for (int i = 0; i < n; ++i) {
std::getline(std::cin, line);
std::stringstream ss2(line);
std::cout << std::fixed << std::setprecision(2) << round2( parse<number_type>(ss2) ) << std::endl;
}
return 0;
}
}``````

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

### Re: 12803 - Arithmetic Expressions

I agree that it's wrong but I tried a few different ways and got WA.
To get AC I just used:
printf("%.2lf\n", result);

If you find a way to get AC and the correct output for that input let me know.
Check input and AC output for thousands of problems on uDebug!

alexhighviz
New poster
Posts: 3
Joined: Fri Nov 21, 2014 4:00 am

### Re: 12803 - Arithmetic Expressions

Thanks. That fixes it. It is a bit of a pity if the wrong answer is accepted and the right one is not. It would have been better if they had asked for three decimal digits and allow us to be 0.001 off.