12803 - Arithmetic Expressions

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

Moderator: Board moderators

Post Reply
Alim14
New poster
Posts: 8
Joined: Sun Jan 05, 2014 3:40 pm
Location: BUBT,Dhaka, Bangladesh

Re: 12803 - Arithmetic Expressions

Post by Alim14 » Mon Oct 06, 2014 2:21 pm

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

Post by brianfry713 » Mon Oct 06, 2014 11:24 pm

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
Location: BUBT,Dhaka, Bangladesh

Re: 12803 - Arithmetic Expressions

Post by Alim14 » Thu Oct 09, 2014 1:32 pm

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

Post by brianfry713 » Thu Oct 09, 2014 8:07 pm

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
Location: BUBT,Dhaka, Bangladesh

Re: 12803 - Arithmetic Expressions

Post by Alim14 » Sat Oct 11, 2014 5:46 pm

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

Post by alexhighviz » Fri Nov 21, 2014 4:30 am

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

Post by brianfry713 » Fri Nov 21, 2014 11:05 pm

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

Post by alexhighviz » Sat Nov 22, 2014 5:13 pm

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.

Post Reply

Return to “Volume 128 (12800-12899)”