12803 - Arithmetic Expressions

[Alim14]

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

[brianfry713]

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

Code: Select all

1
( ( 0.01 / 100.00 ) * 100.0 )

AC output: 0.01

[Alim14]

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

[brianfry713]

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.

[Alim14]

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

[alexhighviz]

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]

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.

[alexhighviz]

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.